我有一个地图(例如,字符为整数)。我将这些值逐个插入到这个映射中。例如,这里有四个插入:插入排序的地图
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。我试图避免在接受的解决方案中做出建议:创建另一个地图。
添加在标准::设置 – sehe
@misha的使用的https://ideone.com/SgbEN演示:寻找插入点(用'lower_bound')为O(log n)的,因为二进制搜索中采用。所以保持它在任何情况下都不是二次方的。请注意std :: set示例,它将项目保存在Btree中(在大多数实现中),就像std :: map – sehe