4.2 vector
4.2.3 vector 的迭代器
vector维护的是连续线性空间，而且普通指针支持vector的随机存取特性，所以vector提供的是Random Access Iterators：
template<class T, class Alloc = alloc>class vector{typedef T value_type;typedef value_type* iterator; //vector的迭代器是普通指针};
4.2.4 vector 的数据结构
vector采用的数据结构是线性连续空间，用两个迭代器start和finish分别指向配置得来的连续空间中目前已被使用的范围，并用end_of_storage指向整块连续空间的尾端：
template<class T, class Alloc = alloc>class vector{...protected:iterator start;iterator finish;iterator end_of_storage;};
为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这就是capacity的概念。
4.2.5 vector 的构造和内存管理
vector默认使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为了更方便以元素大小为配置单位：
template<class T, class Alloc = alloc>class vector{protected:typedef simple_alloc<value_type, Alloc> data_allocator;...};
于是data_allocator::allocate(n)表示配置 n 个元素的空间。
vector提供许多构造函数，其中一个允许指定空间大小及初值：
vector(size_type n, const T& value){fill_initialize(n, value);}//填充并予以初始化void fill_initialize(size_type n, const T& value){start - allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;}//配置而后填充iterator allocate_and_fill(size_type n, const T& x){iterator result = data_allocator::allocate(n); //配置n个元素uninitialized_fill_n(result, n, x);return result;}
uninitialized_fill_n()会根据第一参数的型别特性，决定使用算法fill_n()或反复调用construct()
当使用push_back()将新元素插入vector尾部时，该函数首先检查是否还有备用空间：
- 如果尚还有备用空间就直接在备用空间上构造元素，并调整迭代器
finish，使vector变大； - 如果没有备用空间了，就扩充空间(此过程包含：重新配置、移动数据、释放原空间)：
```cpp
void push_back(const T& x){
if(finish != end_of_storage){
}elseconstruct(finish, x);++finish;
}insert_aux(end(), x);
template
iterator new_start = data_allocator::allocate(len); //实际配置iterator new_finish = new_start;try{//将原 vector 的内容拷贝到新 vectornew_finish = uninitialized_copy(start, position, new_start());//为新元素设定初值xconstruct(new_finish, x);//调整水位++new_finish;//将原vector的备用空间中的内容也拷贝过来(不知缘何)new_finish = uninitialized_copy(position, finish, new_finish);}catch(...){//commit or rollback 语义，要么全做完、要么一个不做destroy(new_start, new_finish);data_allocator::deallocator(new_start, len);throw;}//析构并释放原 vectordestroy(begin(), end());deallocate();//调整迭代器，指向新 vectorstart = new_start;finish = new_finish;end_of_storage = new_start + len;}
}
动态内存的增加，并不是在原空间之后接续新空间，因为**无法保证原空间之后尚有可配置空间**，而是**以原大小两倍另外配置一块较大的空间**，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。<br />**因此，对**`**vector**`**的任何操作一旦引起空间的重新配置，指向原**`**vector**`**的所有迭代器就都失效了**。**vector 的一些成员函数**<br />---<a name="iRlYC"></a># 4.3 list<a name="uTtFr"></a>## 4.3.2 list 的节点`list`本身和`list`的节点是不同的结构，需要分开设计。`list`节点结构如下：```cpptemplate<class T>struct __list_node{typedef void* void_pointer;void_pointer prev;void_pointer next;T data;};
4.3.3 list 的迭代器
list不再能像vector一样以普通指针作为迭代器，因此其节点不保证处于连续空间。list迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。又由于list是一个双向链表，迭代器必须具备前移、后移的能力，所以list的迭代器是Bidirectional Iterator。
插入与接续都不会造成原有的**list**迭代器失效。而**list**的元素删除操作只有指向被删除元素的那个迭代器失效，其他迭代器不受影响。
4.3.4 list 的数据结构
SGI list 不仅是一个双向链表，还是一个环状双向链表，所以只需要一个指针就可以完整表现整个链表。
template<class T, class Alloc = alloc>class list{protected:typedef __list_node<T> list_node;public:typedef list_node* link_type;protected:link_type node; //只要一个指针，便可表示整个环状双向链表};
如果让指针node指向刻意置于尾端的一个空白节点，node便能符合 STL 对于前闭后开区间的要求，成为last迭代器
于是以下几个函数都可以轻易完成：
iterator begin(){return (link_type)((*node).next);}iterator end(){return node;}bool empty()const{return node->next == node;}size_type size()const{size_type result = 0;distance(begin(), end(), result);return result;}reference front(){return *begin();}reference back(){return *(--end());}
4.3.5 list 的构造和内存管理
看书，不记笔记了。。
4.4 deque
vector是单向开口的连续线性空间，deque是一种双向开口的连续线性空间。
deque与vector的差异：
deque允许在常数时间内对头端进行元素的插入或移除操作deque没有容量观念，因为是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。不像vector需要重新配置一块更大的空间，然后复制元素再释放旧空间。所以deque也没有必要提供空间保留功能(reserve)。
deque也提供Random Access Iterator，但是它的迭代器并不是普通指针，其复杂度与vector不可媲美。因此应尽可能使用vector而不是deque。
4.4.2 deque 的中控器
deque是连续空间，是由一段一段的定量连续空间构成，一旦需要在**deque**的前端或尾端增加新空间，便配置一段定量的连续空间，串接在**deque**的头端或尾端。deque只是在这些分段的定量连续空间上维护了其整体连续的假象，并提供了随机存取的接口，避免了重新分配、赋值、释放的低性能，代价是复杂的迭代器架构。
deque采用一块**map**作为主控。此处的**map**是指一小块连续空间，其中的每个元素都是一个指针，指向另一段比较大的连续线性空间——缓冲区。缓冲区才是deque存储空间主体。SGI STL 允许指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。
template<class T, class Alloc = alloc, size_t BufSiz = 0>class deque{public:typedef T value_type;typedef value_type* pointer;...protected://元素的指针的指针typedef pointer* map_pointer;protected:map_pointer map; //指向map，map是块连续空间，其中每个元素都指向一块缓冲区size_type map_size; //map内可容纳多少指针};
其实map是一个T**，即它是一个指针的指针，第二个指针指向型别为T的一块空间：
4.4.5 deque 的迭代器
deque是分段连续空间，维持其整体连续假象的任务落在了迭代器的operator++和operator--两个云算子上。deque的迭代器需要：
- 能够指出缓冲区在哪里，
能够判断自己是否已经出于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了正确跳跃，
deque必须随时掌握中控器map。 ```cpp templatestruct deque_iterator{ //没有继承std::iterator typedef deque_iterator return __deque_buf_size(BufSiz, sizeof(T));
}
//由于未继承 std::iterator，所以必须自行撰写五个必要的迭代器相应型别 typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef T** map_pointer;
typedef __deque_iterator self;
//保持与容器的联结 T cur; //此迭代器所指是缓冲区中现行元素 T first; //此迭代器所指是缓冲区的头 T* last; //此迭代器所指是缓洪区的尾(含备用空间) map_pointer node; //指向管控中心的某个节点 … };
//buf_size()用于决定缓冲区大小，调用全局函数deque_buf_size() inline size_t deque_buf_size(size_t n, size_t sz){ return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1)); } //如果 n 不为0，传回n，表示 buffer_size 由用户自定义 //如果 n 为0，表示 buffer_size 使用默认值，那么 //如果 sz(元素大小，sizeof(value_type))小于512，传回512/sz //如果 sz不小于 512，传回1
<br />例如有一个`deque<int>`，其`start`和`end`迭代器布局如下：<br />---<a name="N8ja3"></a>## 4.4.4 deque 的数据结构`deque`除了维护一个指向`map`的指针外，也维护`start`，`finish`两个迭代器，分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)，此外，也必须**记住目前**`**map**`**的大小**，因为一旦`map`所提供的节点不足，就必须配置更大的一块`map`。<a name="Kb4sO"></a>##<a name="TDXAD"></a>## 4.4.5 deque 的构造与内存管理`deque`的**缓冲区扩充操作非常复杂**。以下逐步介绍：<br />`deque<int, alloc, 32> ideq(20, 9);`声明了一个`deque`，其缓冲区大小为 32bytes，并令其保留 20 个元素空间，每个元素初值为 9。为了指定`deque`的第三个模板参数(**缓冲区大小**)，必须将前两个参数都指明出来，因此必须明确指定`alloc`为空间配置器。`deque`自定了两个专属的空间配置器：```cppprotected://专属空间配置器，每次配置一个元素大小typedef simple_alloc<value_type, Alloc> data_allocator;//专属空间配置器，每次配置一个指针大小typedef simple_alloc<pointer, Alloc> map_allocator;//并提供一个构造函数deque(int n, const value_type& value):start(), finish(), map(0), map_size(0){fill_initialize(n, value);}//fill_initialize()负责产生并安排deque的结构，并设定好初值template<class T, class Alloc, size_t BufSize>void deque<T, Alloc, BufSize>::fill_initialize(size_type n, const value_type& value){create_map_and_nodes(n);map_pointerr cur;__STL_TRY{//为每个节点的缓冲区设定初值for(cur = start.node; cur < finish.node; ++cur)uninitialized_fill(*cur, *cur + buffer_size(), value);//最后一个节点设定稍有不同(因为尾端可能有备用空间，不用设定初值)uinitialized_fill(finish.first, finish.cur, value);}catch(...){...}}
其中create_map_and_nodes()负责产生并安排好deque的结构：
template<class T, class Alloc, size_t BufSize>void deque<T, alloc, BufSize>::create_map_and_nodes(size_type num_elements){//需要节点数 = (元素个数/每个缓冲区可容纳的元素个数) + 1//如果刚好整除，会多配一个节点size_type num_nodes = num_elements / buffer_size() + 1;//一个map要管理几个节点，最少8个，最多是“所需节点数 + 2”//前后各预留一个，扩充时可用map_size = max(initial_map_size(), num_nodes + 2);map = map_allocator::allocate(map_size);//以上配置出一个“具有map_size个节点”的map//以下令nstart和nfinish指向map所拥有的全部节点的最中央区段//保持在最中央，可使头尾两端的扩充能量一样大。每个节点可对应一个缓冲区map_pointer nstart = map + (map_size - num_nodes) / 2;map_pointer nfinish = nstart + num_nodes - 1;map_pointer cur;__STL_TRY{//为map内的每个现用节点配置缓冲区，所有缓冲区加起来就是deque的可用空间for(cur = nstart; cur <= nfinish; ++cur)*cur = allocate_node();}catch(...){}//为deque内的两个迭代器start和end设定正确内容start.set_node(nstart);finish.set_node(nfinish);start.cur - start.first;finish.cur = finish.first + num_elements % buffer_size();}
当尾端插入元素时，缓冲区的大小仍然充足，那么就不会引起缓冲区的再配置，此时的deque状态：
以下是push_back()函数内容：
public:void push_back(const value_type& t){if(finish.cur != finish.last - 1){construct(finish.cur, t);++finish.cur;}elsepush_back_aux(t);}
如果在缓冲区容量不足的情况下，再添加元素到尾端，那么push_back()会调用push_back_aux()，先配置一整块新的缓冲区，再设置新元素内容，然后更改迭代器finish的状态：
//只有当finihs.cur == finish.last - 1时才会调用//即，只有当最后一个缓冲区只剩一个备用元素空间时才会被调用template<class T, class Alloc, size_t BufSize>void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t){value_type t_type = t;reserve_map_at_back(); //若符合某种条件则必须重换一个map*(finish.node + 1) = allocate_node(); //配置一个新节点(缓冲区)__STL_TRY{construct(finish.cur, t_copy); //针对当前元素设值finish.set_node(finish.node + 1); //使finish指向新节点finish.cur = finish.first; //设定finish的内部属性}STL_UNWIND(deallocate_node(*(finish.node + 1)));}
在deque前端插入新元素的情况与在后端插入类似。
有两个函数用于判断何时map需要重新调整：
reserve_map_at_back()reserve_map_at_front()
实际操作则由reallocate_map()执行：
void reserve_map_at_back(size_type nodes_to_add = 1){if(nodes_to_add + 1 > map_size - (finish.node - map))//如果map尾端的节点备用空间不足//符合以上条件必须重换一个map(配置过程与vector扩容过程类似)reallocate_map(nodes_to_add, false);}void reserve_map_at_front(size_type node_to_add = 1){//如果map前端的节点备用空间不足//符合以上条件则必须重换一个mapreallocate_map(nodes_to_add, true);}template<class T, class Alloc, size_t BufSize>void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,bool add_at_front){size_type old_num_nodes = finish.node - start.node + 1;size_type new_num_nodes = old_num_nodes + nodes_to_add;map_pointer new_nstart;if(map_size > 2 * new_num_nodes){new_nstart = map + (map_size - new_num_nodes) / 2+(add_at_front ? nodes_to_add : 0);if(new_nstart < start.node)copy(start.node, finish.node + 1, new_nstart);elsecopy_backward(start.node, finish.node + 1, new_nstart + old_num_node);}else{size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;//配置一块空间，准备给新map使用map_pointer new_map = map_allocator::allocate(new_map_size);new_nstart = new_map + (new_map_size - new_num_nodes) / 2+(add_at_front ? node_to_add : 0);//把原map内容拷贝过来copy(start.node, finish.node + 1, new_nstart);//释放原mapmap_allocator::deallocate(map, map_size);//设定新map的起始地址和大小map = new_map;map_size = new_map_size;}//重新设定迭代器start和finishstart.set_node(new_nstart);finish.set_node(new_nstart + old_num_nodes - 1);}
4.4.6 deque 的元素操作
不记笔记了 看书。。
若有收获，就点个赞吧
0 人点赞
