列表与独特的元素

问题描述：

我需要一个容器，其中：列表与独特的元素

当我添加一个新的元素不存在，它被添加到列表中
的顶部，当我添加的元素已经存在，它不会被添加和II获得其索引列表中的
一旦元素被插入时，它总是具有相同的指数，它可以使用该索引

单独std::set是不够的访问，因为我无法访问[index]中的元素。 std::list都不是，因为它不存储唯一的唯一元素。

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

我不想使用提升。在每次插入后调用list::unique是无法解决的。

如何滚动你自己的？你有没有尝试过？听起来像'list'上的一个非常薄的包装... – 2012-04-20 10:12:01

@Soohjun：用'list'实现这个不会很好;初始碰撞检测将会是O（n），就像按索引查找一样。 – 2012-04-20 10:12:43

列表*和*地图，如果你经常添加现有的元素。 – 2012-04-20 10:12:55

答

如果你只使用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并为它定义一个散列码吧。）

列表与独特的元素

相关推荐