排序映射使用回调函数sort()

我有一个unordered_map<int,int>类型变量。我想根据它的值对地图进行排序。我想知道我是否可以在排序函数中使用回调，以便它根据它的值返回排序映射。

unordered_map<int,int> p;
for(int i=0;i<nums.size();i++){
            p[nums[i]]++;
        }
sort(p.begin(),p.end(),callback);

不能对unordered_map进行就地排序。您需要构建一个可排序的替代容器，将内容转储到其中(或带来引用原始映射中对所必需的适当材料)，然后进行排序。有很多方法可以做到这一点。以下是一些例子:

值复制排序

下面的代码在包含域1的范围内生成100个随机抽取。10，然后根据频率(值)降序排序后打印频率表(我怀疑这是驱动所有这一切开始的不言而喻的任务):

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <random>
int main()
{
    std::mt19937 rng{ std::random_device{}() };
    std::uniform_int_distribution<> dist(1, 10);
    std::unordered_map<int, int> p;
    for (int i = 0; i < 100; ++p[dist(rng)], ++i);
    std::vector<std::pair<int,int>> v { p.begin(), p.end() };
    std::sort(v.begin(), v.end(), 
        [](auto const& pr1, auto const& pr2) 
        { return pr2.second < pr1.second; });
    for (auto const& pr : v)
        std::cout << pr.first << ':' << pr.second << 'n';
}

(不同)

3:14
4:13
7:13
9:11
1:11
2:10
10:7
6:7
8:7
5:7

指向pair的指针

使用指向原始映射对的常量指针的替代机制也是可能的(如果映射内容过于昂贵或完全无法复制，则可能更可取):

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <random>
int main()
{
    std::mt19937 rng{ std::random_device{}() };
    std::uniform_int_distribution<> dist(1, 10);
    std::unordered_map<int, int> p;
    for (int i = 0; i < 100; ++p[dist(rng)], ++i);
    std::vector<const decltype(p)::value_type*> v;
    for (auto const& pr : p)
        v.emplace_back(&pr);
    std::sort(v.begin(), v.end(), 
        [](auto const& pr1, auto const& pr2) 
        { return pr2->second < pr1->second; });
    for (auto const& pr : v)
        std::cout << pr->first << ':' << pr->second << 'n';
}

(不同)

2:16
1:14
3:11
7:11
4:9
10:9
5:8
8:8
9:8
6:6

注意事项适用于此方法。这些指向配对的指针只有在它们兑现的当天才有效。例如，通过插入新键或修剪现有键来修改原始映射，整个指针床将被取消。这显然包括彻底摧毁原始地图。买家注意。

你在这里解决了两个问题:

根据std::map或std::unordered_map的值排序
使用一种"比较回调"std::sort

让我们先解决点2。如果我们在这里阅读CPP参考中对std::sort的描述，那么我们就会看到可以使用"比较函数对象"。作为第三个参数。这可以通过Lambda、函子或向要排序的对象添加比较操作符来实现。

让我们假设我们想要排序的std::vector中有一个struct。

struct IntVal {
    int val{};
};
std::vector<IntVal> intVals{};

如果我们想用Lambda来排序，那么:

std::sort(intVals.begin(), intVals.end(), [](const IntVal& iv1, const IntVal& iv2) { return iv1.val < iv2.val; });

或者，可以在类/结构中添加比较操作符:

struct IntVal{
    int val{};
    bool operator < (const IntVal& other) const { return val < other.val; }
};

或者你可以通过给你的类添加一个可调用操作符()，使你的类成为Functor。

#include <iostream>
#include <vector>
#include <algorithm>
struct IntVal{
    int val{};
    bool operator () (const IntVal& iv1, const IntVal& iv2) const { return iv1.val < iv2.val; }
};
std::vector<IntVal> intVals{ {3},{2},{1} };
int main() {
    std::sort(intVals.begin(), intVals.end(), IntVal());
    for (const IntVal& iv : intVals)
        std::cout << iv.val << 'n';
}

或者，如果不能修改类，则创建外部函子:

#include <iostream>
#include <vector>
#include <algorithm>
struct IntVal{
    int val{};
};
// Functor
struct Comp {
    bool operator () (const IntVal& iv1, const IntVal& iv2) const { return iv1.val < iv2.val; }
};
std::vector<IntVal> intVals{ {3},{2},{1} };
int main() {
    std::sort(intVals.begin(), intVals.end(), Comp());
    for (const IntVal& iv : intVals)
        std::cout << iv.val << 'n';
}

进入下一个话题。

您希望对存储在std::unordered_map中的数据按其"值"类型进行排序。

这在适当的地方是不可能的，因为映射的本质是它们已经排序了。你不能求助于他们。这会违反它们的内部行为。

第二个问题通常是键是唯一的。排序也可能破坏这种严格的要求。

解决方案是使用第二个容器。有了你上面提到的"排序"参数。将数据复制到另一个容器并排序。

可以使用std::vector和它的range构造函数来复制数据

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <utility>
// Functor
struct Comp {
    bool operator () (const std::pair<int,int>& p1, const std::pair<int, int>& p2) { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; }
};
int main() {
    std::unordered_map<int, int> test{ {1,4},{2,3},{3,2},{4,1} };
    std::vector<std::pair<int, int>> data(test.begin(), test.end());
    
    std::sort(data.begin(), data.end(), Comp());
    for (const auto[i1,i2] : data)
        std::cout << i1 << ' ' << i2 << 'n';
}

或者，最后但并非最不重要的，以及最终的解决方案。我们可以使用第二个按照定义排序的容器，比如std::multiset

这将创建一段非常容易理解的代码。

请见:

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <utility>
#include <set>
// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<int, int>;
// The map
using Map = std::unordered_map<Pair::first_type, Pair::second_type>;
// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Sorter = std::multiset<Pair, Comp>;
int main() {
    Map test{ {1,4},{2,3},{3,2},{4,1} };
    Sorter sorter(test.begin(), test.end());
    for (const auto[i1,i2] : sorter)
        std::cout << i1 << ' ' << i2 << 'n';
}

由于您真正想要做的是计数，因此请参见此示例。这里我们将以计算字符串中的字母为例:

#include <iostream>
#include <string>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
#include <cctype>
// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<char, unsigned int>;
// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;
// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

// --------------------------------------------------------------------------------------
// Compact function to calculate the frequency of charcters and then get their rank
Rank getRank(std::string& text) {
    // Definition of our counter
    Counter counter{};
    // Iterate over all charcters in text and count their frequency
    for (const char c : text) if (std::isalpha(c)) counter[char(std::tolower(c))]++;
    
    // Return ranks,sorted by frequency and then sorted by character
    return { counter.begin(), counter.end() };
}
// --------------------------------------------------------------------------------------
// Test, driver code
int main() {
    // Get a string from the user
    if (std::string text{}; std::getline(std::cin, text))
        // Calculate rank and show result
        for (const auto& [letter, count] : getRank(text))
            std::cout << letter << " = " << count << 'n';
}

相关内容

最新更新

热门标签：