可搜索的堆栈 [英] Searchable stack

问题描述

我正在寻找一种类似堆栈的数据结构，该结构可以有效地搜索内容.实际上，我想要一个既可以保持元素插入顺序的结构，又可以通过元素的值比O(n)更快地搜索(以防止重复).

I'm looking for a stack-like data structure that allows efficient searching of the contents. Effectively I want a structure that both maintains the order in which elements are inserted, but is also searchable faster than O(n) by value of the elements (in order to prevent duplicates).

这些元素很小(指针)，我主要关心的是内存效率，因此简单地使用两个互补的数据结构(一个用于保持顺序，一个用于搜索)绝对不是理想的选择.

The elements are small (pointers), and my primary concern is memory efficiency, so simply using two complementary data structures (one to maintain the order and one to search) is definitely not ideal.

推荐答案

不要低估两个数据结构的内存效率.您应该首先尝试简单的boost多索引容器库，并查看其内存占用量是否足够.

Don't underestimate the memory-efficiency of two data structures. You should try the straightforward boost multi-index container library first, and see if its memory footprint is sufficient.

我想到的第一个较不常见的数据结构是一个跳过列表.但是，此列表将不起作用，因为您要搜索与订购的钥匙不同的钥匙.只是注意那些有相同想法的人.

The first less usual data structure I have thought of as an answer was a skip list; however, this list won't do because you are searching for a different key than the one you are ordering on. Just noting for others who have the same idea.

这篇关于可搜索的堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！