Giao diện
⚡ Performance Analysis — Big O
Hiểu Time Complexity của mỗi operation giúp bạn chọn đúng container cho từng use case.
Big O Refresher
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Array access, hash lookup |
| O(log n) | Logarithmic | Binary search, balanced tree |
| O(n) | Linear | Linear search, iteration |
| O(n log n) | Linearithmic | Efficient sorting |
| O(n²) | Quadratic | Nested loops |
┌─────────────────────────────────────────────────────────────────┐
│ TIME COMPLEXITY GROWTH │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Operations │ │
│ ▲ │ O(n²) │
│ │ │ / │
│ │ │ / │
│ │ │ O(n log n) │
│ │ │ / │
│ │ │ O(n) │
│ │ │ /───────────── │
│ │ │ O(log n) │
│ │ │ ────────────── │
│ │ │ O(1) │
│ │ ├──────────────────────────────────────────▶ │
│ │ n (elements) │
│ │
└─────────────────────────────────────────────────────────────────┘Sequence Containers
std::vector
| Operation | Complexity | Note |
|---|---|---|
operator[], at() | O(1) | Random access |
push_back() | O(1) amortized | Occasional O(n) reallocation |
pop_back() | O(1) | |
insert() at end | O(1) amortized | |
insert() at middle | O(n) | Shift elements |
erase() at end | O(1) | |
erase() at middle | O(n) | Shift elements |
find() (unsorted) | O(n) | Linear search |
find() (sorted) | O(log n) | With std::binary_search |
size(), empty() | O(1) |
std::deque
| Operation | Complexity | Note |
|---|---|---|
operator[], at() | O(1) | Random access |
push_front() | O(1) | ✅ Better than vector |
push_back() | O(1) | |
pop_front() | O(1) | ✅ Better than vector |
pop_back() | O(1) | |
insert() at middle | O(n) |
std::list (Doubly Linked)
| Operation | Complexity | Note |
|---|---|---|
| Access by index | O(n) | ❌ No random access |
push_front/back() | O(1) | |
pop_front/back() | O(1) | |
insert() at iterator | O(1) | ✅ No shifting |
erase() at iterator | O(1) | ✅ No shifting |
find() | O(n) | |
splice() | O(1) | Move elements between lists |
Associative Containers
std::map / std::set (Red-Black Tree)
| Operation | Complexity |
|---|---|
insert() | O(log n) |
erase() | O(log n) |
find() | O(log n) |
operator[] | O(log n) |
lower_bound() | O(log n) |
iteration | O(n) sorted |
std::unordered_map / std::unordered_set (Hash Table)
| Operation | Average | Worst |
|---|---|---|
insert() | O(1) | O(n) |
erase() | O(1) | O(n) |
find() | O(1) | O(n) |
operator[] | O(1) | O(n) |
📌 Worst Case
Worst case O(n) xảy ra khi nhiều keys collide vào cùng bucket. Với good hash function, gần như không xảy ra.
Container Comparison Matrix
┌────────────────────────────────────────────────────────────────────────┐
│ CONTAINER SELECTION GUIDE │
├────────────────────────────────────────────────────────────────────────┤
│ │
│ Need random access? │
│ YES ─────► vector, deque, array │
│ NO ─────► Need fast insert/delete at middle? │
│ YES ─────► list │
│ NO ─────► vector (still good) │
│ │
│ Need key-value? │
│ YES ─────► Need sorted keys? │
│ YES ─────► map │
│ NO ─────► unordered_map (faster!) │
│ NO ─────► Need unique elements? │
│ YES ─────► set / unordered_set │
│ NO ─────► vector │
│ │
│ Need LIFO/FIFO? │
│ LIFO ─────► stack │
│ FIFO ─────► queue │
│ Priority ───► priority_queue │
│ │
└────────────────────────────────────────────────────────────────────────┘Comprehensive Comparison Table
| Container | Access | Insert Begin | Insert End | Insert Mid | Erase | Find |
|---|---|---|---|---|---|---|
vector | O(1) | O(n) | O(1)* | O(n) | O(n) | O(n) |
deque | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
list | O(n) | O(1) | O(1) | O(1)† | O(1)† | O(n) |
array | O(1) | - | - | - | - | O(n) |
set | - | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
map | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
unordered_set | - | O(1)‡ | O(1)‡ | O(1)‡ | O(1)‡ | O(1)‡ |
unordered_map | O(1)‡ | O(1)‡ | O(1)‡ | O(1)‡ | O(1)‡ | O(1)‡ |
* Amortized
† Với iterator đã có
‡ Average case
Real-world Benchmarks
cpp
#include <vector>
#include <list>
#include <set>
#include <unordered_set>
#include <chrono>
#include <iostream>
template<typename Container>
void benchmark(const std::string& name, int n) {
Container c;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < n; ++i) {
c.insert(c.end(), i);
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << name << ": " << duration.count() << " μs" << std::endl;
}
int main() {
const int N = 100000;
benchmark<std::vector<int>>("vector", N);
benchmark<std::list<int>>("list", N);
benchmark<std::set<int>>("set", N);
return 0;
}Typical Results (insert 100k elements):
vector: 1,200 μs ← Usually fastest due to cache
list: 8,500 μs ← Node allocations slow
set: 12,000 μs ← Tree rebalancing📌 Key Insight
std::vector thường nhanh hơn expected vì cache-friendly. Contiguous memory = fewer cache misses.
When to NOT Use Default
| Situation | Instead of vector, use... |
|---|---|
| Frequent insert/delete at front | std::deque |
| Frequent insert/delete in middle | std::list (nếu không cần random access) |
| Need unique elements sorted | std::set |
| Need fast key lookup | std::unordered_map |
| Fixed size known at compile time | std::array |
| Threads sharing access | Consider std::list (stable iterators) |
📚 Tổng kết
| Principle | Guideline |
|---|---|
| Default choice | std::vector |
| Key-value fast | std::unordered_map |
| Key-value sorted | std::map |
| Unique elements | std::set or std::unordered_set |
| Cache matters | Contiguous containers win |
| Measure, don't guess | Profile real workloads |
➡️ Tiếp theo
Tiếp theo: Iterators — Abstraction for traversing containers.