0 
#include <iostream>
#include <hash_map>

using namespace stdext;
using namespace std;

class CompareStdString
{
public:
bool operator ()(const string & str1, const string & str2) const
    {
        return str1.compare(str2) < 0;
    }
};
int main()
{
    hash_map<string, int, hash_compare<string, CompareStdString> > Map;
    Map.insert(make_pair("one", 1));
    Map.insert(make_pair("two", 2));
    Map.insert(make_pair("three", 3));
    Map.insert(make_pair("four", 4));
    Map.insert(make_pair("five", 5));
    hash_map<string, int, hash_compare<string, CompareStdString> > :: iterator i;
    for (i = Map.begin(); i != Map.end(); ++i)
    {
        i -> first; // they are ordered as three, five, two, four, one
    }
    return 0;
}

我想使用 hash_map 将 std::string 作为键。但是当我插入下一对订单时，我会感到困惑。为什么订单与插入订单不匹配？我应该如何获得一二三四五的订单？

4

1 回答 1

0

为什么订单与插入订单不匹配？

这是因为stdext::hash_map（以及来自 C++11 的独立于平台的标准库版本std::unordered_map）不维护/保证其元素的任何合理顺序，甚至不保证插入顺序。这是因为它是一个散列容器，各个元素的位置基于它们的散列值和容器的大小。因此，您将无法使用这样的容器维护数据的合理顺序。

你可以用来保持你的元素在一个有保证的顺序是一个很好的旧的std::map。但这也不是按插入顺序对元素进行排序，而是按比较谓词引起的顺序（可以配置为尊重插入时间，但这很不直观，而且根本不那么容易）。

对于其他任何事情，您都不会自己滚动（或搜索其他库，不知道 boost 是否有类似的东西）。例如，将所有元素添加到线性std::vector/std::list以进行插入顺序迭代，并在必要时维护指向该向量/列表的附加std::(unordered_)map指向以进行 O(1)/O(log n) 检索。

于 2013-07-08T14:27:39.493 回答