一个跟踪插入顺序的std :: map？

Question

我目前有一个std::map<std::string,int>存储整数值到唯一字符串标识符,我确实查找字符串.它主要是我想要的,除了它不跟踪插入顺序.因此,当我迭代地图以打印出值时,它们将根据字符串进行排序; 但是我希望它们按照(第一次)插入的顺序排序.

我想过使用一个vector<pair<string,int>>替代,但我需要查找字符串并将整数值增加大约10,000,000次,所以我不知道是否std::vector会明显变慢.

有没有办法使用std::map或是否有std更适合我需要的容器？

[我在GCC 3.4上,我的价值可能不超过50对std::map].

谢谢.

Answer 1

如果你在std :: map中只有50个值,你可以在打印之前将它们复制到std :: vector,并使用适当的函子通过std :: sort进行排序.

或者你可以使用boost :: multi_index.它允许使用多个索引.在您的情况下,它可能如下所示:

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> >
    >
> values_t;

Answer 2

您可以将a std::vector与std::tr1::unordered_map(哈希表)组合在一起.这里有一个链接Boost的文档进行unordered_map.您可以使用向量来跟踪插入顺序和哈希表以进行频繁查找.如果您正在进行数十万次查找,则std::map哈希表的O(log n)查找和O(1)之间的差异可能很大.

std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}

Answer 3

保持平行list<string> insertionOrder.

在打印时,迭代列表并查找地图.

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map

Answer 4

Tessil有一个非常好的有序地图(和集)实现,这是MIT许可.你可以在这里找到它:ordered-map

地图示例

#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"

int main() {
tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}

Answer 5

您无法使用地图来做到这一点，但您可以使用两个单独的结构 - 地图和向量并保持它们同步 - 即当您从地图中删除时，找到并从向量中删除元素。或者您可以创建一个map<string, pair<int,int>>- 并在您的对中存储插入到记录位置时映射的 size() 以及 int 的值，然后在打印时使用位置成员进行排序。