C ++有排序哈希吗？ [英] Does C++ have ordered hash?

问题描述

Perl有一个叫做有序哈希的结构。 Tie :: IxHash 。可以使用它作为哈希表/地图。条目按插入的顺序。

Perl has a structure called "ordered hash" Tie::IxHash. One can use it as a hashtable/map. The entries are in the order of insertion.

想知道C ++中是否有这样的事情。

Wonder if there is such a thing in C++.

这里是一个Perl代码片段：

Here is a sample Perl snippet:

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

As @ kerrek-sb指出，可以使用Boost多索引容器库。只是想知道是否可能做到与STL。

As @kerrek-sb pointed out, one can use Boost Multi-index Containers Library. Just wonder if it is possible to do it with STL.

推荐答案

是和否。不，没有人专门提供完全相同的功能。但是，你可以用几种不同的方式做同样的事情。如果你希望主要以插入的顺序访问数据，那么明显的方法是一个简单的对的向量：

Yes and no. No, there's no one that that's specifically intended to provide precisely the same functionality. But yes, you can do the same in a couple of different ways. If you expect to access the data primarily in the order inserted, then the obvious way to go would be a simple vector of pairs:

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 对特定项目进行线性搜索。

This preserves order by simply storing the items in order. If you need to access them by key, you can use std::find to do a linear search for a particular item. That minimizes extra memory used, at the expense of slow access by key if you get a lot of items.

如果您希望通过键来快速访问大量项目，请使用键来减少访问速度。 ，您可以使用Boost MultiIndex。如果你真的想要避免，你可以很容易地创建自己的索引。要做到这一点，你可以开始将你的项目插入 std :: unordered_map （或者可能是 std :: map ）。这可以通过键快速访问，但不能以插入顺序访问。但是，它会在每个项目插入到地图中时向其返回迭代器。你可以简单地将这些迭代器存储到一个向量中，以按照插入顺序访问。虽然这个原则相当简单，代码有点笨拙的一面，很好地：

If you want faster access by key with a large number of items, you could use a Boost MultiIndex. If you really want to avoid that, you can create an index of your own pretty easily. To do this, you'd start by inserting your items into a std::unordered_map (or perhaps an std::map). This gives fast access by key, but no access in insertion order. It does, however, return an iterator to each items as it's inserted into the map. You can simply store those iterators into a vector to get access in the order of insertion. Although the principle of this is fairly simple, the code is a bit on the clumsy side, to put it nicely:

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

目前，我已经展示了这样做的基本机制 - 如果你想使用它很多，你可能想把它包装成一个漂亮的类来隐藏一些丑陋，保持东西在正常使用中漂亮干净。

For the moment, I've shown the basic mechanism for doing this--if you wanted to use it much, you'd probably want to wrap that up into a nice class to hide some of the ugliness and the keep things pretty and clean in normal use.

这篇关于C ++有排序哈希吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！