What is the fastest way of turning map (value,index) into vector (index,value) in C++?

Question

I have a map that I want to convert it to vector. But also I want to flip keys and values; and order them according to new keys. However it must be fast as it can be while it has around 300.000 element in it.

For better explenation:

Map:

a->5
b->3
c->4
d->2
e->6
f->1

Vector shold be like this->[f,d,b,c,a,e]

Is it possible with one loop?

Depends on your interpretation of 'one loop'.. Anyway: your keys and values are both integers, right? Because you show a b c which is a bit confusing. — stijn, Aug 26 '16 at 06:03
Search for `c++ map sort by value`, there are several questions and answer on this topic. — barak manos, Aug 26 '16 at 06:06
How do you want to handle duplicate integer values in the original map, or are they guaranteed unique? (In your example they become index of the vector.) — geipel, Aug 26 '16 at 06:07
have a look at it... http://stackoverflow.com/questions/19842035/stdmap-how-to-sort-by-value-then-by-key — Vishwadeep Singh, Aug 26 '16 at 06:11
Actually no sorting is needed. Since the map values are unique: -- Allocate the vector to the same size as the number of elements in map. -- Loop through map and insert by value. O(n) — geipel, Aug 26 '16 at 06:13
Just to be sure: do you want `std::map` -> `std::vector` sorted on `Point3D` which has a way of being sorted (according to distance to (0,0,0))? This can only be done in one loop if you don't consider `std::sort()` a loop, but then using `std::transform()` would mean using no loops. So my solution would be: copy keys to vector, sort by referencing the keys and comparing the values. — stefaanv, Aug 26 '16 at 07:38
Please [edit] your question to show [what you have tried so far](http://whathaveyoutried.com). You should include a [mcve] of the code that you are having problems with, then we can try to help with the specific problem. You should also read [ask]. — Toby Speight, Aug 26 '16 at 14:42

Frank Puffer · Answer 1 · 2016-08-26T07:16:37.683

Actually it's really simple. Assuming that the map values are strings, you can do this:

std::vector<std::string> myVector(myMap.size());
for (auto const& mapEntry : myMap) {
    myVector[mapEntry->second - 1] = mapEntry->first;
}

However there is no checking of the index values. You have to make sure that (when sorted) these are consecutive integers starting at 1. This is of course not guaranteed by the map itself. There could be duplicates or gaps.

Edit: Just noticed that in a comment you write that the values are points with three float coordinates. Then just replace the std::string in my code by your point type. I just want to add that using floating point values as map keys is often not a good idea because of possible rounding errors. But that has nothing to do with your question.

score 0 · Answer 2 · answered Jul 23 '19 at 02:00

Here is a solution(requires C++11).


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

    using std::string; 
    using std::map;
    using std::vector;

    int main()
    {
        map<char, int> m = {{'a',5},{'b',3},{'c',4},{'d',2},{'e',6},{'f',1}};
        vector<std::pair<char,int> > v{
        std::make_move_iterator(m.begin()), std::make_move_iterator(m.end())};

        std::sort(v.begin(), v.end(), 
            [](std::pair<char,int>& l, std::pair<char,int>& r) {
                return l.second < r.second;});
        vector<char> keys;    
        std::transform(v.begin(), v.end(), 
            std::back_inserter(keys), [](std::pair<char,int> & a){
                return a.first;});
        for(auto a : keys) {
            std::cout << a << std::endl;
        }
    }

You can also run it at here

What is the fastest way of turning map (value,index) into vector (index,value) in C++?

2 Answers2