我有多个4096项的实例。我需要重新搜索并找到一个项目，我想对它进行优化。由于不是所有4096个项目都可以使用，我想，加快速度的方法是使用链表而不是数组。每当我必须搜索一个项目时，一旦我找到它，我就会把它放在列表的首位，这样下次它出现时，我只需要做最小的搜索（循环）工作。这听起来对吗？
编辑1我不认为二进制搜索树的想法真的是我可以使用的，因为我已经对数据进行了排序，比如一个数组，即前一个节点后面的每个节点都更大，这违背了目的，不是吗？
我试图解决我的缓存问题，并想出了这样的东西：
pending edit
但我得到的输出表明，它并不像我希望的那样工作：
有什么建议可以改进吗？
说到性能，只有一条重要的规则：衡量它！
例如，在您的情况下，您可能有两个不同的考虑因素，一个是理论运行时分析，另一个是机器的实际情况。两者都在很大程度上取决于4096件物品的特性。如果你的数据是排序的，你可以进行O（logn）搜索，如果它是未排序的，那就是最坏的情况O（n）等。
关于链表的想法，您可能会有更多的硬件缓存未命中，因为数据不再存储在一起（空间局部性），最终实现速度较慢，即使您的理论考虑是正确的。
如果你对这些问题感兴趣，我推荐GoingNative 2013的这篇很酷的演讲http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly
最坏的情况是，除非像Brett建议的那样对数组或列表进行排序，否则搜索仍然为O（N）。因此，使用排序列表，可以增加插入的复杂性（按顺序插入），但搜索速度会快得多。你的建议几乎就像一个"缓存"。如果不知道在短期内再次搜索一个找到的项目的频率，我们很难说这会有多有用。显然，缓存有好处，这就是为什么我们在内存中有整个L1、L2、L3体系结构。但它是否会对你起作用还不确定。
如果您的数据可以放在二进制搜索树中：http://en.wikipedia.org/wiki/Binary_search_tree
然后你可以使用一个名为Splay树的数据结构："Splay树是一个自调整的二进制搜索树，具有最近访问的元素可以快速再次访问的附加属性。"http://en.wikipedia.org/wiki/Splay_tree
响应Edit1：我认为，如果你的数据元素不大，比如说只有几个字节甚至几十个字节，那么其中4096个可以放入内存。在这种情况下，您需要的是一个哈希表。在C++中，使用unordered_map。例如，如果键类型为int，则可以定义unorderedmap<int, ptr_to_your_node_type>并在O(1)中获取元素。
如果你能很好地设计你的散列，最快的搜索可能是O(1)，最坏的情况可能是O(n)。如果这些项目很大，无法装入内存，则可以使用所谓的最近最少使用的缓存algorithm来节省内存。
LRU缓存的示例代码
template <typename K>
class Key_Age{
list<K> key_list;
unordered_map<K, typename list<K> :: iterator> key_pos;
public:
void access(K key){
key_list.erase(key_pos[key]);
insert_new(key);
}
void insert_new(K key){
key_list.push_back(key);
key_pos[key] = --key_list.end();
}
K pop_oldest(){
K t = key_list.front();
key_list.pop_front();
return t;
}
};
class LRU_Cache{
int capacity;
Key_Age<int> key_age;
unordered_map<int, int> lru_cache;
public:
LRU_Cache(int capacity): capacity(capacity) {
}
int get(int key) {
if (lru_cache.find(key) != lru_cache.end()) {
key_age.access(key);
return lru_cache[key];
}
return -1;
}
void set(int key, int value) {
if (lru_cache.count(key) < 1) {
if (lru_cache.size() == capacity) {
int oldest_key = key_age.pop_oldest();
lru_cache.erase(oldest_key);
}
key_age.insert_new(key);
lru_cache[key] = value;
return;
}
key_age.access(key);
lru_cache[key] = value;
}
}；