c++ - 有序双向链表搜索

Question

假设我们有按整数值排序的双向链表:

struct ListItem
{
  int value;
  ListItem *prev, *next;
};

struct List
{
  ListItem *first, *last;
  int count;
};

我们能否使用更快的搜索算法(例如二分搜索)在 List 中定位 ListItem 以及如何定位？

Answer 1

出于大多数实际目的，不会。如果你想要更快的搜索，链表是一个糟糕的数据结构选择。考虑使用 vector、deque、set 或 multiset。

编辑:也许最好提供一些指导，说明哪些在什么时候有意义。如果您有两个基本独立的阶段，则 vector 最有意义:要么按顺序插入所有数据，要么插入并排序，然后在数据排序后，数据保持静态，您只需在其中搜索。 deque 几乎是一样的，除了你可以在两端插入，所以如果你可能会乱序获取数据，但新数据总是属于集合的一端或另一端，它可能是一个不错的选择。

set 或 multiset 如果您要将插入/删除与查找混合使用，效果会更好。它始终保持排序，因此搜索总是相当快。在这两者(set 与 multiset)之间的选择非常简单:如果您需要确保集合中的每个项目都是唯一的，您需要 set。如果您可能有多个具有相同键的项目，您需要一个多集。