How can I sort a map according to a property of it

问题:

I've created a map having a vector as below:

map<int,vector<int>> mymap;

How can I sort this map according to the n^th value of the vector contained by map?

回答1:

You can't. You can provide a custom comparator to make the underlying data get sorted another way than the default, but this only relates to keys, not values. If you have a requirement for your container's elements to exist in some specific, value-defined order, then you're using the wrong container.

You can switch to a set, and take advantage of the fact that there is no distinction there between "key" and "value", and hack the underlying sorting yourself:

template <std::size_t N>
struct MyComparator
{
   typedef std::pair<int, std::vector<int>> value_type;
   bool operator()(const value_type& lhs, const value_type& rhs)
   {
      return lhs.second.at(N) < rhs.second.at(N);
   }
};

/**
 * A set of (int, int{2,}) pairs, sorted by the 2nd element in
 * the 2nd item of each pair.
 */
std::set<std::pair<int, std::vector<int>>, MyComparator<1>> my_data;

int main()
{
    my_data.insert(std::make_pair(1, std::vector<int>{0,5,0,0}));
    my_data.insert(std::make_pair(2, std::vector<int>{0,2,0,0}));
    my_data.insert(std::make_pair(3, std::vector<int>{0,1,0,0}));
    my_data.insert(std::make_pair(4, std::vector<int>{0,9,0,0}));

    for (const auto& el : my_data)
        std::cout << el.first << ' ';
}

// Output: 3 2 1 4

(live demo)

However, if you still need to perform lookup on key as well, then you're really in trouble and need to rethink some things. You may need to duplicate your data or provide an indexing vector.

回答2:

map<int,vector<int>> mymap;

How can i sort this map according to the nth value of the vector contained by map?

That's only possible if you're prepared to use that n^th value as the integer key too, as in consistently assigning:

mymap[v[n - 1]] = v;

If you're doing that, you might consider a set<vector<int>>, which removes the redundant storage of that "key" element - you would then need to provide a custom comparison though....

If you envisage taking an existing populated map that doesn't have that ordering, then sorting its elements - that's totally impossible. You'll have to copy the elements out to another container, such as a set that's ordered on the n^th element, or a vector that you std::sort after populating.

回答3:

If I have understood correctly you can (build) add elements to the map the following way

std::vector<int> v = { 1, 2, 3 };
std::vector<int>::size_type n = 2;

mymap[v[n]] = v;

Here is an example

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <ctime>

int main() 
{
    std::srand( ( unsigned )time( 0 ) );
    const size_t N = 10;
    std::map<int, std::vector<int>> m;

    for ( size_t i = 0; i < N; i++ )
    {
        std::vector<int> v( N );
        std::generate( v.begin(), v.end(), []{ return std::rand() % N; } );
        m[v[0]] = v;
    }

    for ( auto &p : m )
    {
        for ( int x : p.second ) std::cout << x << ' ';
        std::cout << std::endl;
    }

    return 0;
}

The output is

0 1 7 8 1 2 9 0 0 9 
1 6 3 1 3 5 0 3 1 5 
3 8 0 0 0 7 1 2 9 7 
5 9 5 0 7 1 2 0 6 3 
6 4 7 5 4 0 0 4 2 0 
7 9 8 6 5 5 9 9 4 5 
8 3 8 0 5 9 6 6 8 3 
9 5 4 7 4 0 3 5 1 9 

Take into account that as there can be duplicated vectors (that is that have the same value of the n-th element (in my example n is equal to 0) then some vectors will not be added to the map. If you want to have duplicates then you should use for example std::multimap

Also you can build a new map according to the criteria based on an existent map.

回答4:

You can abuse the fact a c++ map uses a tree sorted by its keys. This means that you can either create a new map, with as keys the values you wish it to be sorted on, but you can also create a vector with references to the items in your map, and sort that vector (or the other way around: you could have a sorted vector, and use a map to create an index on your vector). Be sure to use a multimap in the case of duplicate keys.