c++ - 包含独特元素的列表

Question

我需要一个容器，其中:

• 当我添加一个尚不存在的新元素时，它会被添加到列表的顶部
• 当我添加一个已经存在的元素时，它没有被添加，我得到它在列表中的索引
• 一旦元素被插入，它总是有相同的索引，并且可以使用这个索引访问它

单独使用

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 支持 < 。如果不支持，您必须建立一个排序标准。或者使用 unordered_map并为它。)