Fast search via index with keeping insertion order in C++

Question

I need a container which has ability to search over 1 million items pretty fast and keep the insertion order.

So first I thought about std::map but it doesn’t care about the insertion order it orders the data according to the key. An I found boost::multi_index which shall preserve the insertion order and search for the data fast via the indexed field (which is id (not unique!) for my case). So I did something like that:

struct myData
{
    unsigned long id;
    unsigned long insertionOrder;

    myData (){};
    myData (unsigned long id_,unsigned long insertionOrder_):id(id_), insertionOrder(insertionOrder _)){}
    ~ myData (){};
};


typedef multi_index_container<
    myData, 
        indexed_by<    
            random_access<>,  // keep insertion order
            ordered_non_unique< member< myData, unsigned long, & myData::id> >
        > 
> myDataContainerType;

I can push data into the container without any problem. Let’s say I insert 5 item to my container like:

myDataContainer.push_back(myData(1002, 1));
myDataContainer.push_back(myData(1001, 2));
myDataContainer.push_back(myData(1005, 3));
myDataContainer.push_back(myData(1003, 4));
myDataContainer.push_back(myData(1000, 5));

The problem is when I perform a search in my container for the item “1001” the iterator++ returns "1002" and the iterator— returns "1000". So it seems that it doesn’t care about the insertion order and orders the data according to the indexed value as well.

I expect results for the iterator++ : “1002” and for iterator-- : “1005”. I mean the data according to the insertion order.

Am i doing smth wrong? How can I achieve something like doing fast search via the index value and retreiving the data according to the insertion order.

I am working on Visual Studio 2008, Visual C++, Win 7 x64 computer.

Answer 1

You were almost there with your boost::multi_index attempt. The problem was that when you did the find using the ordered index, the iteration was also being ordered. Luckily the multi-index provides a project mechanism to switch between indexes. If I read the documentation correctly:

auto ordered_iter = myMap.find(1001);
auto iter = boost::multi_index::project<0>(ordered_iter);