Fast search via index with keeping insertion order in C++
boost, boost-multi-index, c++, containers, search
Solution
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);
Problem
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.