c++ - 具有独特元素的列表

Question

我需要一个容器，其中：

• 当我添加一个尚不存在的新元素时，它被添加到列表的顶部
• 当我添加一个已经存在的元素时，它不会被添加并且我会在列表中获取它的索引
• 插入元素后，它始终具有相同的索引，并且可以使用该索引进行访问

std::set单独是不够的，因为我无法使用[index]. std::list也不是，因为它不存储唯一的元素。

我使用了混合解决方案，list但map也许有一些标准的通用模板？

我不想使用升压。list::unique每次插入后调用都不是解决方案。

Answer 1

如果您只使用 a 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支持<。如果不支持，则必须建立排序标准。或者使用unordered_map并为其定义哈希码。）