我能通过整数索引访问C++ std::map中的元素吗？

Question

我有一个元素的映射表，我想要遍历这个映射表。当然，标准的方法是使用for循环。

for (map<string, int> iterator it = myMap.begin(); it != myMap.end(); ++it) {
    string thisKey = it->first;
    int thisValue = it->second;
}

但是，如果我尝试使用 OpenMP 的 parallel for 构造使这个循环并行运行，它就不起作用，并且这是（显然）一个已知的问题，因为它不识别这种类型的循环构造。

因此，我的备选方案是使用整数索引迭代器，并通过索引访问键和值列表，就像在 C# 中所做的那样：

for (int i = 0; i < myMap.Count; ++i) {
    string thisKey = myMap.Keys[i];
    string thisValue = myMap.Values[i];
}

...但我似乎找不到C++中对应的方法。在C++中有没有我不知道的方法可以实现这个？

- Charles

---

您确定std::map是实现您想要的功能的最佳容器吗？ - AJG85

遍历一个映射就像是遍历一棵树，这不是一个简单的操作。即使你能按照自己想要的方式进行索引，也不能实现并行化。 - Mark Ransom

你的地图里有多少对？ - jk.

马克：谢谢，这基本上回答了我的问题。我认为我的当前解决方案（遍历树并将结果复制到向量中，然后遍历向量）可能是最好的方法。JK：对于这个特定的应用程序，99991。 - Charles

Answer 1

我对OpenMP一无所知，因此不知道它是否能优化以下内容。但是你可以使用std::advance，像这样：

#include <map>
#include <string>
#include <iterator>
#include <iostream>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  for(int i = 0; i < m.size(); ++i) {
    Map::iterator it = m.begin();
    std::advance(it, i);
    std::string thiskey = it->first;
    int thisValue = it->second;
    std::cout << thiskey << "\n";
  }
}

但请注意，std::advance 的时间复杂度为 O(n)，因此您（单线程）的复杂度为 O(n^2)。

---

编辑：如果您将映射元素复制到向量中，请意识到您可以在一个声明中完成：

std::vector<Map::value_type> v(m.begin(), m.end());

因此：

#include <map>
#include <string>
#include <iterator>
#include <iostream>
#include <vector>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  int i = 0;
  for( std::vector<Map::value_type> v(m.begin(), m.end());
    i < v.size(); ++i) {
    std::string thiskey = v[i].first;
    int thisValue = v[i].second;
    std::cout << thiskey << "\n";
  }
}

- Robᵩ

---

我实际上尝试过那个方法...它非常慢。我几乎失去了通过多线程运行它所获得的所有时间，而且我有24个线程在运行。我目前的解决方案是声明一个vector<string>和一个vector<int>，调整它们的大小，并将数据倾倒到向量中，然后以这种方式访问它们...它增加了很少的开销，但似乎很笨拙。 - Charles

最好保留一个 map::value_type 的单一向量。请参考我的编辑。（嗯，但这样不会为初始内存预留足够的空间。） - Robᵩ

Answer 2

以下是几个相对不太痛苦的选项：

1. 保留一个 `std::vector` 或 `std::deque` 以进行数组访问，并保留一个单独的值映射表。确保它们一致的工作是你的问题。 2. 使用 boost::multi_index 确保两个索引结构之间的一致性。需要注意的是，使用此选项编译时间相当长。如果选择这种方式，请考虑使用 pimpl 模式。 3. 我没有使用 OpenMP 的经验，所以无法推测这些选项在实践中是否值得。

- Tom Kerr