从unordered_map获取键和值列表

Question

从unordered_map中获取键和值的列表（作为vector）最有效的方法是什么？

为了具体说明，假设所讨论的映射关系为unordered_map<string, double>。然后，我想将键作为vector<string>获取，并且将值作为vector<double>获取。

unordered_map<string, double> um;

vector<string> vs = um.enum_keys();
vector<double> vd = um.enum_values(); 

我可以遍历这个映射并收集结果，但有没有更高效的方法？最好有一种方法也适用于普通的映射，因为我可能会转换到普通的映射。

- Faheem Mitha

---

看了一下草案标准，我没有看到一个简单的方法来得到你想要的，但我可能漏掉了什么。你可以使用 std::vector<std::pair<const Key, Val>> v(map.begin(), map.end()); 这个语句，它应该会给你一个键值对的向量。 - Keith Layne

@muntoo：不确定编辑的意图。vector<string> vs = um.enum_keys();代表什么？ - Faheem Mitha

Boost有一个转换迭代器，可以仅提取键或仅提取值，但按照Keith的建议一次提取两者会更快。 - Mooing Duck

@FaheemMitha 只是让它“更好”。如果你不喜欢，可以删除它。enum_keys()不存在，但这就是你想要的“格式”，所以我想澄清一下。 - Mateen Ulhaq

@MooingDuck：你仍然可以添加一个答案，但无论如何。有趣的问题是这些花哨的方法是否比常规方法更快。我猜可以计时并找出答案。 - Faheem Mitha

Answer 1

好的，这是你想要的:

std::vector<Key> keys;
keys.reserve(map.size());
std::vector<Val> vals;
vals.reserve(map.size());

for(auto kv : map) {
    keys.push_back(kv.first);
    vals.push_back(kv.second);  
} 

效率可能可以提高，但就是这样了。然而你在操作两个容器，所以没有真正能够隐藏这个事实的STL魔法。

正如Louis所说，这对于STL的任何map或set容器都适用。

- Keith Layne

---

好的，所以我猜没有比迭代地遍历这个 map 更好的方式了。我不认识你正在使用的语法。(auto kv : map) 表示什么意思？我本来期望只是对 map 元素进行迭代（例如通过 for 循环）。 - Faheem Mitha

@FaheemMitha 这是新的C++11 for循环。它确切地做了它看起来要做的事情，并且与auto结合使用可以使事情变得更加整洁。auto可以避免您显式编写kv类型。有几种方法可以实现基本相同的功能，包括迭代器的for循环，带有lambda的for_each等。由于您提到了unordered_map，我假设您正在使用C++11。 - Keith Layne

我想我是，但我不太熟悉新标准。谢谢。 - Faheem Mitha

效率可以通过储备来提高，但没有什么比这更快或更容易了。 - Mooing Duck

为避免不必要的对pair（以及它们的结构体成员）进行拷贝，我建议在此处使用auto&而不是auto。但是，对于set容器来说这种方法行不通，因为它们的value_type不是std::pair<K, V>而是键值类型本身。 - Juicebox

你可以使用 std::vector<Key> keys(map.size()); 来代替 std::vector<Key> keys; keys.reserve(map.size());，另一个 vector 也是同理。 - fire in the hole

Answer 2

使用C++-14，您还可以执行以下操作（已编辑以包含完整源代码）：

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

typedef string Key;
typedef int Value;

auto key_selector = [](auto pair){return pair.first;};
auto value_selector = [](auto pair){return pair.second;};

int main(int argc, char** argv) {
  // Create a test map
  unordered_map<Key, Value> map;
  map["Eight"] = 8;
  map["Ten"] = 10;
  map["Eleven"] = 11;

  // Vectors to hold keys and values
  vector<Key> keys(map.size());
  vector<Value> values(map.size());

  // This is the crucial bit: Transform map to list of keys (or values)
  transform(map.begin(), map.end(), keys.begin(), key_selector);
  transform(map.begin(), map.end(), values.begin(), value_selector);

  // Make sure this worked: Print out vectors
  for (Key key : keys) cout << "Key: " << key << endl;
  for (Value value : values) cout << "Value: " << value << endl;

  return 0;
}

我用以下命令进行了编译：

g++ keyval.cpp -std=c++14 -o keyval

测试结果如预期一样打印了键和值。

- Marius Renn

---

你能写一个可以编译的自包含示例吗？另外，如果你能提到要使用的编译器并提供一个用于编译的命令行，那将非常有帮助。谢谢。 - Faheem Mitha

这在clang 3.5和gcc 4.9上可以工作。相对于普通循环，这有什么效率优势吗？ - Faheem Mitha

由于使用了lambda函数，可能不是非常高效，但作为一种函数式算法非常优雅。 - minexew

Lambda表达式不应该引入额外开销，它们（就像其他的函数对象一样）可以内联到transform循环中。但是当使用auto时，要记得它会推断值类型，因此那些基于范围的for循环会引入一些拷贝。在合适的情况下，你可以使用const auto&代替普通的auto。 - Paul Rooney

今天的编译器几乎肯定会内联λ，甚至不需要关键字。这样做不会影响性能。 - John Phu Nguyen

Answer 3

在STL中，没有内置的方法可以获取映射表中的所有键或值。

无序映射表和常规映射表的迭代没有区别，最好的方法是迭代并将键或值收集到向量中。

您可以编写一个模板函数来迭代任何类型的映射表。

- Louis

Answer 4

加入晚了，但我认为这可能对某些人有帮助。
两个模板函数利用key_type和mapped_type。

namespace mapExt
{
    template<typename myMap>
    std::vector<typename myMap::key_type> Keys(const myMap& m)
    {
        std::vector<typename myMap::key_type> r;
        r.reserve(m.size());
        for (const auto&kvp : m)
        {
            r.push_back(kvp.first);
        }
        return r;
    }

    template<typename myMap>
    std::vector<typename myMap::mapped_type> Values(const myMap& m)
    {
        std::vector<typename myMap::mapped_type> r;
        r.reserve(m.size());
        for (const auto&kvp : m)
        {
            r.push_back(kvp.second);
        }
        return r;
    }
}

使用方法：

std::map<long, char> mO;
std::unordered_map<long, char> mU;
// set up the maps
std::vector<long> kO = mapExt::Keys(mO);
std::vector<long> kU = mapExt::Keys(mU);
std::vector<char> vO = mapExt::Values(mO);
std::vector<char> vU = mapExt::Values(mU);

- elimad

Answer 5

我正在使用range-v3库，它很快也会出现在STL库中，如果有点运气的话，可能会在c++23中实现（ranges::to肯定会，views::key可能会）。

std::unordered_map<std::string, int> map {{"one", 1}, {"two", 2}, {"three", 3}};

auto keys = map | ranges::views::keys | ranges::to<std::vector>();

- Silver Zachara

Answer 6

类似于@Keith Layne的答案，但是储备在一行中完成； 而for循环使用引用（而不是通过值复制每个条目）并使其成为const。但如果可以使用C++14，则@Marius Renn的答案应该更好。

std::map<long, char> mO;

// populate the mO

std::vector<long> keys(mO.size());
std::vector<char> vals(mO.size());

for(const auto &kv : mO) {
    keys.push_back(kv.first);
    vals.push_back(kv.second);  
} 

- Anton Krug