Quick index search while maintaining insertion order in C ++

Question

I need a container that can quickly find over 1 million items and keep the insertion order.

So, at first I thought about std :: map, but he does not care about the insert order, which he orders the data according to the key. I found boost :: multi_index which should preserve the insertion order and quickly search for data through an indexed field (which is id (and not unique!) For my case). So I did something like this:

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 put data in a container without any problems. Suppose I insert 5 elements into my container, for example:

 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 that I search in the container for the element "1001" iterator++ returns "1002" , and iterator— returns "1000" . Thus, it seems that he does not care about the insertion order and orders the data according to the indexed value.

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

Am I doing something wrong? How can I achieve something like a quick index search and returning data according to the insertion order.

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

Answer 1

You were almost there with your attempt to boost::multi_index . The problem was that when you did a search using an ordered index, an iteration was also ordered. Fortunately, a multi-index provides a project mechanism for switching 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 multimap<Key,List<Item>::Iterator> paired with List<Item> . I would use a map to search, and List saved the elements in the order of placement. You will need to update both containers in all insert / update / delete scripts. If you can point out your use case, the best option may be available.

This option will give you a search in the log (n), but it will allow you to delete the time and index in constant time. This is similar to how I 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; } 

Exit

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

Answer 3

Yes, what Mark B. suggested is exactly true. I just wanted to present the correct syntax for possible future visitors.

I created typedef:

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

and syntax for finding data by id and changing the index by 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); // ***