c++ - map 的插入排序

Question

我有一个映射(例如，字符到整数)。我将值一个一个地插入到这张 map 中。例如，这里有四个插入:

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

我想根据关联值对 map 键进行排序。因此，在每次插入时，我都会得到排序后的输出:

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 中，并在执行插入之前删除该映射。 multimap 使键保持有序，因此它负责排序。

有没有更快的方法来做到这一点？我应该使用不同的、更高效的容器吗？

编辑

这是 C++ STL multimap我正在使用。它很方便，因为它保留了它的元素 internally ordered .

这是一个 related question .我试图避免按照已接受的解决方案中的建议进行操作:创建另一张 map 。

Answer 1

我本来会做的是这样的事情。想象一下你的 map x至 y .我会创建一个结构(类，随便什么):

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的元素存在您想要的值(value)。如果是这样，只需更新 y , 否则插入一个新元素。