Iterator vs. Reference vs. Pointer

Question

I have a class that spawns an arbitrary number of worker object that compute their results into a std::vector. I'm going to remove some of the worker objects at certain points but I'd like to keep their results in a certain ordering only known to the class that spawned them. Thus I'm providing the vectors for the output in the class A.

I have (IMO) three options: I could either have pointers to the vectors, references or iterators as members. While the iterator option has certain draw backs (The iterator could be incremented.) I'm unsure if pointers or references are clearer. I feel references are better because they can't be NULL and a cruncher would require the presence of a vector.

What I'm most unsure about is the validity of the references. Will they be invalidated by some operations on the std::list< std::vector<int> >? Are those operations the same as invalidating the iterators of std::list? Is there another approach I don't see right now? Also the coupling to a container doesn't feel right: I force a specific container to the Cruncher class.

Code provided for clarity:

#include <list>
#include <vector>
#include <boost/ptr_container/ptr_list.hpp>

class Cruncher {
  std::vector<int>* numPointer;
  std::vector<int>& numRef;
  std::list< std::vector<int> >::iterator numIterator;
public:
  Cruncher(std::vector<int>*);
  Cruncher(std::vector<int>&);
  Cruncher(std::list< std::vector<int> >::iterator);
};

class A {
  std::list< std::vector<int> > container;
  boost::ptr_list< std::vector<int> > container2;
  std::vector<Cruncher> cruncherList;
};

Answer 1

If an iterator is invalidated, it would also invalidate a pointer/reference that the iterator was converted into. If you have this:

std::vector<T>::iterator it = ...;
T *p = &(*it);
T &r = *p;

if the iterator is invalidated (for example a call to push_back can invalidate all existing vector iterators), the pointer and the reference will also be invalidated.

From the standard 23.2.4.2/5 (vector capacity):

Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence.

The same general principal holds for std::list. If an iterator is invalidated, the pointers and references the iterator is converted into are also invalidated.

The difference between std::list and std::vector is what causes iterator invalidation. A std::list iterator is valid as long as you don't remove the element it is referring to. So where as std::vector<>::push_back can invalidate an iterator, std::list<>::push_back cannot.

Answer 2

If the parent's vector's contents is re-allocated after spawning your worker threads, then their pointers, references, iterators, or whatever are almost certainly invalid. A list MAY be different (given how they're allocated) but I don't know, and may even be platform-dependent.

Basically, if you have multiple worker threads, it's probably safest to actually have a method on the parent class to dump the results back into as long as the copy isn't that taxing. Sure it's not as good as allocating directly into the parent, but then you need to ensure the container you're dumping into doesn't get "lost" on re-allocation.

If the list you're using is guaranteed not to re-allocate its "other" space when members are added (or deleted), then that would achieve what you're looking for, but the vector is definitely unsafe. But either way, the way in which you access it (pointer, reference, or iterator) probably doesn't matter that much as long as your "root container" isn't going to move around its contents.

Edit:

As mentioned in the comments below, here's a block about the list from SGI's website (emphasis mine) :

Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

So this basically says "use a list as your master store" and then each worker can dump into its own, and knows it won't get invalidated when another worker is completely done and their vector is deleted from the list.

Answer 3

In the current version of C++ (i.e. no move constructors) then pointers into items embedded in a std::list will be invalidated along with the list iterators.

If however you used a std::list*>, then the vector* could move around but the vector would not, so your pointer into the vector would remain valid.

With the addition of move constructors in C++0x the vector content is likely to stay put unless the vector itself is resized, but any such assumption would be inherently non-portable.

Answer 4

I like the pointer parameter. It is a matter of style. I prefer this parameter type style:

• Const reference: Large object is being passed for reading. Reference avoids wasteful copying. Looks just like pass-by-value at the point of call.
• Pointer: Object is being passed for reading and writing. The call will have an "&" to get the pointer, so the writing is made obvious during code review.
• Non-const reference: banned, because code review can't tell which parameters might get changed as a side effect.

As you say, an iterator creates a pointless dependency on the parent container type. (std::list is implemented as a double-linked list, so only deleting its entry invalidates a vector. So it would work.)