Список с уникальными элементами

Question

мне нужен контейнер, где:

• , когда я добавить новый элемент, который еще не существует, он добавляется в начало списка
• , когда я добавить элемент, уже существует, он не добавляется и II получить его индекс в списке
• когда элемент вставлен, он всегда имеет один и тот же индекс, и его можно получить с помощью этого индекса

std::set сам по себе недостаточен, посколькуЯ не могу получить доступ к элементам с помощью [index]. std::list ни потому, что он не хранит уникальные только элементы.

Я использовал смешанное решение с list и map, но, возможно, для этого существует стандартный стандартный шаблон?

Я не хочу использовать boost. Вызов list::unique после каждой вставки не является решением.

Answer 1

Если вы используете только std::list (или std::vector, по этому вопросу), вы не собираетесь обойти линейный поиск, если вы не хотите, чтобы избегать дублирования, но вы хотите сохранить оригинальный заказ. Простой std::vector решение, основанное может быть:

int 
createIndex(std::vector<T>& references, T const& newValue) 
{ 
    int results = std::find(references.begin(), references.end(), newValue) 
            - references.begin(); 
    if (results == references.size()) { 
     references.push_back(newValue); 
    } 
    return results; 
} 

В качестве альтернативы, вы можете использовать std::map:.

int 
createIndex(std::map<T, int>& references, T const& newValue) 
{ 
    st::map<T, int>::iterator results = references.find(newValue); 
    if (results == references.end()) { 
     results = references.insert(
        std::make_pair(newValue, references.size())).first; 
    } 
    return results->second; 
} 

(Это предполагает, что T поддерживает < Если нет, то вам придется установить упорядоченность critera. Или используйте unordered_map и определите хеш-код для .)