插入排序的地图

Question

我有一个地图（例如，字符为整数）。我将这些值逐个插入到这个映射中。例如，这里有四个插入：

1: A -> 1 
2: B -> 2 
3: C -> 3 
4: D -> 1 

我想根据它们的关联值对映射键进行排序。因此，在每次插入，我会在排序输出：

1: A(1) 
2: B(2), A(1) 
3: C(3), B(2), A(1) 
4: C(3), B(2), A(1), D(1) 

此外，我希望能够覆盖现有的映射，以保持键（字符）是唯一的。所以第五插入：

5: A -> 27 

会导致排序输出为：

5: A(27), C(3), B(2), D(1) 

的一种方式，我可以做到这一点是使用多重映射。 multimap的关键是整数，值是字符。每次插入到multimap中首先需要检查该字符是否已经存在于multimap中，并在执行插入操作之前删除该映射。 multimap保持键的顺序，以便照顾排序。

有没有更快的方法来做到这一点？是否有我应该使用的另一个更高效的容器？

编辑

下面是我使用的C++ STL multimap。它很方便，因为它保留了其元素internally ordered。

这是related question。我试图避免在接受的解决方案中做出建议：创建另一个地图。

Answer 1

的图谱排序由它的键，顾名思义。

这些值不能用于映射的排序谓词中，因为这些值是非常量！更改它们会使容器不变量（排序）无效。

如果您想通过“价值”命令项，它是隐含的关键，你可能需要一个

std::set<std::pair<key, value> > 

更新这里是一个工作演示：https://ideone.com/SgbEN

改为

。为了能够通过不同的谓词重新排序，您需要一个列表，向量或任何其他顺序容器。

编辑

名单的解决方案过于低效的，因为我会在每次插入后进行排序，并且不会有保持键唯一的有效途径。

这里的解决方案是使用

• std::make_heap
• std::push_heap
• 和std::sort_heap

算法。他们用列表正常工作（以及矢量便宜value_types - 或使用的C++ 0x移动语义）

如果您无法使用列表，购买后得到sort_heap步：使用

insert_point = std::lower_bound(lst.begin(), lst.end(), insertee); 
st.insert(insertion_point, insertee); 

到直接插入有序位置。你可以预计push_heap对于许多插入来说会更快，并且lowerbound/insert对于许多访问更快。

Answer 2

通常情况下，映射是混洗数据结构（至少对于关联值）。因此，排序地图的元素是没有意义的。

因此，您应该使用类似列表或数组的东西来保持元素排序。

我认为针对您的问题的最佳解决方案是最简单的方法：将元素存储在列表中并对其进行排序。或者你可以使用堆。

UPDATE：

地图是一种存储由密钥值的组合和映射的值形成 元件关联容器的。

在映射中，键值通常用于唯一标识 元素，而映射值是与此关键字 关联的某种值。键和映射值的类型可能不同。例如， 地图的典型示例是电话指南，其中名称是 键，电话号码是映射值。

内部，在地图中的要素从低到高 键值下面就 建设设置一个特定的严格弱排序标准进行排序。

作为关联容器，它们是特别设计为 效率可以通过键（不同于序列 容器，这是通过它们的 相对或绝对位置更有效的存取元件）[1]访问其元素。

[1] http://www.cplusplus.com/reference/stl/map/

Answer 3

我会做的就是这样。想象一下你的地图地图x到y。我想创建一个struct（类，等等）：

struct element 
{ 
    map_this_t x; 
    to_this_t y; 
    bool operator < (element &rhs) 
    { 
     return y < rhs.y;  // sorted based on y 
    } 
}; 

然后创建一个set<element>并插入到这一点。如果您遍历集合中的所有数据，那么您可以按照所需的顺序获取数据。插入时，首先搜索并查看是否存在具有x值的元素。如果是这样，只需更新y，否则插入一个新元素。

Answer 4

只使用一个map <char,int>和你的按键将保持独特的双<char,int>将在IT卖场排序。

基于其相关值店pair<int,char>一组太元素进行排序。