c++ - C++ 有有序哈希吗？

Question

Perl 有一个名为“有序散列” Tie::IxHash 的结构。可以将其用作哈希表/映射。条目按插入顺序排列。

想知道C++中有没有这样的东西。

这是一个示例 Perl 片段:

use Tie::IxHash;

tie %food_color, "Tie::IxHash";
$food_color{Banana} = "Yellow";
$food_color{Apple}  = "Green";
$food_color{Lemon}  = "Yellow";

print "In insertion order, the foods are:\n";
foreach $food (keys %food_color) {
    print "  $food\n"; #will print the entries in order
}

更新 1

正如@kerrek-sb 所指出的，可以使用 Boost 多索引容器库。只是想知道是否可以用 STL 来做。

Answer 1

是也不是。不，没有任何一款专门用于提供完全相同的功能。但是，是的，您可以通过几种不同的方式来做同样的事情。如果您希望主要按照插入的顺序访问数据，那么显而易见的方法是一个简单的对 vector :

std::vector<std::string, std::string> food_colors;

food_colors.push_back({"banana", "yellow"});
food_colors.push_back({"apple", "green"});
food_colors.push_back({"lemon", "yellow"});

for (auto const &f : food_colors)
    std::cout << f.first << ": " << f.second << "\n";

这通过简单地按顺序存储项目来保持顺序。如果您需要按键访问它们，您可以使用 std::find 对特定项目进行线性搜索。这最大限度地减少了使用的额外内存，但代价是如果您获得大量项目，则按键访问速度较慢。

如果您希望通过按键更快地访问大量项目，您可以使用 Boost MultiIndex。如果你真的想避免这种情况，你可以很容易地创建自己的索引。为此，您首先要将项目插入 std::unordered_map(或者可能是 std::map)。这可以通过键快速访问，但不能按插入顺序访问。但是，它确实会在每个项目插入 map 时返回一个迭代器。您可以简单地将这些迭代器存储到一个 vector 中，以便按插入顺序进行访问。虽然这个原理很简单，但是代码有点笨拙，说得好听一点:

std::map<std::string, std::string> fruit;
std::vector<std::map<std::string, std::string>::iterator> in_order;

in_order.push_back(fruit.insert(std::make_pair("banana", "yellow")).first);
in_order.push_back(fruit.insert(std::make_pair("apple", "green")).first);
in_order.push_back(fruit.insert(std::make_pair("lemon", "yellow")).first);

这允许通过 key 访问:

// ripen the apple:
fruit["apple"] = "red";

...或按插入顺序:

for (auto i : in_order)
    std::cout << i->first << ": " << i->second << "\n";

目前，我已经展示了执行此操作的基 native 制——如果您想经常使用它，您可能希望将其包装到一个不错的类中以隐藏一些丑陋之处并保留一些东西正常使用时漂亮干净。