datastructure в C++ для поддержания порядка вставки и устранения дубликатов

Question

Мне нужно поддерживать порядок ввода пользователем данных, но необходимо устранить дубликаты. Я посмотрел на карту, она устраняет дубликаты, но невозможно поддерживать порядок ввода пользователя. Такая же проблема с множеством. Есть ли какая-либо структура данных в stl, которая может отвечать обоим требованиям? Я не могу использовать boost над этим проектом.

Answer 1

Поддержание карты и списка. Для каждого элемента выполните поиск карты перед добавлением в список. Если не найдено, добавьте в список и вставьте в карту, продолжайте.

Answer 2

Проблема в том, что если вы поддерживаете порядок поиска, вам стоит искать дубликаты, поэтому вы не склонны находить структуры данных, которые делают оба. C++ 11 вводит std::unordered_set, что, вероятно, вам нужно.

Если вы не используете C++ 11, вы можете просто инкапсулировать некоторые стандартные контейнеры в класс. Я бы предположил, что вы поместите свои предметы в set или map, а затем сохраните итератор для элемента в vector.

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/