Complexity Contract：STL API 的隐藏“性能接口” | STL

本章覆盖：Big-O；amortized complexity；average complexity；worst-case complexity；complexity guarantee 是 API contract 的一部分；`vector::push_back` 摊还常数；`map::find` 对数复杂度；`unordered_map::find` 平均常数；“O(1)”不代表一定比“O(log n)”快；常数因子、cache、allocation 同样重要。

本章知识点

  • Big-O
  • amortized complexity
  • average complexity
  • worst-case complexity
  • complexity guarantee 是 API contract 的一部分
  • vector::push_back 摊还常数
  • map::find 对数复杂度
  • unordered_map::find 平均常数
  • “O(1)”不代表一定比“O(log n)”快
  • 常数因子、cache、allocation 同样重要