Container with two indexes (or a compound index)

Question

I have a class like this

class MyClass 
{
    int Identifier;
    int Context;
    int Data;
}

and I plan to store it in a STL container like

vector<MyClass> myVector;

but I will need to access it either by the extenal Index (using myVector[index]); and the combination of Identifier and Context which in this case I would perform a search with something like

vector<MyClass>::iterator myIt;
for( myIt = myVector.begin(); myIt != myVector.end(); myIt++ )
{
    if( ( myIt->Idenfifier == target_id ) &&
        ( myIt->Context == target_context ) )
        return *myIt; //or do something else...
}

Is there a better way to store or index the data?

Answer 1

Yes, but if you want speed, you'll need to sacrifice space. Store it in a collection (like an STL set) with the identifier/context as key, and simultaneously store it in a vector. Of course, you don't want two copies of the data itself, so store it in the set using a smart pointer (auto_ptr or variant) and store it in the vector using a dumb pointer.

Answer 2

We need to know your usage. Why do you need to be able to get them by index, and how often do you need to search the container for a specific element.

If you store it in an std::set, your search time with be O(ln n), but you cannot reference them by index.

If you use an std::vector, you can index them, but you have to use std::find to get a specific element, which will be O(n).

But if you need an index to pass it around to other things, you could use a pointer. That is, use a set for faster look-up, and pass pointers (not index's) to specific elements.

Answer 3

Boost::Multi-Index has this exact functionality if you can afford the boost dependency (header only). You would use a random_access index for the array-like index, and either hashed_unique, hashed_non_unique, ordered_unique, or ordered_non_unique (depending on your desired traits) with a functor that compares Identifier and Context together.