包含独特元素的列表

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并为其定义一个哈希码。）