I'd largely echo Chris' answer but with some possible deviations. The ultimate thing I'd echo wholeheartedly is to store indices to your particles and contacts, stored in big sequences like a couple of big vector pers network. If particles die, then you can remove them in constant-time and reclaim/insert in constant-time, like so:
... where Nodes nodes[n] might be std::vector<Node>.
First, what would be an efficient and community-recommended way to store the contacts for each particle?
Assuming it's efficient to just simulate and gather the contacts for all particles at once (which is often the case in many simulations), short answer:
// Stores all the contacts between particles. Each per-particle
// contact list begins with a count followed by the indices to each
// contact.
std::vector<int> contact_data;
// Stores an index into the contact data for each particle.
std::vector<int> contacts;
To get the contacts for the nth particle, we do:
// Fetch the index into the contact data for the nth particle.
const int cd_index = contacts[n];
// Fetch the number of contacts.
const int num = contact_data[cd_index];
// Fetch a pointer to the array of contact indices.
const int* indices = contact_data.data() + cd_index + 1;
And now you have the indices of the contacts and the number of them for the nth particle. You can clear the list and compute it for each time step. You can also do it multithreaded with a bit of work (gather the contacts for ranges of particles in each thread locally, then merge the results into the two vectors at the end).
network.getContacts(Particle particle)
If you follow the suggestion to use indices, the above turns to this:
// Returns the number of contacts and a pointer to the array
// of contact indices for the particle indexed by 'particle_index'.
std::pair<int, const int*> network.getContacts(int particle_index)
... you can use something a bit nicer than std::pair, like your own structure or class.
SmallVectors and the Like
Now using something like boost::small_vector or llvm::SmallVector is a very good solution, far superior to requiring a heap allocation for every particle as would be the case if you used std::vector for each one. But if you want to persistently store the contacts, these small buffer optimizations start to get a bit explosive in memory (they are great for temporary storage though), which is why I recommend just a big old vector of integers instead.
[...] 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?
shared_ptr is for sharing ownership of a resource and extending its lifetime until all owners release their ownership. To just refer to a resource in multiple places without sharing ownership (which is all you need here) and without duplication of the resource's data, just use plain old indices or pointers. There's a pretty hefty relative overhead to shared_ptr used on a per-particle or per-contact basis.
A quick thing in practice using the above techniques:
And not really "particles" in this case but still agents that collide with each other and a collision list between agents (gathered all at once into two vectors of integers as shown above): 500,000 agents, single-threaded, with a good portion of the time spent just plotting pixels and not merely simulating:
First, what would be an efficient and community-recommended way to store the contacts for each particle?
If you want to do things very efficiently when the temptation is to store a boatload of tiny lists, ideally store all the data in big sequences, not a bunch of teeny ones. You don't actually need to instantiate a million containers in order to represent the equivalent of a million containers associated to a million elements. You can just use two, for example: one storing all the data and one parallel to the million elements storing starting indices into that data.
This is a general optimization strategy regardless of context, and it addresses a common performance gotcha in languages that provide a lot of convenient containers. Those containers are very efficient for storing a million elements in one container, but not very efficient for storing a million containers with a few elements each.