c++ - 稳定排序C++ HashMap -保留相等元素的插入顺序

Question

假设我有一个std::unordered_map<std::string, int>，代表一个单词和该单词在书中出现的次数，我希望能够按值对它进行排序。
问题是，我希望排序稳定，以便在两个项目具有相等值的情况下，我希望将第一个插入到 map 中的项目放在第一位。

通过添加附加字段来实现它很简单，该字段将保留插入的time。然后，创建一个同时使用time和value的编译器。使用简单的std::sort将给我O(Nlog(N))时间复杂度。

就我而言，只要时间可以改善，空间就不是问题。我想利用它并进行存储桶分类。这应该给我O(N)时间复杂度。但是，当使用存储桶排序时，没有编译器，当迭代映射中的项目时，不会保留顺序。

如何既可以使其保持稳定，又可以通过存储桶排序或其他方式保持O(N)时间的复杂性？
我猜想，如果我有某种哈希映射可以在迭代时保留插入顺序，那将解决我的问题。

具有相同时间复杂度的任何其他解决方案都是可以接受的。

注意-我已经看过this和that，由于它们都是2009年的，而且我认为我的案子更具体，所以我提出了这个问题。

Answer 1

这是我使用std::unordered_map并使用std::vector跟踪插入顺序的可能解决方案。

创建一个以字符串为键的哈希映射，并将其计为值。
此外，使用该映射类型的迭代器创建一个 vector 。

在对元素进行计数时，如果对象尚未在 map 中，则将其添加到 map 和 vector 中。否则，只需增加计数器。 vector 将保留将元素插入到 map 的顺序，并且插入/更新将仍然处于O(1)时间复杂度。

通过对 vector (而不是 map )进行迭代来应用存储桶排序，这可以确保保留顺序，并且我们将获得稳定的排序。 O(N)

从存储桶中提取内容以创建排序数组。 O(N)

实现:

    unordered_map<std::string, int> map;
    std::vector<std::unordered_map<std::string,int>::iterator> order;

    // Lets assume this is my string stream
    std::vector<std::string> words = {"a","b","a" ... };

    // Insert elements to map and the corresponding iterator to order
    for (auto& word : words){
        auto it = map.emplace(word,1);
        if (!it.second){
            it.first->second++;
        }
        else {
            order.push_back(it.first);
        }
        max_count = std::max(max_count,it.first->second);
    }

    //  Bucket Sorting
    /*  We are iterating over the vector and not the map
        this ensures we are iterating by the order they got inserted */
    std::vector<std::vector<std::string>> buckets(max_count);
    for (auto o : order){
        int count = o->second;
        buckets[count-1].push_back(o->first);
    }

    std::vector<std::string> res;
    for (auto it = buckets.rbegin(); it != buckets.rend(); ++it)
        for (auto& str : *it)
            res.push_back(str);