簡單而有效的方法來存儲可以通過密鑰或序數C++訪問的數據

我需要創建一個數據結構，可以通過字符串鍵或它們的序號來訪問元素。簡單而有效的方法來存儲可以通過密鑰或序數C++訪問的數據

該類當前使用包含字符串鍵和指向任何元素的指針的節點數組。這允許O（n）循環，或O（1）通過序號獲取元素，但是我發現通過鍵找到元素的唯一方法是執行O（n）循環並比較鍵直到找到我想要的，當有1000多個元素時，這是很慢的。有沒有辦法使用鍵來引用指針，還是我運氣不好？

編輯：通過序號沒有那麼重要O（n）循環。這將被用作一個基礎結構，它將被繼承用於其他方式，例如，如果它是一個可繪製對象的結構，我希望能夠在一個循環中繪製所有這些結構

來源

2011-05-06 Andrew

您可以使用std::map來搜索O(log n)的搜索速度。查看this branch瞭解更多詳情。在這個分支中，恰好你的情況（快速檢索值string或/和ordinal鍵）被討論。

小例子（序鍵使用，你可以做similiar事情串）：

#include <map> 
#include <string> 

using std::map; 
using std::string; 

struct dummy { 
unsigned ordinal_key; 
string dummy_body; 
}; 

int main() 
{ 
map<unsigned, dummy> lookup_map; 
dummy d1; 
d1.ordinal_key = 10; 
lookup_map[d1.ordinal_key] = d1; 
// ... 
unsigned some_key = 20; 
//determing if element with desired key is presented in map 
if (lookup_map.find(some_key) != lookup_map.end()) 
    //do stuff 
}

來源

2011-05-06 05:50:49 beduin

-1

使用hashmap

來源

2011-05-06 05:53:23 QuantumMechanic

如果你很少修改數組你可以把它分類和使用binary_search在它上面找到O(logn)時間內的鍵值（技術上O(klogn)，因爲你正在使用字符串[其中k是鍵字符串的平均長度]）。
當然這（就像使用map或unordered_map一樣）會混淆你的序數檢索，因爲元素將按照排序順序而不是順序存儲。

來源

2011-05-06 06:04:11

這似乎是現在最有效的時間和空間方式，感謝您的幫助 – Andrew 2011-05-06 15:09:34

@Andrew：通常值得檢查處理您當前的容器是否在引入新容器之前解決了問題。 – 2011-05-07 00:02:28

使用向量與地圖：

std::vector<your_struct> elements; 
std::map<std::string, int> index;

地圖允許您檢索在O（LG n）的時間關鍵的指標，而向量允許通過索引O（1）元素訪問。

來源

2011-05-06 06:04:51 zvrba

int將在地圖中顯示什麼，以及這會創建多少開銷？ – Andrew 2011-05-06 15:04:43

int是元素向量的索引。 – zvrba 2011-05-08 04:51:33

簡單而有效的方法來存儲可以通過密鑰或序數C++訪問的數據

回答

相關問題