c++ - C++ 中的数据结构，用于维护插入顺序和消除重复

Question

我需要维护用户输入数据的顺序，但需要消除重复项。我查看了地图，它消除了重复项，但无法保持用户输入的顺序。设置同样的问题。stl中是否有任何数据结构可以同时满足这两个要求？我不能在这个项目上使用 boost。

Answer 1

问题在于，如果您保持搜索顺序，则搜索重复项的成本很高，因此您不会倾向于找到两者兼得的数据结构。C++11 引入了std::unordered_set，这可能是你想要的。

如果你不使用 C++11，你可以将一些标准容器封装在一个类中。我建议您将项目弹出到 aset或 amap中，然后将迭代器存储到 a 中的项目vector。

Answer 2

维护地图和列表。对于每个元素，在附加到列表之前搜索地图。如果没有找到，追加到列表并插入到地图中，否则继续。

Answer 3

#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#include <unordered_set>

using namespace std;

int main(int argc, char *argv[])
{
    std::vector<int> data;
    std::unordered_set<int> uniqueCollection;

    for(int i = 0; i < 50; ++i)
    {
        int newData = rand() % 27;

        cout << "trying to insert: " << newData << endl;

        if(uniqueCollection.find(newData) == uniqueCollection.end())
        {
            cout << "  inserting item: " << newData << endl;

            data.push_back(newData);    
            uniqueCollection.insert(newData);
        }
        else
        {
            cout << "  element already exists: " << newData << endl;
        }
    }

    return 0;
}

http://www.cplusplus.com/reference/unordered_set/unordered_set/

http://www.cplusplus.com/reference/vector/