c++ - 什么是存储排列的好数据结构以及排列发生多少次？

Question

我的排列是唯一的数字对。我需要浏览一个列表并计算给定排列发生的次数。所以我需要将它记录在数据结构中。

(1,1) 0
(1,2) 5
(1,3) 3
(2,2) 5
(2,3) 2
(3,3) 1

最终，我需要能够按降序对这个容器进行排序，这样我才能得到出现次数最多的排列。非常感谢！！

Answer 1

我只是制作一个pair到int的无序映射（假设int就足够了，你可能需要一个长整数或任意大的整数）。如果键已经存在，只需增加值，否则将值设置为 1

Answer 2

使用std::map<std::pair<int, int>, int>. 像这样插入：

std::map<std::pair<int, int>, int> myMap;
typedef std::map<std::pair<int, int>, int>::iterator Iterator;
// Insert "permutation" (0,1) with a default of 0 uses
Iterator it=myMap.insert(std::make_pair(std::make_pair(0, 1), 0)).first;
++it->second; // Increment use count - will use old count if already there

您甚至不需要事后对其进行排序，您始终可以在每次插入后记录当前的最大值！

请注意，插入中的外部对带有您使用次数的默认值。如果元素尚未在地图中，这将设置为 0。所以如果排列已经存在，它会找到你的地图元素，否则它会插入它并将使用计数设置为零。然后你只是增加它的任何一种方式！