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 的内容拷贝到新 vector
new_finish = uninitialized_copy(start, position, new_start());
//为新元素设定初值x
construct(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;
}
//析构并释放原 vector
destroy(begin(), end());
deallocate();
//调整迭代器,指向新 vector
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}
动态内存的增加,并不是在原空间之后接续新空间,因为**无法保证原空间之后尚有可配置空间**,而是**以原大小两倍另外配置一块较大的空间**,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。<br />**因此,对**`**vector**`**的任何操作一旦引起空间的重新配置,指向原**`**vector**`**的所有迭代器就都失效了**。
**vector 的一些成员函数**<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/26389447/1658475941220-ea37ddb0-99af-472a-a40f-3623987618e0.png#clientId=ue764dc87-8788-4&crop=0&crop=0.1215&crop=1&crop=0.8611&from=paste&height=1093&id=u996b2579&margin=%5Bobject%20Object%5D&name=image.png&originHeight=1640&originWidth=2360&originalType=binary&ratio=1&rotation=0&showTitle=false&size=208382&status=done&style=none&taskId=u974f4f36-02b3-4f91-9382-5f688b3e4cc&title=&width=1573)
---
<a name="iRlYC"></a>
# 4.3 list
<a name="uTtFr"></a>
## 4.3.2 list 的节点
`list`本身和`list`的节点是不同的结构,需要分开设计。`list`节点结构如下:
```cpp
template<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 iterator; typedef __deque_iterator const_iterator; static size_t buffer_size(){ 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
![image.png](https://cdn.nlark.com/yuque/0/2022/png/26389447/1658562178371-21125fc1-ebf4-4db6-b062-a08f79725288.png#clientId=uea2aa39c-7c47-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=402&id=u754b5efc&margin=%5Bobject%20Object%5D&name=image.png&originHeight=502&originWidth=803&originalType=binary&ratio=1&rotation=0&showTitle=false&size=62490&status=done&style=none&taskId=u03ba0bd1-9a64-40d1-8ee7-a12672e1749&title=&width=642.4)<br />例如有一个`deque<int>`,其`start`和`end`迭代器布局如下:<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/26389447/1658562725252-16ce4fc2-0a56-4bcc-9add-a62141c5a933.png#clientId=uea2aa39c-7c47-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=490&id=u7399ce9c&margin=%5Bobject%20Object%5D&name=image.png&originHeight=613&originWidth=909&originalType=binary&ratio=1&rotation=0&showTitle=false&size=100964&status=done&style=none&taskId=u6690e948-bf64-4fe7-83a5-729315302d8&title=&width=727.2)
---
<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`自定了两个专属的空间配置器:
```cpp
protected:
//专属空间配置器,每次配置一个元素大小
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;
}else
push_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前端的节点备用空间不足
//符合以上条件则必须重换一个map
reallocate_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);
else
copy_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);
//释放原map
map_allocator::deallocate(map, map_size);
//设定新map的起始地址和大小
map = new_map;
map_size = new_map_size;
}
//重新设定迭代器start和finish
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
4.4.6 deque 的元素操作
不记笔记了 看书。。