C++函数调用中高效操作set容器的原理与实践

1次阅读

没有评论

共计 2144 个字符，预计需要花费 6 分钟才能阅读完成。

set 是 C ++ STL 中的关联容器，基于红黑树实现，具有以下核心特性：

自动排序：元素插入后自动按升序排列（默认使用 less 比较）
唯一性：容器内不允许重复元素（与 multiset 区别）
对数复杂度：查找 / 插入 / 删除操作平均时间复杂度为 O(log n)

典型使用场景包括：

需要维护有序唯一元素的集合
需要频繁查询元素是否存在的场景
需要快速获取最大值 / 最小值的场景

在实际开发中，我们发现以下常见性能问题：

插入效率：
直接使用 insert 会先构造临时对象
频繁插入导致内存频繁分配
查找效率：
线性查找（如find_if）破坏红黑树优势
错误使用 count 进行存在性判断
删除效率：
单个元素循环删除导致多次树调整
未利用范围删除的批量优势

直接构造元素到容器内部，避免临时对象创建：

std::set<std::string> names;
// 传统 insert 方式（有拷贝开销）names.insert("Alice"); 
// 优化方案（直接构造）names.emplace("Bob");

性能对比（测试 10 万次插入）：

insert: 38ms
emplace: 25ms（节省 34% 时间）

利用红黑树有序特性进行范围查询：

std::set<int> scores{60, 70, 80, 90, 100};
// 查找第一个 >=75 的元素
auto it = scores.lower_bound(75); // 返回指向 80 的迭代器
// 查找第一个 >85 的元素  
it = scores.upper_bound(85); // 返回指向 90 的迭代器

使用迭代器范围删除比单元素删除更高效：

// 低效方式（O(n log n)）for(auto it = s.begin(); it != s.end();) {if(*it % 2 == 0) {it = s.erase(it); // 每次删除都触发树调整
  } else {++it;}
}

// 高效方式（O(n)）auto first = s.lower_bound(20);
auto last = s.upper_bound(80);
s.erase(first, last); // 批量删除 [20,80] 区间

#include <iostream>
#include <set>
#include <chrono>

void benchmark() {
  std::set<int> s1, s2;

  // 插入性能对比
  auto t1 = std::chrono::high_resolution_clock::now();
  for(int i=0; i<100000; ++i) {s1.insert(i);
  }
  auto t2 = std::chrono::high_resolution_clock::now();

  for(int i=0; i<100000; ++i) {s2.emplace(i);
  }
  auto t3 = std::chrono::high_resolution_clock::now();

  std::cout << "insert:" 
    << std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count() 
    << "ms\n";

  std::cout << "emplace:"
    << std::chrono::duration_cast<std::chrono::milliseconds>(t3-t2).count()
    << "ms\n";
}

int main() {
  // 初始化 set
  std::set<std::string> cities = {"Beijing", "Shanghai", "Guangzhou"};

  // emplace 插入
  cities.emplace("Shenzhen");

  // 范围查找
  auto it1 = cities.lower_bound("H"); // "Guangzhou"
  auto it2 = cities.upper_bound("S"); // "Shanghai"

  // 批量删除 [H,S) 区间
  cities.erase(it1, it2);

  // 性能测试
  benchmark();

  return 0;
}