可搜索堆棧

Question

我正在尋找一種可以高效搜索內容的堆棧式數據結構。實際上，我想要一個既能保持插入元素的順序，又能通過元素的值（爲了防止重複）而快速搜索O（n）的結構。

元素很小（指針），我主要關心的是內存效率，所以簡單地使用兩個互補的數據結構（一個維護順序和一個搜索）絕對不是理想的。

Answer 1

不要低估兩個數據結構的內存效率。您應該首先嚐試簡單的boost多索引容器庫，然後查看其內存佔用是否足夠。

我認爲作爲答案的第一個不太常見的數據結構是跳過列表;但是，這個列表不會執行，因爲您正在搜索與您訂購的不同的鍵。只是注意那些有着同樣想法的人。

Answer 2

如果您主要關心的是內存效率，那麼您最好使用原始鏈接列表數據結構。線性搜索的複雜性並沒有那麼糟糕，除非你已經證明了相反。

或者你可以嘗試使用任何數據結構，它提供了一個有兩個小升級的高效搜索：每個元素應該包含一個鏈接到以前添加的元素，所以做一個反向列表，並且你應該存儲一個鏈接到頭這個列表，即最後添加的元素。這些升級是緩解推送和爆裂元素所必需的。