C++ STL

vector实现原理

vector是C++中最常用的容器之一，本质上是一个动态数组，支持快速随机访问和尾部插入/删除操作。

核心实现细节：

• 内存管理：
  • 维护三个指针：start、finish和end_of_storage
  • 容量(capacity)等于end_of_storage - start
  • 大小(size)等于finish - start
• 动态扩容：
  • 当元素数量达到容量上限时，分配更大的内存块（通常是当前容量的1.5倍或2倍）
  • 将现有元素复制或移动到新内存块
  • 释放旧内存

list实现原理

list是一个双向链表，提供O(1)复杂度的插入和删除操作，但不支持随机访问。

核心实现细节：

• 节点结构：
  • 每个节点包含数据和两个指针（前向和后向）
  • 通常实现为带哨兵节点的循环链表
• 内存管理：
  • 节点内存不连续，需要单独分配
  • 通常使用内存池技术优化频繁的内存分配和释放
• 迭代器：
  • 双向迭代器，支持++和--操作
  • 迭代器实际上封装了指向节点的指针

// list节点简化示例
template <typename T>
struct __list_node {
    __list_node* prev;
    __list_node* next;
    T data;
};

map/set实现原理

map和set通常基于红黑树实现，提供O(log n)的查找、插入和删除复杂度。

红黑树特性：

• 自平衡二叉搜索树
• 每个节点要么是红色，要么是黑色
• 根节点是黑色
• 红色节点的子节点必须是黑色
• 从任一节点到其叶子的所有路径都包含相同数目的黑色节点

unordered_map/set实现原理

无序关联容器基于哈希表实现，提供平均O(1)的查找、插入和删除复杂度。

核心实现细节：

• 哈希表结构：
  • 一个桶(bucket)数组
  • 每个桶维护一个链表，用于处理哈希冲突
• 哈希函数：将键映射到桶索引
• 再哈希(rehash)：
  • 当负载因子超过阈值时发生
  • 创建更多的桶并重新分配元素

// 哈希表插入操作伪代码
template <class Key, class Value>
void unordered_map<Key, Value>::insert(const pair<Key, Value>& kv) {
    if (load_factor() > max_load_factor())
        rehash();
    
    size_t bucket_index = hash_function(kv.first) % bucket_count();
    // 检查是否已存在
    for (auto& elem : buckets[bucket_index]) {
        if (elem.first == kv.first)
            return; // 键已存在，不插入
    }
    
    // 在对应桶的链表头部插入新元素
    buckets[bucket_index].push_front(kv);
    ++element_count;
}

算法类别

算法设计原则

• 泛型设计：通过模板参数接受任何满足要求的迭代器
• 效率优先：算法实现追求最佳时间和空间复杂度
• 标签分派技术：根据迭代器类别选择最优算法实现

排序算法实现示例

std::sort的实现通常基于内省排序(Introsort)，它结合了快速排序、堆排序和插入排序的优点：

// sort算法的简化实现
template<typename RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last) {
    if (first != last) {
        // 如果数据量足够大，使用内省排序
        introsort(first, last, log2(last - first) * 2);
        // 对小数组使用插入排序
        insertion_sort(first, last);
    }
}

template<typename RandomAccessIterator>
void introsort(RandomAccessIterator first, RandomAccessIterator last, int depth_limit) {
    while (last - first > threshold) {
        if (depth_limit == 0) {
            // 达到最大递归深度，切换到堆排序
            partial_sort(first, last, last);
            return;
        }
        depth_limit--;
        // 使用三数取中法选择枢轴
        auto pivot = median_of_three(first, first + (last-first)/2, last-1);
        // 进行快速排序的分区操作
        auto cut = partition(first, last, pivot);
        // 递归排序右半部分
        introsort(cut, last, depth_limit);
        // 迭代排序左半部分
        last = cut;
    }
}

STL的设计思想

• 泛型编程

  通过模板实现类型无关的代码，在编译时而非运行时实现多态，提高效率。

• 分离数据结构和算法

  数据结构(容器)专注于数据管理，算法专注于数据处理，迭代器作为两者的桥梁。

• 效率与抽象的平衡

  提供高层抽象的同时不牺牲效率，遵循零抽象惩罚原则(zero-overhead principle)。

STL实现中的优化技术