c++ - 通过索引快速搜索并保持 C++ 中的插入顺序

Question

我需要一个能够快速搜索超过 100 万个项目并保持插入顺序的容器。

所以首先我想到了 std::map 但它不关心插入顺序它根据键对数据进行排序。我发现 boost::multi_index 将保留插入顺序并通过索引字段快速搜索数据(对于我的情况是 id(不是唯一的!))。所以我做了类似的事情:

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;

我可以毫无问题地将数据推送到容器中。假设我向容器中插入 5 个项目，例如:

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

问题是当我在我的容器中搜索项目 “1001” 时，iterator++ 返回 "1002" 并且 iterator— 返回 "1000"。所以看起来它并不关心插入顺序，而是根据索引值对数据进行排序。

我期望 iterator++ 的结果:“1002” 和 iterator-- 的结果:“1005” .我的意思是根据插入顺序的数据。

我做错了吗？我怎样才能实现像通过索引值进行快速搜索并根据插入顺序检索数据这样的事情。

我正在使用 Visual Studio 2008、Visual C++、Win 7 x64 计算机。

Answer 1

您的boost::multi_index 尝试就快完成了。问题是，当您使用有序索引进行查找时，迭代也被排序。幸运的是，多索引提供了一个 project 机制来在索引之间切换。如果我正确阅读文档:

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