当前位置： 文江博客 话题详情

如何按值对 STL 映射进行排序？

发布于 2024-08-30 00:27:08 字数 312 浏览 4 评论 0 原文

如何实现STL映射按值排序？

例如，我有一个地图 m：

map<int, int> m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

我想按 m 的值对该地图进行排序。因此，如果我打印地图，我希望得到如下结果：

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

如何以这种方式对地图进行排序？有什么方法可以处理带有排序值的键和值吗？

原文

How can I implement STL map sorting by value?

For example, I have a map m:

map<int, int> m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

I'd like to sort that map by m's value. So, if I print the map, I'd like to get the result as follows:

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

How can I sort the map in this way? Is there any way that I can deal with the key and value with sorted values?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（12）

(り薆情海 2024-09-06 00:27:08

将所有键值对转储到 set 中> 首先，其中 set 是用一个小于函子构造的，该函子仅比较该对的第二个值。这样，即使您的值并不完全不同，您的代码仍然可以工作。

或者将键值对转储到向量中。 >，然后使用相同的小于函子对该向量进行排序。

Dump out all the key-value pairs into a set<pair<K, V> > first, where the set is constructed with a less-than functor that compares the pair's second value only. That way, your code still works even if your values aren't all distinct.

Or dump the key-value pairs into a vector<pair<K, V> >, then sort that vector with the same less-than functor afterwards.

回复 原文
荆棘i 2024-09-06 00:27:08

您可以构建第二个映射，将第一个映射的值作为键，将第一个映射的键作为值。

仅当所有值都不同时，此方法才有效。如果您不能假设这一点，那么您需要构建多重地图而不是地图。

You can build a second map, with the first map's values as keys and the first map's keys as values.

This works only if all values are distinct. If you cannot assume this, then you need to build a multimap instead of a map.

回复 原文
伴梦长久 2024-09-06 00:27:08

我想知道如何实现STL映射按值排序。

根据定义，你不能。映射是一种按键对其元素进行排序的数据结构。

I wonder how can I implement the STL map sorting by value.

You can’t, by definition. A map is a data structure that sorts its element by key.

回复 原文
呆橘 2024-09-06 00:27:08

您应该使用 Boost.Bimap对于这种事情。

You should use Boost.Bimap for this sort of thing.

回复 原文
酒儿 2024-09-06 00:27:08

基于@swegi的想法，我使用 c++11 实现了一个解决方案a multimap:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
multimap<int, int> mm;

for(auto const &kv : m)
    mm.insert(make_pair(kv.second, kv.first));  // Flip the pairs.

for(auto const &kv : mm)
    cout << "m[" << kv.second << "] = " << kv.first << endl;  // Flip the pairs again.

Ideone 上的代码

我还实现了一个基于 C++11 的解决方案@Chris 的想法是使用成对的向量。为了正确排序，我提供了 lambda 表达式 作为比较函子：

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
using mypair = pair<int, int>;

vector<mypair> v(begin(m), end(m));

sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; });

for(auto const &p : v)
    cout << "m[" << p.first << "] = " << p.second << endl;

Ideone 上的代码

第一个解决方案更加紧凑，但两种解决方案应该具有大致相同的性能。插入到 multimap 的时间复杂度为 O(log n)，但必须对 n 个条目执行此操作，导致 O( n log n)。对第二个解决方案中的向量进行排序也会导致 O(n log n)。

我还尝试了@Chris关于使用一组对的想法。但是，如果值不完全不同，则该方法将不起作用。使用仅比较该对的第二个元素的函子没有帮助。如果您首先将 make_pair(1, 1) 插入集合中，然后尝试插入 make_pair(2, 1)，则不会插入第二对，因为该组将这两对视为相同。您可以在 Ideone 上看到该效果。

Based on @swegi's idea, I implemented a solution in c++11 using a multimap:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
multimap<int, int> mm;

for(auto const &kv : m)
    mm.insert(make_pair(kv.second, kv.first));  // Flip the pairs.

for(auto const &kv : mm)
    cout << "m[" << kv.second << "] = " << kv.first << endl;  // Flip the pairs again.

Code on Ideone

I also implemented a C++11 solution based on @Chris' idea using a vector of pairs. For correct sorting, I provide a lambda expression as comparison functor:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
using mypair = pair<int, int>;

vector<mypair> v(begin(m), end(m));

sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; });

for(auto const &p : v)
    cout << "m[" << p.first << "] = " << p.second << endl;

Code on Ideone

The first solution is more compact, but both solutions should have roughly the same performance. Inserting into a multimap is of O(log n), but this has to be done for n entries, resulting in O(n log n). Sorting the vector in the second solution also results in O(n log n).

I also gave a try to @Chris' idea on using a set of pairs. However, it won't work if the values aren't all distinct. Using a functor that compares only the pair's second element doesn't help. If you first insert make_pair(1, 1) into the set and then try to insert make_pair(2, 1), then the second pair won't be inserted, because both pairs are seen as identical by that set. You can see that effect here on Ideone.

回复 原文
如果没结果 2024-09-06 00:27:08

我刚刚在我的 C++ 书中做了一个类似的问题。我想出的答案可能不是很有效：

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s)
        ++counters[s];

    //Get the largest and smallest values from map
    int beginPos = smallest_map_value(counters);
    int endPos = largest_map_value(counters);

    //Increment through smallest value to largest values found
    for(int i = beginPos; i <= endPos; ++i)
    {
        //For each increment, go through the map...
        for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)
        {
            //...and print out any pairs with matching values
            if(it->second == i)
            {
                cout << it->first << "\t" << it->second << endl;
            }
        }
    }
    return 0;
}

//Find the smallest value for a map<string, int>
int smallest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int lowest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second < lowest)
            lowest = it->second;
    }
    return lowest;
}

//Find the largest value for a map<string, int>
int largest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int highest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second > highest)
            highest = it->second;
    }
    return highest;
}

I've just done a similar question in my c++ book. The answer I came up with might not be very efficient though:

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s)
        ++counters[s];

    //Get the largest and smallest values from map
    int beginPos = smallest_map_value(counters);
    int endPos = largest_map_value(counters);

    //Increment through smallest value to largest values found
    for(int i = beginPos; i <= endPos; ++i)
    {
        //For each increment, go through the map...
        for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)
        {
            //...and print out any pairs with matching values
            if(it->second == i)
            {
                cout << it->first << "\t" << it->second << endl;
            }
        }
    }
    return 0;
}

//Find the smallest value for a map<string, int>
int smallest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int lowest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second < lowest)
            lowest = it->second;
    }
    return lowest;
}

//Find the largest value for a map<string, int>
int largest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int highest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second > highest)
            highest = it->second;
    }
    return highest;
}
回复 原文
日暮斜阳 2024-09-06 00:27:08

创建另一个映射，根据值而不是键提供 less() 函数，并且如果 value1 <= value2 （不严格是 < ），则该函数应返回 true。在这种情况下，也可以对具有非不同值的元素进行排序。

Create another map, provide a less() function based on the value not key, AND the function should return true if the value1 <= value2 (not strictly < ). In this case, elements with non-distinct values can be sorted as well.

回复 原文
神魇的王 2024-09-06 00:27:08

我在 thispointer 中找到了这个。该示例对 std::map< 进行排序std::string,int>由所有 int 值组成。

#include <map>
#include <set>
#include <algorithm>
#include <functional>

int main() {

    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 13 } };

    // Declaring the type of Predicate that accepts 2 pairs and return a bool
    typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;

    // Defining a lambda function to compare two pairs. It will compare two pairs using second field
    Comparator compFunctor =
            [](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
            {
                return elem1.second < elem2.second;
            };

    // Declaring a set that will store the pairs using above comparision logic
    std::set<std::pair<std::string, int>, Comparator> setOfWords(
            mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

    // Iterate over a set using range base for loop
    // It will display the items in sorted order of values
    for (std::pair<std::string, int> element : setOfWords)
        std::cout << element.first << " :: " << element.second << std::endl;

    return 0;
}

I have found this in thispointer. The example sorts a std::map< std::string,int> by all the int values.

#include <map>
#include <set>
#include <algorithm>
#include <functional>

int main() {

    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 13 } };

    // Declaring the type of Predicate that accepts 2 pairs and return a bool
    typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;

    // Defining a lambda function to compare two pairs. It will compare two pairs using second field
    Comparator compFunctor =
            [](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
            {
                return elem1.second < elem2.second;
            };

    // Declaring a set that will store the pairs using above comparision logic
    std::set<std::pair<std::string, int>, Comparator> setOfWords(
            mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

    // Iterate over a set using range base for loop
    // It will display the items in sorted order of values
    for (std::pair<std::string, int> element : setOfWords)
        std::cout << element.first << " :: " << element.second << std::endl;

    return 0;
}
回复 原文
最舍不得你 2024-09-06 00:27:08

在某些情况下可以做的一件事是使用 vector> 而不是使用 maps。这样你就失去了使用map的好处，例如更少的查找时间，但你可以直接使用带有向量>>的比较器函数

bool compare(pair<int, int> a, pair<int, int> b)
{
    return (a.second < b.second);
}

One thing that could be done in some scenarios, is using a vector<pair<int, int>> rather than using maps<int, int>. In this way you lose the benefits of using map, such as the less lookup time but you can directly use comparator function with vector<pair<int, int>>

bool compare(pair<int, int> a, pair<int, int> b)
{
    return (a.second < b.second);
}
回复 原文
长梦不多时 2024-09-06 00:27:08

地图已经根据第一个键进行排序，如果您想根据第二个值对其进行排序，请将第二个值作为键。其他人使用另一个容器，如向量>。

map is already sorded based on the first key, if you want to sort it based on the second value make second value as key. otherwies use another container like vector<pair<int,int>>.

回复 原文
夏花。依旧 2024-09-06 00:27:08

最近不得不做这个。我最终使用了指针...

快速基准测试结果

#include <iostream>
#include <type_traits>
#include <algorithm>
#include <map>
#include <vector>

using map_t = std::map<int,int>;
const map_t m
{
    { 5, 20 },
    { -18, 28 },
    { 24, 49 },
    { 17, 27 },
    { 23, 46 },
    { 8, 16 },
    { -13, 11 },
    { -22, 32 },
    { 12, 45 },
    { -2, 19 },
    { 21, 11 },
    { -12, 25 },
    { -20, 8 },
    { 0, 29 },
    { -5, 20 },
    { 13, 26 },
    { 1, 27 },
    { -14, 3 },
    { 19, 47 },
    { -15, 17 },
    { 16, 1 },
    { -17, 50 },
    { -6, 40 },
    { 15, 24 },
    { 9, 10 }
};

template<typename T>
void sort_values_using_vector(T const& m)
{
    using map_t = T;

    using sort_t = std::vector<std::pair<typename map_t::key_type,
        typename map_t::mapped_type>>;
    sort_t sorted{ m.begin(), m.end() };
    
    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs.second < rhs.second;
        });
}

template<typename T>
void sort_values_using_multimap(T const& m)
{
    using map_t = T;

    using sort_t = std::multimap<typename map_t::mapped_type,
        typename map_t::key_type>;
    sort_t sorted;

    for (auto const& kv : m)
    {
        sorted.insert(std::make_pair(kv.second, kv.first));
    }
}

template<typename T>
void sort_values_using_ptrs(T const& m)
{
    using map_t = T;

    using ptr_t = std::add_pointer_t
        <std::add_const_t<typename map_t::value_type>>;
    using sort_t = std::vector<ptr_t>;
    sort_t sorted;
    sorted.reserve(m.size());

    for (auto const& kv : m)
    {
        sorted.push_back(std::addressof(kv));
    }

    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs->second < rhs->second;
        });
}

template<typename T>
void sort_values_using_refs(T const& m)
{
    using map_t = T;

    using ref_t = std::reference_wrapper
        <std::add_const_t<typename map_t::value_type>>;
    using sort_t = std::vector<ref_t>;
    sort_t sorted{ m.begin(), m.end() };

    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs.get().second < rhs.get().second;
        });
}

static void copy_to_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_vector(m);
  }
}
BENCHMARK(copy_to_vector);

static void copy_flipped_to_multimap(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_multimap(m);
  }
}
BENCHMARK(copy_flipped_to_multimap);

static void copy_ptrs_to_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_ptrs(m);
  }
}
BENCHMARK(copy_ptrs_to_vector);

static void use_refs_in_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_refs(m);
  }
}
BENCHMARK(use_refs_in_vector);

Recently had to do this. I ended up using pointers...

Quick Benchmark Results

#include <iostream>
#include <type_traits>
#include <algorithm>
#include <map>
#include <vector>

using map_t = std::map<int,int>;
const map_t m
{
    { 5, 20 },
    { -18, 28 },
    { 24, 49 },
    { 17, 27 },
    { 23, 46 },
    { 8, 16 },
    { -13, 11 },
    { -22, 32 },
    { 12, 45 },
    { -2, 19 },
    { 21, 11 },
    { -12, 25 },
    { -20, 8 },
    { 0, 29 },
    { -5, 20 },
    { 13, 26 },
    { 1, 27 },
    { -14, 3 },
    { 19, 47 },
    { -15, 17 },
    { 16, 1 },
    { -17, 50 },
    { -6, 40 },
    { 15, 24 },
    { 9, 10 }
};

template<typename T>
void sort_values_using_vector(T const& m)
{
    using map_t = T;

    using sort_t = std::vector<std::pair<typename map_t::key_type,
        typename map_t::mapped_type>>;
    sort_t sorted{ m.begin(), m.end() };
    
    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs.second < rhs.second;
        });
}

template<typename T>
void sort_values_using_multimap(T const& m)
{
    using map_t = T;

    using sort_t = std::multimap<typename map_t::mapped_type,
        typename map_t::key_type>;
    sort_t sorted;

    for (auto const& kv : m)
    {
        sorted.insert(std::make_pair(kv.second, kv.first));
    }
}

template<typename T>
void sort_values_using_ptrs(T const& m)
{
    using map_t = T;

    using ptr_t = std::add_pointer_t
        <std::add_const_t<typename map_t::value_type>>;
    using sort_t = std::vector<ptr_t>;
    sort_t sorted;
    sorted.reserve(m.size());

    for (auto const& kv : m)
    {
        sorted.push_back(std::addressof(kv));
    }

    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs->second < rhs->second;
        });
}

template<typename T>
void sort_values_using_refs(T const& m)
{
    using map_t = T;

    using ref_t = std::reference_wrapper
        <std::add_const_t<typename map_t::value_type>>;
    using sort_t = std::vector<ref_t>;
    sort_t sorted{ m.begin(), m.end() };

    std::sort(sorted.begin(), sorted.end(),
        [](auto const& lhs, auto const& rhs)
        {
            return lhs.get().second < rhs.get().second;
        });
}

static void copy_to_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_vector(m);
  }
}
BENCHMARK(copy_to_vector);

static void copy_flipped_to_multimap(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_multimap(m);
  }
}
BENCHMARK(copy_flipped_to_multimap);

static void copy_ptrs_to_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_ptrs(m);
  }
}
BENCHMARK(copy_ptrs_to_vector);

static void use_refs_in_vector(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    sort_values_using_refs(m);
  }
}
BENCHMARK(use_refs_in_vector);
回复 原文
雄赳赳气昂昂 2024-09-06 00:27:08

此代码使用自定义排序函数按值对地图进行排序

// Comparator function to sort pairs
// according to value
bool comp(pair<int, int>& a,
        pair<int, int>& b)
{
    return a.second < b.second;
}

// Function to sort the map according
// to value in a (key-value) pair
void customSort(map<int, int>& m)
{

    vector<pair<int, int>> a;

    for(auto x:m)
        a.push_back(make_pair(x.first,x.second));

    sort(a.begin(), a.end(), comp);

    for (auto x:a) {
        cout << x.first<<" "<<x.second<<endl;
    }
}

This code uses custom sorting function to sort map by values

// Comparator function to sort pairs
// according to value
bool comp(pair<int, int>& a,
        pair<int, int>& b)
{
    return a.second < b.second;
}

// Function to sort the map according
// to value in a (key-value) pair
void customSort(map<int, int>& m)
{

    vector<pair<int, int>> a;

    for(auto x:m)
        a.push_back(make_pair(x.first,x.second));

    sort(a.begin(), a.end(), comp);

    for (auto x:a) {
        cout << x.first<<" "<<x.second<<endl;
    }
}
回复 原文
~没有更多了~

关于作者

西瑶

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

qq_otekVRB4

文章 0 评论 0

阿杰

文章 0 评论 0

姐不稀罕

文章 0 评论 0

qq_pphr7

文章 0 评论 0

━╋う一瞬間旳綻放

文章 0 评论 0

贺

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文