Implementing list position locator in C++?

Question

I am writing a basic Graph API in C++ (I know libraries already exist, but I am doing it for the practice/experience). The structure is basically that of an adjacency list representation. So there are Vertex objects and Edge objects, and the Graph class contains:

list<Vertex *> vertexList
list<Edge *> edgeList

Each Edge object has two Vertex* members representing its endpoints, and each Vertex object has a list of Edge* members representing the edges incident to the Vertex.

All this is quite standard, but here is my problem. I want to be able to implement deletion of Edges and Vertices in constant time, so for example each Vertex object should have a Locator member that points to the position of its Vertex* in the vertexList. The way I first implemented this was by saving a list::iterator, as follows:

vertexList.push_back(v);
v->locator = --vertexList.end();

Then if I need to delete this vertex later, then rather than searching the whole vertexList for its pointer, I can call:

vertexList.erase(v->locator);

This works fine at first, but it seems that if enough changes (deletions) are made to the list, the iterators will become out-of-date and I get all sorts of iterator errors at runtime. This seems strange for a linked list, because it doesn't seem like you should ever need to re-allocate the remaining members of the list after deletions, but maybe the STL does this to optimize by keeping memory somewhat contiguous?

In any case, I would appreciate it if anyone has any insight as to why this happens. Is there a standard way in C++ to implement a locator that will keep track of an element's position in a list without becoming obsolete?

Much thanks, Jeff

See how boost graph library addresses the problem. It is several orders of magnitude more complex than a simple `std::list` (it basically allows you to define the graph in any way you may possibly want), but it is worth looking at since you are learning C++. — Alexandre C., Apr 01 '12 at 23:21

Andrew Tomazos · Answer 1 · 2012-04-01T23:22:41.700

(I am assuming you are single-threaded, obviously list isn't thread-safe)

but maybe the STL does this to optimize by keeping memory somewhat contiguous?

Incorrect - list::insert, list::push_front and list::push_back do not affect the validity of list::iterators. If you are only calling these mutators on the list, than it will remain valid.

In any case, I would appreciate it if anyone has any insight as to why this happens. Is there a standard way in C++ to implement a locator that will keep track of an element's position in a list without becoming obsolete?

Your method should work, please post some code demonstrating it not working. In the meantime here are two alternative representations:

Why not use:

struct Graph
{
    typedef unique_ptr<Vertex> PVertex;
    typedef unique_ptr<Edge> PEdge;

    unordered_set<PVertex> verticies;
    unordered_set<PEdge> edges;
};

That way you can delete them in constant time like you wish. unordered_set is generally implemented with a hash table so its amortized O(1) access time.

And also unique_ptr means that you can have the unordred_sets "owning" them

If verticies are countable and have a fixed maxmimum upper limit (N), another representation would be:

struct Graph
{
    typedef unique_ptr<Vertex> PVertex;
    typedef unique_ptr<Edge> PEdge;

    array<PVertex, N> verticies;
    array<array<PEdge, N>, N> edges;
};

Where edges[i][j] holds the edge between verticies[i] and verticies[j]

If verticies[x] or edges[x][y] is nullptr in means the corresponding vertex or edge does not exist.

Old C++ Versions:

unordered_set was introduced in TR1. If you don't have this you can use boost. if you don't want to use boost you can use a plain old set which will give logn access time, or you can implement your own hash table.
unique_ptr can be replaced with auto_ptr for older versions.
array can be replaced with a regular array or with a vector.

Please note, that unordered_set<>, unique_ptr<> and array<> are C++11 features. — stanwise, Apr 01 '12 at 22:47
If `std::unordered_set` and `std::array` are not available, and a compiler upgrade is not possible, and you don't have a recruiter, you can always get them from Boost. — R. Martinho Fernandes, Apr 01 '12 at 22:52
And the 2011 version is the current ratified standard of C++. By default we use the current version - but ok, I add some notes for older versions — Andrew Tomazos, Apr 01 '12 at 22:55

Implementing list position locator in C++?

1 Answers1