c++ - 搜索列表的更快方法？

Question

我正在尝试使我的程序更有效地运行，并且我相信修复此线性搜索会在速度方面有很大帮助，但我很好奇我将如何将其更改为二进制搜索之类的东西，因为我相信列表不一定是有序的。是否有某种方法可以根据第一个参数对列表进行排序key？

我目前正在使用的内容：

int* key_sequences::data(int key){
    for(it=myList.begin(); it!=myList.end(); ++it){
        if(it->first==key){
            return &(it->second[0]);
        }
    }
    return nullptr;
};

Answer 1

在简单链表中搜索是 O(n)，其中n是列表的大小。

然而，在某些实现中，人们使用三个列表指针，一个在开头，一个在中间，一个在结尾，这样当搜索出现时 - 他们可以加快处理速度，因此您可以在线搜索。

但是，如果我是你并且对加快搜索非常感兴趣，我会尝试另一种数据结构（散列？类似std::unordered_map）或对列表进行排序。