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);

Answer 2

I would use a multimap<Key,List<Item>::Iterator> paired with a List<Item>. I would use the map for lookup and the List would hold the items in insertion order. You will need to keep both containers up to date on all insertion/update/deletion scenarios. If you could expound on your use case a better option may be available.

This option would give you log(n) lookup while still allow constant time removal of the index and the item. This is similar to how I have implemented LRU caches in the past.

Edit due to question

typedef list<myData> DataLst;
typedef DataLst::iterator LstIter; 
typedef multimap<unsigned long, LstIter> mpType; 

mpType BuildIndex(DataLst &lst)
{
    mpType ret; 
    for (auto Item = begin(lst); Item != end(lst); Item++)
    {       
        ret.insert(make_pair(Item->id,Item));
    }
    return ret; 
}

int _tmain(int argc, _TCHAR* argv[])
{
    DataLst myDataContainer; 
    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));

    auto myMap = BuildIndex(myDataContainer);
    auto iter = myMap.find(1001);
    cout << "The iter insert  = " << iter->second->insertionOrder << endl;
    cout << "The iter insert after = " <<  std::next(iter->second)->insertionOrder << endl;
    cout << "The iter insert before = " << std::prev(iter->second)->insertionOrder << endl;
    string foo; 
    cin >> foo; 
}

output

The iter insert  = 2
The iter insert after = 3
The iter insert before = 1

Answer 3

Yeah, what Mark B offered is exactly correct. I just wanted to submit the right syntax for the benefit of possible future visitors.

I created a typedef:

typedef myDataContainerType::nth_index<1>::type myDataContainerType_by_id;

myDataContainerType myDataContainer;

and the syntax for finding the data according to id and changing index to insertion order:

myDataContainerType_by_id& idIndex = myContainer.get<1>();
myContainerType_by_id::iterator itId = idIndex.find(fId);

if (itId == idIndex.end())
    return 0;

myDataContainerType::const_iterator itInsertionOrder = myDataContainer.project<0>(itId);

// *** Alternative way to change index which works as well
myDataContainerType::const_iterator itInsertionOrder2 = myDataContainer.iterator_to(*itId);
// ***