1 深入理解 STL GP 思维: Algorithm 利用 Iterator 操作 Container & iterator_traits
image.png
1 两种 Iterator
[1] native pointer
[2] smart ptr
2 STL 设计 `2 大 目标, 4 种 方法`
2大目标
`关联 type` 用于
[1] declare obj
[2] 作 return type`
4 种方法
————————————————————————————————————————————————————————————————————
[1] 函数模板 实参推导
限制: 无法解决 关联类型 作 return type
————————————————————————————————————————————————————————————————————
[2-4] class 型 Iterator (关联类型) +
`no-traits / iterator_traits 泛化 / iterator_traits 偏特化`
————————————————————————————————————————————————————————————————————
[2/3] 效果相同
限制: Iterator 不能为 native pointer
[3] dif with [2]
`为 Iterator class 声明 iterator_traits`
=> Iter::value_type 变为 iterator_traits<Iter>::value_type`
————————————————————————————————————————————————————————————————————
[4]
`Iterator 可为 native pointer`
dif with [3]
加 2个 iterator_traits 偏特化版本:T* 和 const T*
————————————————————————————————————————————————————————————————————
Note
1) simple Iterator + 单元素容器
阐述 Algorithm 如何利用 Iterator 操作 Container 中 element`
2) typename: `告诉 compiler 其所修饰的 name 是 type`
用途: declare obj 或 作 return type
3) `偏特化`
对 模板参数 `进一步限制`
4) const int* 通过
iterator_traits<T*> 取出 const int
iterator_traits<const T*> 取出 int
2 STL 6大部件 & Iterator Traits & OOP 与 GP & 容器 分类 和 关系
STL 6大部件.png
STL 6大部件: 例子.png
image.png
image.png
Iterator Traits.png
Iterator Traits.png
Iterator Traits.png
1 STL 体系结构 基础: STL 6大部件 (Components)
容器 Container : 即 数据结构
分配器 Allocator
算法 Algorithm
迭代器 Iterator
适配器 Adapter
仿函数 Functors / Function object
Data structures + Algorithms = Programs
(1) `容器` 放 data, data 要占 memory
(2) 容器 借助 `分配器` 解决掉 memory 问题
使 `client 不用 care memory`, 只需 往/从 容器中 放/取 东西即可
(3) 容器 是 `template class`
操作 data 的 `func 一些放 容器 里`;
`一些 以 telmplate function 独立出来`, 就是 `算法`
(4) 算法 处理 容器 中 的 data, 要借助
`迭代器`
这个 `泛化的 pointer`
(5) `适配器` : 适配 容器 / 迭代器 / 仿函数
(6) `仿函数` : 作用像 函数, 可保存 state
// eg
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
int array[5] = {3, 1, 5, 10, 8};
vector<int, allocator<int> > vec(array, array + 6);
cout << cout_if(vec.begin(), vec.end(),
not1( bind2nd( less<int>() , 6 ) ) ); // 大于等于: not1( less<T> )
return 0;
}
选哪种容器 取决于 data 的 分布特性
Note
前闭后开 区间
标准库 中用于表现 容器 的 头和尾
begin() : 头
end() : 尾 下一个位置
2 Iterator Traits
Traits: 从丢给它的东西中 提取出 想要的特征
Iterator 让算法知道要处理的 data scope
(1) 算法 问 Iterator: 你的 特征 是什么 ?`
1) class 型 Iterator 自己可以 回答
2) non-class / native pointer 型 Iterator 自己无法回答
借助 `中间层 ( 银弹 silver bullet )` Traits ( `偏特化` ) `替自己回答`
为 统一接口 -> class 型 Iterator 也 借助 Traits ( 泛化 ) 替自己回答
(2) Iterator Traits + 泛化 / 偏特化` 作用
1) 区分 Iterator 是 class 还是 native pointer,
区分 native ptr 指向 non-const 还是 const ( 是 T* / const T* )
2) 提取 class Iterator 5 种 关联类型
3) 提取 native pointer 的 value type
3 OOP vs. GP
data / 操作 data 的 func
均放 容器 - OO
放 容器 / 算法 - GP
=> OO 和 GP 思路不同
(1) OP 企图 把 data 和 method 关联起来
list 里有 sort
(2) GP 企图 把 data 和 methods 分开
sort 独立出来放在 Algorithms 中, 作 global func
::sort( c.begin(), c.end() );
Containers 和 Algorithms 团队可各自闭门造车,
其间以 Iterators 沟通 即可:
Algorithm 通过 Iterators 确定操作范围,
存/取 Container element
template <typename T>
inline const T&
min(const T& a, const T& b)
{
return b < a ? b : a;
}
Container: T 类型 怎么规定 < ?
由 T 自己决定
=> T 要 重载 `operator <`
Algorithm: min 不用关注 < 怎么实现
`STL Algorithm 中 sort 所用 Iterator` 要求 `随机存取 Iterator, list::iterator 不满足`
`所有 algrothms`, 其内 `最终涉及 元素本身` 的操作, 无非就是 `比大小`
4 容器 分类 和 关系
Gnu2.9.1 中很少有继承
class A 要用到 class B 功能: B 复合 / 继承 A
缩排容器间: 复合关系
set 中 has a rb_tree
3.1 vector
image.png
insert.png
insert.png
insert.png
序列式 容器
几乎任何 特定 data structure 都是为了
实现某种 特定 algorithm
STL容器 就是实现出 运用最广的一些 data structure
G4.9版 实现用了很多继承, 很复杂, 但不见得好
1 概述
(1) vector 是 动态 array, 当 满载 & 继续放元素 时, vector 会
另寻空间, 并 自动 2 倍 增长
每次扩充, 有大量的 copy ctor（旧 vector copy 到新 vector）
和 dtor ( 旧vector 元素)
(2) memory 中 不能在原地扩充
因为 vector 在 memory 某处产生后,
其后 memory 是否使用, 及 有多大 space 并不知道
所以, vector 自动扩充 时,
(1) 另寻一块 2 倍 的空间
(2) 把 旧空间元素 拷过去，新元素 紧随 旧元素 后面放
(3) 释放原空间
`重新配置, 移动数据, 释放原空间`
(3) 用 3 根 pointer 就可控制整个 vector: strat, finish, end_of_storage`**
sizeof( vector_obj ) = 3 * 4 = 12
2 source code
`任意容器, 若 空间(vector) / 逻辑(deque) 连续，就必须提供 operator []`**
vector 初始容量为 0 时, new_size 设为 1;
否则, 无法扩充
3 vector 的 iterator
vector 是 线性连续空间
=> 其 iterator 为 native ptr = T*
3.2 list
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
list 最具代表性
list 优势
(1) 插入/删除 1个 元素, 就 配置/释放 1个 元素空间
- 空间效率高
(2) 在指定 position 插入/删除, 通常是常数时间 - 时间效率高
Note: `prefix/postfix ++ 中 *this 不会唤起 operator* 的 3 种 情形`
(1) return *this;
return by reference => 不 唤起 什么
(2) self tmp = *this;
*this 作 arg of 作 copy ctor
(3) ++*this;
*this 作 arg of operator++
2 `operator-> 特性`
-> 作用下去( 即 调 operator->() ) 的 result,
继续用 -> 作用下去, 直到触及 a pointer to a build-in type
// construct list
std::list<Foo>::iterator iter
= list.begin();
iter->method(); // <=>
( &(*iter) )->method(); // <=>
(*iter).method(); // (*iter) is a Foo_obj
//------ clear / splice : easy
template <class T, class Alloc>
void list<T, Alloc>::
clear()
{
link_type cur_pnode = pnode->next;
while (cur_pnode != pnode)
{
link_type tmp = cur_pnode;
cur_pnode = cur_pnode->next;
destory_node(tmp);
}
pnode->next = pnode;
pnode->prev = pnode;
}
// 接合 splice = transfer + 适当区间
// 把 iter_scope [first, last) elem(s) 接合于 position 之前
// 其他 2 种重载 只要 转化为 区间形式即可
// 对 [iter, ++iter) / [list2.begin(), list2.end()) 用 transfer
template <class T, class Alloc>
void list<T, Alloc>::
splice(iterator position, iterator first, iterator last)
{
if(first != last)
transfer(position, first, last);
}
template <class T, class Alloc>
void list<T, Alloc>::
splice(iterator position, iterator iter)
{
// iter/next == position 时, do nothing
iterator next = ++iter;
if( iter == position || next == position)
return;
transfer(position, iter, next);
}
template <class T, class Alloc>
void list<T, Alloc>::
splice(iterator position, list& list2)
{
if( ! list2.empty() )
transfer(position, list2.begin(), list2.end());
}
//------ unique: 双指针
template <class T, class Alloc>
void list<T, Alloc>::
unique()
{
iterator current = begin();
iterator tail_off_one = end();
if (current == tail_off_one)
return;
iterator next = current;
while (++next != tail_off_one)
{
if (*next == *current)
erase(next);
else
current = next;
next = current;
}
}
//------ 3 merge list2 to list1: 5 iterator
// (1) 2对 [current, last) 形成 动态处理区间
// (2) list2 的 two iterator: next / current2 联动
template<class T, class Alloc>
void list<T, Alloc>::
merge(list<T, Alloc>& list2)
{
iterator current1 = begin();
iterator last1 = end();
iterator current2 = list2.begin();
iterator last2 = list2.end();
//(1) case1: list1/list2 都没 遍历完
while(current1 != last1 && current2 != last2)
{
if(*current2 < *current1)
{ // 3 steps
iterator next = current2;
transfer(current1, current2, ++next);
current2 = next;
}
else //=> list1 traverse_iter ++ : ready for the next loop to judge
++current1;
}
//(2) case2: list2/list1 遍历完/没遍历完(irst2 == last2 / first1 != last1),
// 则 merge 已完成
//(3) case3: list1/list2 遍历完/没遍历完,
// 则 transfer list2 剩余部分 到 list1.end() 之前
if(current2 != last2)
transfer(last1, current2, last2);
}
// reverse: 逐个 transfer [2th, end() ) elem to begin() 前
template<class T, class Alloc>
void list<T, Alloc>::
reverse()
{
//---1. list 有 0/1 个 node, do_nothing
if( pnode->next == pnode || (pnode->next)->next == pnode )
return;
iterator current = begin();
++current;
while(current != end() )
{
iterator current_old = current;
++current;
transfer(begin(), current_old, current);
}
}
// --- the most important func: not hard
template<class T, class Alloc>
void list<T, Alloc>::
transfer(iterator pos, iterator first, iterator last)
{
if(pos != last) // else do_nothing
{ // 7 steps
( *(*last.pnode).prev ).next = pos.pnode;
( *(*pos.pnode).prev ).next = first.pnode;
link_type tmp = (*first.pnode).prev;
(*first.pnode).prev = (*pos.pnode).prev;
(*pos.pnode).prev = (*last.pnode).prev;
tmp->next = last.pnode;
(*last.pnode).prev = tmp;
}
}
int main()
{
list<int> list1;
list1.push_back(1);
list1.push_back(2);
list1.push_back(3);
list<int> list2;
list2.push_back(4);
list2.push_back(5);
list2.push_back(6);
list<int>::iterator ite1_beg = list1.begin();
list<int>::iterator ite1_end = list1.end();
list<int>::iterator ite2_beg = list2.begin();
list<int>::iterator ite2_end = list2.begin();
list1.merge(list2);
for(ite1_beg = list1.begin();
ite1_beg != list1.end();
++ite1_beg)
std::cout << *ite1_beg << std::endl;
list1.reverse();
for(ite1_beg = list1.begin();
ite1_beg != list1.end();
++ite1_beg)
std::cout << *ite1_beg << std::endl;
}
5 重要算法图示
`transfer 思维 很重要`
transfer: other 算法 的 基础, 实现不难
position 与 [first, last) 可 属于 同一 list`
取成员 . 优先级 高于 解引用 *
3.3 deque 概述
image.png
image.png
image.png
image.png
image.png
1
(1) array vector deque 比较
array
线性连续空间
不能 动态增长
vector
线性连续空间
`向 尾端 动态增长`
重配空间/复制元素/释放原空间
单向开口
`尾`部 插入/删除 常数时间
deque
`线性 分段连续空间, 对外呈现 整体连续 的假象`
可 向两端 动态增长, 随时可增加 1个分段连续空间 并串接起来
双向开口: `头 和 尾` 插入/移除 常数时间
相同点
都可在 任意位置 插/删
(2) deque (vs. vector)
1) 头尾 插/删 均常数时间
2) 没 capacity 概念,
随时可增加一个 分段连续空间
3) iterator 为 随机型
iterator 复杂度高, 非必要, 尽量用 vector, 而非 deque
4) sort deque
copy 到 vector -> STL sort() -> 再 copy 回来
2 中控器 / map: 在 `分段连续 基础上, 维持 整体连续 的 假象`
(1) 中控器 memory blocks/nodes
1) node/map type 为 T*/T**
期望 指向 deque 某 buf / 中控器 memory 首 node T*
note: 这里的 node 是指 map blk_mem 的 elem
而不是 deque_iterator 的 mem data node(map_pointer/T**)
2) map memory 要增长时, map memory 据 deque 向左还是向右 增长,
另找一块 更大空间, map 随之指向 新空间 首 node
(2) 中控器 表示
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;
// 2 mem data: pointer to map memory / map_size
map_pointer map; // map : T**
size_type map_size;
};
(3) map 一侧 满载, 且要向 该侧增长时, 另找一块空间 作新 map
(4) 中控器 / buf / iterator 图`
deque<int, alloc, 8> deq; // 经一系列操作后有20个元素
3 iterator
deque 的 分段连续空间 / buf: deque 元素 的 存储空间
deque 有若干 大小相同的 分段连续空间 / buf
buf 大小 : 1个 buf 中 deque elem num
(1) iterator structure: 4 mem data`
1) 要能 `指向 current elem`
T* cur;
note:
`start / finish iterator: cur 指向 deque 第 1 有效元素 / last_off_by_one`
2) 要能 `指向` 所指 buf `边缘`
T* first
T* last
3) 要能 `判断` 自己`是否指向` 所指 buf `边缘`
cur == first cur == last
4) 指向 右 / 左边缘 (last / first) 时, 若 前进/后退,
要能 `跳到` the next / previous buf
map_pointer node; // node : T**
(2) iterator key behavior`
1) get buf_size
static size_t buffer_size()
{
deque_buf_size(BufSiz, sizeof(T));
}
若 iterator 指定 BufSiz, 则 取指定值;
否则, // 即 BufSiz = 0
若 deque 元素大小 sizeof(T) < 512, 取 512 / sizeof(T);
否则, 取 1
2) 跳到 new_node 指定 buf
void set_node(map_pointer new_node)
3) ++ --
self& operator++(); self& operator--()
`cur :`
`+1/-1 后/前 在 buf 右/左 边界, 则 跳到 next / previous buf 左/右边界 -> 更新 cur / 更新 cur 再 -1`
`记 每个 buf 为 [first, last)`
`cur ++ 前 必然没在 last, 否则, 遇 last 就跳已到 next buf`
1] ++cur
2] judge whether last
yes:
跳到 next buf
update cur = first
// cur -- 前 可能在 first
1] 先判 whether first
yes:
跳到 previous buf
update cur = last
2] --cur
4) += n
iterator 跳 n (= > < 0) 个 elem
self& operator+=(difference_type n)
4 deque data structure
(1) mem data
1) 要能 跳到指定 buf:
map_pointer map
2) 要能 向两侧 扩充 map
map_size 记住 current map size
3) 要能定位 第1 buf / tail_buf 的 第 1 elem / last_off_by_one
start / finish: 4 pointer
3.4 stack: LIFO
image.png
从 形象 角度看, deque 左 / 右 侧 为 front() / back(),
封掉 左侧 / 左进 + 右出,
且 只留 push pop top / push pop front back 3/4 种 operations
及 empty size 2个 simple func 即为 stack / queue`
1 stack 无 iterator
2 stack 定义
(1) 缺省情况下, stack 底层 data structure 为 deque
(2) stack 利用其 `底层容器` ( deque / list) 完成其 所有功能`,
因具有 `修改某物接口, 形成另一种风貌` 的性质
称 `adapter`
(3) stack obj non-const 时,
取出的 顶部元素是 reference, 可直接修改 之
template <class T, class Sequence = deque<T> >
class stack
{
friend bool operator== <> (const stack& const stack&); // 调 Sequence 的 operator==, 实现 略
friend bool operator< <> (const stack& const stack&);
protected:
Sequence c; // 底层容器 c
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
void push(const value_type& x)
{ c.push_back(x); }
void pop() { c.pop_back(); }
// 取顶部 reference
reference
top() { return c.back(); }
const_reference
top() const { return c.back(); }
// size() / empty
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
};
#include <stack>
#include <list>
#include <iostream>
#include <algorithm>
int main()
{
std::stack<int, std::list<int> > stk; // 以 list 作底层容器 的 stack
stk.push(1);
stk.push(5);
stk.push(10);
std::cout << stk.size() << std::endl; //3
std::cout << stk.top() << std::endl; //10
stk.pop();
std::cout << stk.size() << std::endl; //2
std::cout << stk.top() << std::endl; //5
stk.top() = 6;
stk.push(7);
stk.pop();
std::cout << stk.top() << std::endl; //6
}
3.5 queue: FIFO
image.png
3.6 set
1 2 点 与 map 相同
[1] key 各不相同
[2] 元素 据 key 自动排序
2 source code
set 函数 基本都是 转调 RB-tree 函数
pair<iterator, bool>
set<Key, Compare, Alloc>::insert(const value_type& x)
{
pair<typename rep_type::iterator, bool> p
= t.insert_unique(x);
return pair<iterator, bool>(p.first, p.second);
}
3.7 map
1 元素是 pair, pair.first/second 为 key / value
typedef pair<const Key, T> value_type;
用 map 迭代器 不可 / 可 修改 map 的 key / value
Note
map 的 iterator 既非 const iterator 也非 mutable iterator`
2 source code
// <stl_pair.h> 中 pair 的定义
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first; // note: public
T2 second;
pair() : first(T1()), second(T2()) { }
pair(const T1& a, const T2& b) : first(a), second(b) { }
};
下标操作符 operator[]
引用传递, 先据 key 找 value, 再 插
key 不存在/存在, 插入成功/失败,
`返回 pair.first = iterator` 指向 `目标 key` 的 `新/旧 elem`
[] 作左值 -> 写: 插入成功/失败 + 改写 vaule
[] 作右值 -> 读: 插入成功/失败 + 读 新 unknow_value / 旧 key 的 value`
4 适配器
1 容器 适配器
stack queue 都是 adapter
2 函数对象 adapter
(1) member
1) `mem data` 为 `要配接的 Operation 的 copy`
|
|/
less<int>()
2) 重载 operator()
调用 Operation copy 的 operator()
在 para 和 return value 上 动手脚
[1] 最灵活, 可 配接、配接、再配接
[2] 价值: `通过 它们之间的 `绑定、否定、组合 等`
几乎可 `无限制地` 创造出各种可能的 `表达式`, 搭配 `STL algorithms`
[3] `期望获得 配接能力 的 component, 本身必须 可配接`
1] `1 / 2 元 Functor` 必须继承自 `unary_function / binary_function`
2] `non-mem func` 必须以 `ptr_fun` 处理
3] `mem func` 必须以 `mem_fun 等` 处理
2.1 bind2nd()
函数调用运算符: operator() (...& arg1 ) { return op_copy(arg1, op_arg2_copy); }
|\
|
第 1 参数: Operation |
| binder2nd: 用 2 个 mem data 保存
| |\
| | 值传递 copy
| |
| + => 2 个实参 构造 binder2nd<OP> 并 return
|
强转为 Operation 第 2 形参类型
|\
|
|
第 2 参数: 要绑定的参数
2.2 用于 `non-mem 函数指针: ptr_fun`
ptr_fun 是 模板函数
para 是 函数指针 类型
return 函数对象 pointer_to_unary_function<Arg, Result>
|
|/
1] `wrap 函数指针`
|
|
|/
mem data 用于存 函数指针 的 copy
2] 函数调用运算符 operator()
`转调` 函数指针 copy 的 函数调用运算符 operator()
void
print(int value)
{
std::cout << value << ' ';
}
int main()
{
int a[3] = { 1,3,5 };
std::vector<int> vec(a, a + 3);
// interface
for_each(vec.begin(), vec.end(),
ptr_fun(&print) );
}
2.3 适配 `成员函数 指针` : `mem_fun / mem_fun_ref / mem_fun1 / mem_fun_ref`
结果是 作 `函数对象` 用, 以 搭配 GP algorithm
(1) 4 种函数
1) 带/不带 1: 有1个参数 / 无参
2) 带/不带 ref: ref/ptr 调 operator()
(2) 思想
wrap + 转调 operator()
(3) 应用: 用 `GP algorithm 实现 多态调用`
`GP 与 多态` 间 重要接轨
1] 容器 元素 A* 或 A&
2] 适配 `vf 指针`
std::vector<Shape*> vec;
// ...
for_each(vec.begin(), vec.end(), std::mem_fun( &Shape::display ) );
