C++: need indexed set

Question

I need an indexed associative container that operates as follows:

• initially empty, size=0.

• when I add a new element to it, it places it at index [size], very similar to a vector's push_back. It increments the size and returns the index of the newly added element.

• if the element already exists, it returns the index where it occurs.

Set seems the ideal data structure for this but I don't see any thing like getting an index from a find operation. Find on a set returns an iterator to the element.

Will taking the difference with set.begin() be the correct thing to do in this situation?

Answer 1

There's no immediately-appropriate data structure in the STL for this, but one straightforward and fairly efficient way of implementing this would be to use a map and a vector of pointers. The map maps objects to their index in the array (so that checking whether an object exists is efficient, and, if the object does exist already, the index is at hand immediately), and the vector maps indexes to the object in the map (so that retrieving objects by index is efficient).

std::map<T,size_t> objects;
std::vector<const T *> indexed;

To add an element:

size_t add_element(const T &v) {
    std::map<T,size_t>::iterator it=objects.find(v);
    if(it==objects.end()) {
        it=objects.insert(std::map<T,size_t>::value_type(v,objects.size())).first;
        indexed.push_back(&it->first);
    }
    return it->second;
}

(Obvious alterations according to personal style might be to store a vector of map iterators, use map::insert every time and check the bool part of the result to see whether indexed needs updating, etc.)

And to get an element:

const T &get_element(size_t index) {
    return *indexed[index];
}

And that's that. One issue is of course that once an object is in the set, it can't be modified. This is a sort of leak from the way it's been implemented here, because map keys are const, for obvious reasons -- but in fact it's what's wanted anyway, I think, regardless of implementation. If you're insisting on having no duplicates, then once an object is in the list it mustn't be modifiable, in case any modifications would make it become a duplicate of another object.

(Also note that I've cheated a bit by using size_t here -- I suppose std::vector<const T *>::size_type might be more precisely correct -- this is mainly in the interests of brevity!)