列表與獨特的元素

我需要一個容器，其中：列表與獨特的元素

當我添加一個新的元素不存在，它被添加到列表中
的頂部，當我添加的元素已經存在，它不會被添加和II獲得其索引列表中的
一旦元素被插入時，它總是具有相同的指數，它可以使用該索引

單獨std::set是不夠的訪問，因爲我無法訪問[index]中的元素。 std::list都不是，因爲它不存儲唯一的唯一元素。

我用list和map的混合解決方案，但也許有一些標準的通用模板？

我不想使用提升。在每次插入後調用list::unique是無法解決的。

來源

2012-04-20 Jakub M.

如何滾動你自己的？你有沒有嘗試過？聽起來像'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併爲它定義一個散列碼吧。）

來源

2012-04-20 10:25:21

列表與獨特的元素

回答

相關問題