c++ - 为什么无序集会混合值

Question

我正在尝试使用 unordered_set 从 vector 中删除重复项。但我的设计创建了一个无法正确维护排序的 unordered_set。在此示例中，“z”不在末尾。我究竟做错了什么？提前谢谢你。

编辑:抱歉，如果我不清楚我在寻找什么。我希望输出为“e、d、a、b、c、z” 我想保留原始顺序但删除重复项。我目前使用大约 3 个不同的 for 循环和一个额外的 init vector 拷贝来工作。我只是在寻找一个尽可能更简洁的 STL 函数。

产生的输出:e d a b c a a a b b b b c z打印无序集e d a z b c

#include <iostream> 
#include <iterator>     
#include <algorithm>    
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    vector<string>terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };
    for (vector<string>::iterator it = terminals.begin(); it != terminals.end(); it++) // print given vector
        cout << *it << " ";
    cout << endl;
    unordered_set<string> newSet;
    copy(terminals.begin(), terminals.end(), inserter(newSet, newSet.end()));
    cout << "printing unordered set" << endl;
    for (unordered_set<string>::iterator it = newSet.begin(); it != newSet.end(); it++)
        cout << *it << " ";
    cout << endl;
    //system("pause");
    return 0;
}

Answer 1

std::unordered_set :

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

如果您需要订购独特的终端，请使用 std::set :

#include <iostream>
#include <vector>
#include <string>
#include <set>

int main() {
    std::vector<std::string>terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };

    for(const std::string& terminal : terminals) // print given vector
        std::cout << terminal << " ";
    std::cout << "\n";;

    // populate the set directly from the vectors iterators:
    std::set<std::string> newSet(terminals.begin(), terminals.end());;

    std::cout << "printing the (ordered) set:" << "\n";;
    for(const std::string& terminal : newSet)
        std::cout << terminal << " ";
    std::cout << "\n";;
}

如果你想保持原始顺序，你不能使用任何一个集合作为你的最终存储，但你可以使用一个std::unordered_set作为缓存/blacklist 用于您已插入最终存储的值。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>

int main() {
    std::vector<std::string>terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };

    for(const std::string& terminal : terminals) // print given vector
        std::cout << terminal << " ";
    std::cout << "\n";;

    std::vector<std::string> newSet; // not really a set anymore
    std::unordered_set<std::string> cache; // blacklist

    // try to insert all terminals and only when an insert is successful,
    // put the terminal in newSet

    std::for_each(terminals.begin(), terminals.end(),
        [&](const std::string& terminal) {
            auto [it, inserted] = cache.insert(terminal);
            if(inserted)
                newSet.push_back(terminal);
        }
    );

    std::cout << "printing the vector of unique terminals:" << "\n";;
    for(const std::string& terminal : newSet)
        std::cout << terminal << " ";
    std::cout << "\n";;
}

如果您想要原始顺序并且不介意直接对原始terminals vector 进行更改，您可以使用std::remove_if 与 unordered_set 相结合，这很好，因为它不需要新的 vector 。这是@Marek R 的回答的注释变体:

首先阅读:Erase–remove idiom

int main() {
    std::vector<std::string>terminals = { "e", "d", "a", "b", "c", "a", "a", "a", "a", "b","b", "b", "b", "c", "z" };

    for(const std::string& terminal : terminals) // print given vector
        std::cout << terminal << " ";
    std::cout << "\n";;

    std::unordered_set<std::string> cache; // blacklist

    // remove_if() moves all entries in your container, for which the
    // UnaryPredicate(*) returns true, to the end of the container. It returns
    // an iterator pointing to the first element in the vector that was
    // moved - which is a suitable starting point for a subsequent erase().
    //
    // (*) UnaryPredicate: A callable that returns true or false given a single
    //                     value.

    // auto past_new_end = std::vector<std::string>::iterator past_new_end
    auto past_new_end = std::remove_if(terminals.begin(), terminals.end(),
        // this lambda is the UnaryPredicate
        [&](const std::string& terminal) {
            // insert returns a std::pair<Iterator, bool>
            // where the bool (.second in the pair) is false
            // if the value was not inserted (=it was already present)
            return cache.insert(terminal).second == false;
        }
    );

    std::cout << "display all the entries (now with unspecified values) "
                 "that will be erased:\n";
    std::copy(past_new_end, terminals.end(),
                            std::ostream_iterator<std::string>(std::cout, "<"));
    std::cout << "\n";

    // erase all the moved entries
    terminals.erase(past_new_end, terminals.end());

    std::cout << "printing the unique terminals:" << "\n";;
    for(const std::string& terminal : terminals)
        std::cout << terminal << " ";
    std::cout << "\n";;
}