map中的元素按照key,value值排序

时间：2022-06-07 19:18:04

C++ STL中Map的按Key排序

其实，为了实现快速查找，map内部本身就是按序存储的（比如红黑树）。在我们插入<key, value>键值对时，就会按照key的大小顺序进行存储。这也是作为key的类型必须能够进行<运算比较的原因。现在我们用string类型作为key，因此，我们的存储就是按学生姓名的字典排序储存的。

<span style="font-size:18px;">#include<map>  
#include<string>  
#include<iostream>  
using namespace std;  

typedef pair<string, int> PAIR;  

ostream& operator<<(ostream& out, const PAIR& p) {  
  return out << p.first << "\t" << p.second;  
}  

int main() {  
  map<string, int> name_score_map;  
  name_score_map["LiMin"] = 90;   
  name_score_map["ZiLinMi"] = 79;   
  name_score_map["BoB"] = 92;   
  name_score_map.insert(make_pair("Bing",99));  
  name_score_map.insert(make_pair("Albert",86));  
  for (map<string, int>::iterator iter = name_score_map.begin();  
       iter != name_score_map.end();  
       ++iter) {  
    cout << *iter << endl;  
  }  
  return 0;  
 }  </span>
map中的元素按照key,value值排序
map的定义如下： 

<span style="font-size:18px;">template < class Key, class T, class Compare = less<Key>,  
           class Allocator = allocator<pair<const Key,T> > > class map;  </span>
 less是stl里面的一个函数对象，function object，也叫作仿函数，其实现如下： 

<span style="font-size:18px;">template <class T> struct less : binary_function <T,T,bool> {  
  bool operator() (const T& x, const T& y) const  
    {return x<y;}  
};  </span>
我们可以在定义map的时候，指定它的第三个参数Compare，比如我们把默认的less指定为greater，程序就会按照字典序升序输出，

当然我们也可以自己定义排序规则，只需要定义一个仿函数就可以，如下：

<span style="font-size:18px;">struct CmpByKeyLength {  
  bool operator()(const string& k1, const string& k2) {  
    return k1.length() < k2.length();  
  }  
};  </span>

C++ STL中Map的按Value排序

网上说的一些方法看似可行但实际有问题，使用lambda表达式，函数对象，都没有办法达到想要的结果。会报一些奇怪的错误，目前只有一下几个是可行的。

方法1. 将map中的key和value分别存放在一个pair类型的vector中，然后利用vector的sort函数排序，其中map_verb存放我的map值
方法2. 再新建一个map结构，然后把已知的map值得key和value分别作为新map的value和key，这样map结构就会自动按照value值排序


对于leetcode上的一道算法题Top K Frequent Elements，使用如下方法求解：

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

<span style="font-size:18px;">class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> cnt;
        for(int i = 0; i < nums.size(); ++i)
        {
            cnt[nums[i]]++;
        }

        vector<int> vec;
        map<int, vector<int>, greater<int>> cnt_res;
        for(map<int,int>::iterator iter = cnt.begin(); iter != cnt.end(); ++iter)
        {
            cnt_res[iter->second].push_back(iter->first);
        }

        int temp = 0;

        //sort(cnt_res.begin(), cnt_res.end(), [](pair<int, vector<int>> i, pair<int, vector<int>> j){return i.first < j.first;});
        map<int, vector<int>>::iterator iter = cnt_res.begin();
        while(temp < k)
        {
            for(int i = 0; i < iter->second.size(); ++i)
            {
                vec.push_back(iter->second[i]);
                ++temp;
                if(temp == k)
                {
                    break;
                }
            }
            ++iter;
        }
        return vec;
    }
};</span>

这里正是运用了第二种方法，新建了一个map，将key，value的类型互换，使得元素自动排序的时候使用降序排序。

顺便写一下lambda表达式的用法，

C++11 的 lambda 表达式规范如下：

[ capture ] ( params ) mutable exception attribute -> ret { body } (1)
[ capture ] ( params ) -> ret { body } (2)
[ capture ] ( params ) { body } (3)
[ capture ] { body } (4)  

其中

  • (1) 是完整的 lambda 表达式形式，
  • (2) const 类型的 lambda 表达式，该类型的表达式不能改捕获("capture")列表中的值。
  • (3)省略了返回值类型的 lambda 表达式，但是该 lambda 表达式的返回类型可以按照下列规则推演出来：
    • 如果 lambda 代码块中包含了 return 语句，则该 lambda 表达式的返回类型由 return 语句的返回类型确定。
    • 如果没有 return 语句，则类似 void f(...) 函数。
  • 省略了参数列表，类似于无参函数 f()。

mutable 修饰符说明 lambda 表达式体内的代码可以修改被捕获的变量，并且可以访问被捕获对象的 non-const 方法。

exception 说明 lambda 表达式是否抛出异常(noexcept)，以及抛出何种异常，类似于void f() throw(X, Y)。

attribute 用来声明属性。

另外，capture 指定了在可见域范围内 lambda 表达式的代码内可见得外部变量的列表，具体解释如下：

  • [a,&b] a变量以值的方式呗捕获，b以引用的方式被捕获。
  • [this] 以值的方式捕获 this 指针。
  • [&] 以引用的方式捕获所有的外部自动变量。
  • [=] 以值的方式捕获所有的外部自动变量。
  • [] 不捕获外部的任何变量。

此外，params 指定 lambda 表达式的参数。

一个具体的 C++11 lambda 表达式例子： 

#include <vector>#include <iostream>
#include <algorithm>
#include <functional>

int main()
{
    std::vector<int> c { 1,2,3,4,5,6,7 };
    int x = 5;
    c.erase(std::remove_if(c.begin(), c.end(), [x](int n) { return n < x; } ), c.end());

    std::cout << "c: ";
    for (auto i: c) {
        std::cout << i << ' ';
    }
    std::cout << '\n';

    // the type of a closure cannot be named, but can be inferred with auto
    auto func1 = [](int i) { return i+4; };
    std::cout << "func1: " << func1(6) << '\n'; 

    // like all callable objects, closures can be captured in std::function
    // (this may incur unnecessary overhead)
    std::function<int(int)> func2 = [](int i) { return i+4; };
    std::cout << "func2: " << func2(6) << '\n'; 
}


标签：

相关文章