1

是否保证当 hash_map/unordered_map 加载相同的项目时，它们在迭代时将具有相同的顺序？基本上我有一个从文件加载的哈希图，我会定期将有限数量的项目提供给例程，然后释放哈希图。消费完项目后，我将相同的文件重新加载到哈希图中，并希望在我上次停止的点之后获取下一批项目。我停止的点将由钥匙识别。

4

2 回答 2

2

从技术上讲，不，不能保证它们按任何特定顺序排列。

然而，在实践中，鉴于您使用确定性哈希函数，您想要做的应该没问题。

考虑

std::string name;
std::string value;

std::unordered_map <std::string, std::string> map1;
std::unordered_map <std::string, std::string> map2;

while (read_pair (name, value))
{
    map1[name] = value;
    map2[name] = value;
}

您可以合理地期望名称-值对以相同map1的map2顺序出现。

于 2012-11-29T09:29:16.247 回答
2

不，你不能安全地做到这一点。首先，标准并不能保证，但即使您忽略标准并查看实际实现，这也是一个坏主意。

大多数哈希表结构都不是历史独立的。即：哈希表的状态不仅取决于它包含什么项目，还取决于它们被插入的顺序。

这是一个具体的例子：

#include <unordered_map>
#include <string>
#include <iostream>

static const char* const NAMES[] = {
    "joe",
    "bob",
    "alexander",
    "warren",
    "paul",
    "michael",
    "george",
    "david",
    "peter"
};
static const int NAME_COUNT = sizeof(NAMES)/sizeof(NAMES[0]);

static void print_umap(const std::unordered_map<std::string, int>& m) {
    for (const auto& item : m) {
        std::cout << "  " << item.first << "\n";
    }
}

int main(void) {
    std::unordered_map<std::string, int> a;
    std::unordered_map<std::string, int> b;
    std::unordered_map<std::string, int> c;

    for (int i = 0; i < NAME_COUNT; ++i) {
        a[NAMES[i]] = 0;
        b[NAMES[NAME_COUNT - 1 - i]] = 0;
    }

    for (const auto& item : a) {
        c[item.first] = 0;
    }

    std::cout << "a:\n";
    print_umap(a);
    std::cout << "\n\nb:\n";
    print_umap(b);
    std::cout << "\n\nc:\n";
    print_umap(c);
    return 0;
}

当我使用clang和 C++ 标准库的libc++实现构建它时，我得到以下输出：

a:
  peter
  george
  michael
  david
  paul
  bob
  warren
  alexander
  joe


b:
  joe
  alexander
  bob
  warren
  david
  paul
  michael
  george
  peter


c:
  joe
  alexander
  warren
  bob
  paul
  david
  michael
  george
  peter

请注意，每种情况下的顺序都不同。这对于哈希表来说一点也不稀奇。

于 2012-11-29T10:00:50.430 回答