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.

Solution 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.

Solution 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.

Solution 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.

Solution 4

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

View more solutions

Comments

[Keith Layne]

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.

[Faheem Mitha]

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

[Keith Layne]

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

[Faheem Mitha]

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

[Mooing Duck]

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

[Mateen Ulhaq]

@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.

[Faheem Mitha]

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

[Mooing Duck]

@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: stackoverflow.com/a/2794168/845092

[Faheem Mitha]

@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.

[Mooing Duck]

@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.

[Faheem Mitha]

@MooingDuck: Ok. Thanks for the clarification.

[Faheem Mitha]

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.

[Keith Layne]

@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.

[Faheem Mitha]

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

[Mooing Duck]

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

[Whitecat]

Can you explain this more

[Faheem Mitha]

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.

[Faheem Mitha]

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.

[Marius Renn]

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.

[Faheem Mitha]

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

[minexew]

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

[Paul Rooney]

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.

[Juicebox]

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.

[John Phu Nguyen]

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

[fire in the hole]

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