我可以按值对地图中的元素重新排序吗？ C++

Question

我想做一个table的字母频率，就像this

所以，我有包含一些文本的变量 str，还有包含每个字母出现次数的 map<char, int> m。

所以我有类似的东西：

vector<char> get_rank(const string& str)
{
    map<char, int> m;

    for (char i = 'a'; i <= 'z'; i++)
        m[i] = 0;

    for (char ch : str)
        m[ch]++;

    for (auto& it : m)
        v.push_back(it.first);
    return v;
}

但是地图是按键排序的，而不是按值排序的。有没有办法“重载” map 的比较器以按值对每个元素进行排序？如果答案是否定的，我怎样才能以同样的优雅实现同样的想法。因为我的每一个想法都显得有些枯燥和粗糙。

Answer 1

Is there a way to "overload" a comparator of map to order each element by value?

没有

If the answer is no, how can I implement the same idea but with the same elegancy.

取决于用例。该示例的一个优雅解决方案是对向量进行排序。

Answer 2

与其尝试使用显然不是为此设计的 STL 容器（订购地图），不如使用不同的容器。

您始终可以使用 std::pair<char, int> 作为 std::vector 的类型。

这些可以排序。

我更喜欢 std::vector<std::pair<char,int>> 只是因为我更习惯于使用向量，但这取决于你。

Answer 3

无法根据地图的映射值对地图进行排序。地图元素的顺序由地图根据其仅考虑键的比较器进行管理。

但是，当键是连续的且范围有限时，您不需要映射来计算频率。

使用 std::vector<letter_and_count> 和

而不是地图

struct letter_and_count {
     char letter;
     int count = 0;
};

用 letter 初始化为 a 直到 z 的元素初始化向量，然后在字符串中遇到字母 i 时递增 v[ i - 'a']。然后使用std::sort根据count成员对向量进行排序。

PS：注意下面的评论。字母 a 到 z 不一定是连续的。但是（也来自 eerorika 的想法）您可以使用简单的查找 table:

std::string alphabet{"abcdefghijklmnopqrstuvwxyz"};

然后首先找到那个alphabet中的字母并使用它在字母表中的索引进行计数。

Answer 4

我发现使用专用容器的方法非常好。

要计算 std::map 或在您的情况下应使用 std::unordered_map。之后可以将其复制到 std::vector 中并根据需要进行排序。示例：

#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <algorithm>

// Function to get the rank of letters in a string
std::vector<std::pair<char,int>>  getRank(const std::string& str) {

    // Count letters
    std::unordered_map<char, int> counter;
    for (const char c : str) counter[c]++;

    // Copy to vector and sort
    std::vector<std::pair<char, int>> rank(counter.begin(), counter.end());
    std::sort(rank.begin(), rank.end(), [](const std::pair<char, int>& p1, const std::pair<char, int>& p2) { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; });

    return rank;
}

// Test / Driver Code
int main() {

    std::string testString{ "122333444455555666666777777788888888" };

    for (const auto& [letter, count] : getRank(testString))
        std::cout << letter << ' ' << count << '\n';
}

这将以简单的方式工作。

使用 std::multiset 会使代码更加紧凑，因为它会自动为您排序值：

#include <iostream>
#include <string>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<const char, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<std::remove_const<Pair::first_type>::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>;
// ------------------------------------------------------------

// Function to get the rank of letters in a string
Rank getRank(const std::string& str) {

    Counter counter;
    for (const char c : str) counter[c]++;

    return { counter.begin(), counter.end() };
}

// Test / Driver Code
int main() {

    std::string testString{ "122333444455555666666777777788888888" };

    for (const auto& [letter, count] : getRank(testString)) 
        std::cout << letter << ' ' << count << '\n';
}

也可以使用最大堆找到最常使用的元素。

或者，在下面的例子中，我们可以获得x个最顶层的元素。而这只需要几行代码。下面将统计几乎所有的东西并根据值排序：

#include <iostream>
#include <utility>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <iterator>
#include <type_traits>

// Helper for type trait We want to identify an iterable container ----------------------------------------------------
template <typename Container>
auto isIterableHelper(int) -> decltype (
    std::begin(std::declval<Container&>()) != std::end(std::declval<Container&>()),     // begin/end and operator !=
    ++std::declval<decltype(std::begin(std::declval<Container&>()))&>(),                // operator ++
    void(*std::begin(std::declval<Container&>())),                                      // operator*
    void(),                                                                             // Handle potential operator ,
    std::true_type{});
template <typename T>
std::false_type isIterableHelper(...);

// The type trait -----------------------------------------------------------------------------------------------------
template <typename Container>
using is_iterable = decltype(isIterableHelper<Container>(0));

// Some Alias names for later easier reading --------------------------------------------------------------------------
template <typename Container>
using ValueType = std::decay_t<decltype(*std::begin(std::declval<Container&>()))>;
template <typename Container>
using Pair = std::pair<ValueType<Container>, size_t>;
template <typename Container>
using Counter = std::unordered_map<ValueType<Container>, size_t>;

// Function to get the k most frequent elements used  in any Container ------------------------------------------------
template <class Container>
auto topKFrequent(const Container& data, size_t k) {

    if constexpr (is_iterable<Container>::value) {

        // Count all occurences of data
        Counter<Container> counter{};
        for (const auto& d : data) counter[d]++;

        // For storing the top k
        std::vector<Pair<Container>> top(k);

        // Get top k
        std::partial_sort_copy(counter.begin(), counter.end(), top.begin(), top.end(),
            [](const std::pair<int, size_t >& p1, const std::pair<int, size_t>& p2) { return p1.second > p2.second; });

        return top;
    }
    else
        return data;
}
int main() {
    std::vector testVector{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6,7 };
    for (const auto& p : topKFrequent(testVector, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    double cStyleArray[] = { 1.1, 2.2, 2.2, 3.3, 3.3, 3.3 };
    for (const auto& p : topKFrequent(cStyleArray, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    std::string s{ "abbcccddddeeeeeffffffggggggg" };
    for (const auto& p : topKFrequent(s, 2)) std::cout << "Value: " << p.first << " \t Count: " << p.second << '\n';
    std::cout << '\n';

    double value = 12.34;
    std::cout << topKFrequent(value, 2) << "\n";

    return 0;
}

以上代码适用于C++17

下面是在任何容器中查找最频繁元素的示例。

但这是一个 C++20 解决方案：

#include <iostream>
#include <utility>
#include <unordered_map>
#include <queue>
#include <vector>
#include <iterator>
#include <type_traits>
#include <string>

// Some Alias names for later easier reading --------------------------------------------------------------------------
template <typename Container>
using ValueType = std::ranges::range_value_t<Container>;

template <typename Container>
using Pair = std::pair<ValueType<Container>, size_t>;

template <typename Container>
using Counter = std::unordered_map<ValueType<Container>, size_t>;

template <typename Container>
using UnderlyingContainer = std::vector<Pair<Container>>;

// Predicate Functor
template <class Container> struct LessForSecondOfPair {
    bool operator ()(const Pair<Container>& p1, const Pair<Container>& p2) { return p1.second < p2.second; }
};

template <typename Container>
using MaxHeap = std::priority_queue<Pair<Container>, UnderlyingContainer<Container>, LessForSecondOfPair<Container>>;

// Calculate max element ---------------------------------------------------------------------------------------------
template <class Container>
auto topFrequent(const Container& data) {

    if constexpr (std::ranges::range<Container>) {
        // Count all occurences of data
        Counter<Container> counter{};
        for (const auto& d : data) counter[d]++;

        // Build a Max-Heap
        MaxHeap<Container> maxHeap(counter.begin(), counter.end());

        // Return most frequent number
        return maxHeap.top().first;
    }
    else
        return data;
}

// Test
int main() {
    std::vector testVector{ 1,2,2,3,3,3,4,4,4,4,5,5,5,5,6,6,6,6,6,7 };
    std::cout << "Most frequent is: " << topFrequent(testVector) << "\n";

    double cStyleArray[] = { 1.1, 2.2, 2.2, 3.3, 3.3, 3.3 };
    std::cout << "Most frequent is: " << topFrequent(cStyleArray) << "\n";

    std::string s{ "abbcccddddeeeeeffffffggggggg" };
    std::cout << "Most frequent is: " << topFrequent(s) << "\n";

    double value = 12.34;
    std::cout << "Most frequent is: " << topFrequent(value) << "\n";

    return 0;
}

我可以按值对地图中的元素重新排序吗？ C++

Can I reorder elements in map by value? C++

c++

dictionary

stl

comparator