在C++程序开发中，查找和插入操作的性能往往是影响整体运行效率的关键因素，不同的数据结构在这两类操作上的时间复杂度差异极大，选择适配场景的高效数据结构能够显著降低操作耗时。
常用高效数据结构对比
首先我们来看几种常见的高效数据结构在查找和插入操作上的时间复杂度表现，方便后续根据场景选择：
| 数据结构 | 平均查找时间 | 平均插入时间 | 最坏情况时间 | 适用场景 |
|---|---|---|---|---|
| 哈希表（unordered_map） | O(1) | O(1) | O(n) | 无需有序、频繁查找插入的场景 |
| 红黑树（map） | O(log n) | O(log n) | O(log n) | 需要有序、稳定时间复杂度的场景 |
| 跳表 | O(log n) | O(log n) | O(n) | 需要有序且实现简单的场景 |
哈希表的使用与优化
C++标准库中的unordered_map和unordered_set底层基于哈希表实现，平均查找和插入时间都是O(1)，是减少操作耗时的首选方案之一。我们可以通过自定义哈希函数和预留空间来进一步优化性能。
基础使用示例
下面是使用unordered_map进行插入和查找的基础代码：
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 创建哈希表
std::unordered_map<int, std::string> userMap;
// 插入操作
userMap[1001] = "张三";
userMap.insert(std::make_pair(1002, "李四"));
userMap.emplace(1003, "王五");
// 查找操作
auto it = userMap.find(1002);
if (it != userMap.end()) {
std::cout << "找到用户：" << it->second << std::endl;
} else {
std::cout << "未找到用户" << std::endl;
}
// 判断是否存在key
if (userMap.count(1003) > 0) {
std::cout << "用户1003存在" << std::endl;
}
return 0;
}
优化技巧
- 提前调用
reserve方法预留足够的桶空间，避免频繁扩容带来的性能损耗 - 对于自定义类型作为key的情况，自定义哈希函数减少哈希冲突
- 如果不需要修改value，尽量使用
find而不是operator[]，避免意外插入默认值
红黑树的使用场景
当我们需要数据结构中的元素保持有序，或者需要稳定的O(log n)时间复杂度时，标准库的map和set是更好的选择，它们底层基于红黑树实现，虽然平均效率略低于哈希表，但不会出现最坏情况的性能骤降。
代码示例
下面是使用map进行有序插入和范围查找的示例：
#include <iostream>
#include <map>
#include <string>
int main() {
// 创建红黑树结构的map，key会自动排序
std::map<int, std::string> scoreMap;
// 插入操作，key会自动按升序排列
scoreMap[95] = "优秀";
scoreMap[60] = "及格";
scoreMap[85] = "良好";
scoreMap[59] = "不及格";
// 查找指定key
auto it = scoreMap.find(85);
if (it != scoreMap.end()) {
std::cout << "85分对应等级：" << it->second << std::endl;
}
// 范围查找，输出60到90分之间的等级
std::cout << "60到90分之间的等级：" << std::endl;
auto low = scoreMap.lower_bound(60);
auto high = scoreMap.upper_bound(90);
for (auto iter = low; iter != high; ++iter) {
std::cout << iter->first << "分：" << iter->second << std::endl;
}
return 0;
}
自定义跳表实现
如果标准库的数据结构无法满足需求，我们也可以自己实现跳表来平衡性能和实现难度，跳表的有序查找和插入效率同样为O(log n)，实现起来比红黑树简单很多。
简化跳表实现示例
下面是一个简化版的跳表插入和查找实现：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// 跳表节点定义
struct SkipListNode {
int key;
std::vector<SkipListNode*> forward; // 每层的下一个节点指针
SkipListNode(int k, int level) : key(k), forward(level, nullptr) {}
};
// 跳表类
class SkipList {
private:
int maxLevel; // 最大层数
float probability; // 节点升级层数的概率
SkipListNode* header; // 头节点
int currentLevel; // 当前实际层数
// 随机生成节点层数
int randomLevel() {
int level = 1;
while ((rand() % 100) < probability * 100 && level < maxLevel) {
level++;
}
return level;
}
public:
SkipList(int maxL, float prob) : maxLevel(maxL), probability(prob), currentLevel(1) {
header = new SkipListNode(-1, maxLevel);
srand(time(nullptr));
}
// 插入操作
void insert(int key) {
std::vector<SkipListNode*> update(maxLevel, nullptr);
SkipListNode* node = header;
// 从最高层往下查找每层的前驱节点
for (int i = currentLevel - 1; i >= 0; --i) {
while (node->forward[i] != nullptr && node->forward[i]->key < key) {
node = node->forward[i];
}
update[i] = node;
}
// 检查key是否已存在
node = node->forward[0];
if (node == nullptr || node->key != key) {
int newLevel = randomLevel();
if (newLevel > currentLevel) {
for (int i = currentLevel; i < newLevel; ++i) {
update[i] = header;
}
currentLevel = newLevel;
}
// 创建新节点并插入
SkipListNode* newNode = new SkipListNode(key, newLevel);
for (int i = 0; i < newLevel; ++i) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
}
// 查找操作
bool search(int key) {
SkipListNode* node = header;
for (int i = currentLevel - 1; i >= 0; --i) {
while (node->forward[i] != nullptr && node->forward[i]->key < key) {
node = node->forward[i];
}
}
node = node->forward[0];
return node != nullptr && node->key == key;
}
};
int main() {
SkipList skipList(5, 0.5);
// 插入测试数据
skipList.insert(3);
skipList.insert(1);
skipList.insert(5);
skipList.insert(2);
// 查找测试
std::cout << "查找2：" << (skipList.search(2) ? "存在" : "不存在") << std::endl;
std::cout << "查找4：" << (skipList.search(4) ? "存在" : "不存在") << std::endl;
return 0;
}
数据结构选择建议
在实际开发中，我们可以根据以下原则选择数据结构：
- 如果不需要元素有序，且对平均性能要求高，优先选择
unordered_map/unordered_set - 如果需要元素有序，或者需要稳定的时间复杂度，选择
map/set - 如果标准库结构不满足需求，且需要实现简单的有序结构，可以自定义跳表
- 如果数据量极小，普通数组或
vector的线性查找也可能比复杂数据结构更高效，不需要过度优化