C++有没有订购哈希？

Question

Perl有一个名为"ordered hash" 的结构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 Multi-index Containers Library.只是想知道是否可以用STL做到这一点.

Answer 1

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

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。如果您确实想避免这种情况，您可以很容易地创建自己的索引。为此，您首先将项目插入到 a std::unordered_map（或者可能是std::map）中。这可以通过按键进行快速访问，但不能按插入顺序进行访问。但是，当每个项目插入到映射中时，它确实会返回一个迭代器。您可以简单地将这些迭代器存储到向量中，以便按插入顺序进行访问。虽然原理很简单，但是代码有点笨拙，说得好听一点：

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

这允许通过密钥访问：

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

...或按插入顺序：

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

目前，我已经展示了执行此操作的基本机制 - 如果您想经常使用它，您可能希望将其包装到一个漂亮的类中以隐藏一些丑陋并保持事物漂亮和干净在正常使用情况下。