C++ – Using Vectors of Shared Pointers to Prevent Object Duplication

cc++11classclass-designsmart-pointer

In my C++ project, I have three classes, Particle, Contact, and Network. The Network class will have N particles (std::vector<Particle> particles) and Nc contacts (std::vector<Contact> contacts). Particle objects will each have a number of contacts, represented by Contact objects, and contacts are shared by pairs of particles.

It will be necessary for me to know what contacts a specific particle has, and I have decided to be able to obtain that information through the Network object (e.g., using network.getContacts(Particle particle)).

My question can be broken into two parts:

First, what would be an efficient and community-recommended way to store the contacts for each particle?

I believe that I can either create a vector of vector of shared pointers to Contact objects, vector<vector<shared_ptr<Contact>>> prtContacts (where I have left off std:: for ease of viewing), so that prtContacts[i] will contain a vector of shared pointers to the contacts of the ith particle. It has been suggested that using shared_ptr in this context is useful, as it will ensure that I am not creating duplicate Contact objects for two particles with a shared contact. Is there an alternative method that would make more sense?

Second, if I do end up creating prtContacts as defined above, what is the best way to initialize it? My current thinking is to have an initial loop that initializes std::vector<Contact> contacts with the Nc contacts and then have a second loop that initializes prtContacts with shared pointers to the Contacts. Is that reasonable or, again, are there alternative, more efficient, approaches?

Thank you!

Some additional information:

The number of particles, N, will range from O(10^1) to perhaps O(10^4). The number of contacts per particle will most likely not exceed 6-7, but will be allowed to vary. Each contact will have a position and contact force (2-component vector) associated with it, and both positions and contact forces will be allowed to vary during the course of simulations (e.g., Monte Carlo simulations).

Best Answer

The right solution will depend a lot on your non-functional requirements. How many particles will you typically have? How many contacts does a particle typically have? How much is a network updated, and in what ways? How fast does it need to be?

I suggest referring to objects by index if you can and then particle contacts can be a list of contact indexes. If a particle typically has a small number of contacts then instead of a vector I suggest using something that is optimized for a small number of elements like boost::container::small_vector, absl::inlined_vector, folly::small_vector or llvm::SmallVector. 

using ParticleContacts = boost::container::small_vector<int, 12>;

class Network {
  std::vector<Particle> particles;
  std::vector<Contact> contacts;
  std::vector<ParticleContacts> particle_contacts;
 public:
  ParticleContacts getParticleContacts(int particle_index) const {
    return particle_contacts.at(particle_index);
  }
  Contact getContact(int contact_index) const {
    return contacts.at(contact_index);
  }
  //...
};

Live demo.

Edit: If you have to be able to delete from the middle of the vector of contacts then using an index will not work. I would seriously consider if you can change your algorithm so that this is not necessary. Not only does it invalidate pointers, iterators and indexes but it also is quite inefficient because all the contacts after the deletion have to be moved. Perhaps, for example, you can just leave orphaned contacts until the end of the simulation with no connection to a particle. Anyway, if you really need to be able to delete from the middle of the list of contacts perhaps a vector is not the best data structure and you should prefer something like a linked list. The advantage of a linked list is you can do quick deletion from the middle and also pointers to contacts in the list are not invalidated by inserts or deletions so your list of particle contacts can be raw pointers. The downside is it is much slower and does not allow random access.

using ParticleContacts = boost::container::small_vector<Contact*, 12>;

class Network {
  std::vector<Particle> particles;
  std::forward_list<Contact> contacts;
  std::vector<ParticleContacts> particle_contacts;
 public:
  ParticleContacts getParticleContacts(int particle_index) const {
    return particle_contacts.at(particle_index);
  } 
  void addParticle(const Particle& particle) {
    particles.push_back(particle);
    particle_contacts.emplace_back();
  } 
  Contact* addParticleContact(int particle_index_1, int particle_index_2) {
    contacts.emplace_front();
    particle_contacts.at(particle_index_1).push_back(&contacts.front());
    particle_contacts.at(particle_index_2).push_back(&contacts.front());  
    return &contacts.front();
  }
};

Live demo.

Alternatively, you could use std::vector<std::unique_ptr<Contact>>. Raw pointers to the contact won't be invalidated by insertions and deletions. It has the advantage of allowing random access but the disadvantage of being slower at insertions and deletions: Live demo

The right choice will depend on how the data is typically accessed by the simulation.

Related Topic