Obtaining list of keys and values from unordered_map

Question

What is the most efficient way of obtaining lists (as a vector) of the keys and values from an unordered_map?

For concreteness, suppose the map in question is a unordered_map<string, double>. I'd then like to obtain the keys as a vector<string>, and the values as a vector<double>.

unordered_map<string, double> um;

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

I can just iterate across the map and collect the result, but is there a more efficient method? It would be nice to have a method that also works for regular map, since I might switch to that.

Creative

Looking at the draft standard, I don't see an easy way to get what you want, but I may be missing something. You could say std::vector<std::pair<const Key, Val>> v(map.begin(), map.end()); which should give you a vector of key-value pairs. – Raymond

@keith.layne: I'm looking for separate vectors for keys and values. – Creative

As I said, there's nothing built-in for that. See below. – Raymond

@muntoo: Not sure what is with the edit. What is vector<string> vs = um.enum_keys(); supposed to signify? – Creative

Boost has a transform iterator which can pull just keys or just values, but its faster to do both at once as Keith suggests – Footway

@FaheemMitha Just making it 'better'. If you don't like it, you can remove it. enum_keys() doesn't exist, but that is the 'format' you want it in, so I thought I'd clarify. – Ml

@MooingDuck: Feel free to add a answer using transform. I think it would be useful in cases when someone just wants one of these. – Creative

@FaheemMitha: It turns out to not be a good answer to your particular situation since you want both, but it's described and shown in other questions: https://mcmap.net/q/92867/-how-to-retrieve-all-keys-or-values-from-a-std-map-and-put-them-into-a-vector – Footway

@MooingDuck: You could still add an answer, but whatever. The interesting question is whether these fancy methods are faster than the regular ones. I guess one could time them and find out. – Creative

@FaheemMitha: The boost answer isn't faster than keith.layne's answer. It's mostly useful if you want to return an iterator to just keys, or just values for a iter<key> get_keys() function. – Footway

Answer 1

Okay, here you go:

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);  
} 

Efficiency can probably be improved, but there it is. You're operating on two containers though, so there's not really any STL magic that can hide that fact.

As Louis said, this will work for any of the STL map or set containers.

Raymond

Ok, sO I guess there is nothing better than iterating over the map then. I don't recognize the syntax you are using. What does (auto kv : map) denote. I would have expected just an iteration (i.e. for loop) over the elements of the map. – Creative

@FaheemMitha That is the new C++11 for loop. It does exactly what it looks like it does, and combined with auto makes things a little more tidy. auto saves you from having to explicitly write the type of kv. There are several ways to accomplish essentially the same thing including a for loop over the iterators, for_each with a lambda, etc. Since you mentioned unordered_map I assumed you were using C++11. – Raymond

I guess I am, but I'm not really familar with the new standard. Thanks. – Creative

Effienency can be improved with a reserve, but not much will be faster or easier than this. – Footway

I would use auto& instead of auto here to avoid unnecessary copies of the pair (and underlying first/second members if they are structs). And it won't work for set containers because their value_type is not a std::pair<K, V> but the Key/Val type itself. – Julienne

instead of std::vector<Key> keys; keys.reserve(map.size()); you can write std::vector<Key> keys(map.size()); same with the other vector – Christensen

@fireinthehole No, vector<T> v(n); creates a vector with n default-constructed elements, which is incorrect here: after all the push_back()s, you would end up with 2n elements in total. By contrast vector<T> v; v.reserve(n); creates a vector with 0 elements but a reserved capacity of n. – Romaineromains

Answer 2

Using C++-14 you could also do the following (edited to contain full source):

#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;
}

I compiled this with the following command:

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

Testing it printed the keys and values as expected.

Phatic

Can you explain this more – Charge

Could you write a self-contained example that can be compiled? Also, if you could mention what compiler to use and provide a command line to use to compile it, that would be helpful. thanks. – Creative

Also, what are Key and Value and um here? You haven't defined them. Perhaps you are using the definition from the question, namely "unordered_map<string, double> um;", but in that case, you should mention that here again, regardless. – Creative

Sorry folks, was on the bus when I wrote this and stayed rather brief. I now updated the code to something that should compile. Let me know if it does not work. The way this works is that we apply a lambda function to each element of the map (which is a key-value pair). The key-selector simply returns the first element of the pair, while the value selector returns the second. We use the transform function to copy the keys (or values) to the vectors. I am not an expert in std library's algorithms so there may be a more elegant way. – Phatic

Works here with clang 3.5 and gcc 4.9. Has this any efficiency advantages relative to a plain loop? – Creative

Probably not very efficient due to use of a lambda function, but very elegant as a functional algorithm. – Aerotherapeutics

The lambas should introduce no overhead they (like any other functors) can be inlined into the transform loop. But when using auto be sure to remember it deduces value types, so those range based for loops introduce some copies. You can use const auto& instead of plain auto, where it makes sense to. – Ombre

Today's compilers will almost certainly inline the lambda without even requiring the keyword. There will be no performance hit. – Ironclad

Answer 3

In STL there is no built-in method to get all keys or values from a map.

There is no different to iterate a unordered map or regular map, the best way is to iterate it and collect key or value to a vector.

You can write a template function to iterate any kind of map.

Prosenchyma

Answer 4

I'm using this with the range-v3 library, it will also be in the STL library soon, with a little luck in c++23 (ranges::to definitely and views::key maybe).

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

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

Vigen

Answer 5

Joining late, but thought this might be helpful to someone.
Two template functions making use of key_type and 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;
    }
}

Usage:

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

Tisman

Answer 6

Similar to @Keith Layne answer, but the reserve is done in one line; and the for loop uses const reference (instead of copying each entry by value). However, if C++14 can be used then @Marius Renn answer should be better.

std::map<long, char> mO;

// populate the mO's keys and values
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);  
} 

Fab