Should I return an iterator or a pointer to an element in a STL container?

Question

I am developing an engine for porting existing code to a different platform. The existing code has been developed using a third party API, and my engine will redefine those third party API functions in terms of my new platform.

The following definitions come from the API:

typedef unsigned long shape_handle;    
shape_handle make_new_shape( int type );

I need to redefine make_new_shape and I have the option to redefine shape_handle.

I have defined this structure ( simplified ):

struct Shape
{
    int type
};

The Caller of make_new_shape doesn't care about the underlying structure of Shape, it just needs a "handle" to it so that it can call functions like:

void `set_shape_color( myshape, RED );`

where myshape is the handle to the shape.

My engine will manage the memory for the Shape objects and other requirements dictate that the engine should be storing Shape objects in a list or other iterable container.

My question is, what is the safest way to represent this handle - if the Shape itself is going to be stored in a std::list - an iterator, a pointer, an index?

Answer 1

Both an iterators or a pointers will do bad stuff if you try to access them after the object has been deleted so neither is intrinsically safer. The advantage of an iterator is that it can be used to access other members of your collection.

So, if you just want to access your Shape then a pointer will be simplest. If you want to iterate through your list then use an iterator.

An index is useless in a list since std::list does not overload the [] operator.

Answer 2

IIF the internal representation will be a list of Shapes, then pointers and iterators are safe. Once an element is allocated, no relocation will ever occur. I wouldn't recommend an index for obvious access performance reasons. O(n) in case of lists.

If you were using a vector, then don't use iterators or pointers, because elements can be relocated when you exceed the vectors capacity, and your pointers/iterators would become invalid.

If you want a representation that is safe regardless of the internal container, then create a container (list/vector) of pointers to your shapes, and return the shape pointer to your client. Even if the container is moved around in memory, the Shape objects will stay in the same location.

Answer 3

The answer depends on your representation:

• for std::list, use an iterator (not a pointer), because an iterator allows you to remove the element without walking the whole list.
• for std::map or boost::unordered_map, use the Key (of course)

Your design would be much strong if you used an associative container, because associative containers give you the ability to query for the presence of the object, rather than invoking Undefined Behavior.

Try benchmarking both map and unordered_map to see which one is faster in your case :)

Answer 4

Iterators aren't safer than pointers, but they have much better diagnostics than raw pointers if you're using a checked STL implementation!

For example, in a debug build, if you return a pointer to a list element, then erase that list element, you have a dangling pointer. If you access it you get a crash and all you can see is junk data. That can make it difficult to work out what went wrong.

If you use an iterator and you have a checked STL implementation, as soon as you access the iterator to an erased element, you get a message something like "iterator was invalidated". That's because you erased the element it points to. Boom, you just saved yourself potentially a whole lot of debugging effort.

So, not indices for O(n) performance. Between pointers and iterators - always iterators!