C++ STL STRING的COPY-ON-WRITE技术

STL六大组件：

• 容器(Container)， 存放数据

• 分配器(Allocators)， “幕后英雄”， 为容器分配内存。allocator版本底层调用operator new, new调用malloc

• 迭代器(Iterators)，操作数据
• 算法(Algorithms)，操作数据的规则
• 适配器(Adapters), 比如deque,stack
• 仿函数(Functors)

1
2
3
4
5
6
7
8
9

int main () {
    int ia[6] = {27, 210, 12,47,109,83};
    vector<int, allocator<int>> vi(ia, ia+6);

    cout << count_if(vi.begin(), vi.end(), 
                     not1(bind2nd(less<int>(), 40)));

  return 0;
}

容器：

• 顺序容器:
  • array： size固定，不可扩充
  • vector：size不固定，可向后扩充
  • deque: size不固定，可向前，向后扩充
  • list: size不固定，内存不连续
• 关联容器: map/unordered_map, set/unordered_set

OOP vs GP

• OOP: 将data和method关联在一起
• GP: 将data和method分开

GP：

• Container和Algorithm团队各自开发，通过iterator沟通即可。
• Algorithms通过iterator确定操作范围，然后取用Container元素。

介绍下STL（vector, map等，内存分配等角度）

主要是通过GP(Generic Programming)实现

迭代器，空间配置器理解

map如何实现的

map里如何正确删除元素（注意iterator失效问题）

list和vector实现的区别

remove() vs erase()

STL容器空间配置器

vector的resize，reverse方法，迭代器什么情况下会失效（push_back时end失效，扩容时first, end失效, 删除操作会导致删除点开始之后的迭代器全部失效）

stl容器新增的实用方法