1 深入理解 STL GP 思维: Algorithm 利用 Iterator 操作 Container & iterator_traits
image.png
1 两种 Iterator
[1] native pointer
`无需 单独定义 Iterator class/type`
// vector iterator: T*
template <class T, class Alloc = alloc>
class vector
{
public:
typedef T value_type;
typedef value_type* iterator;
};
[2] smart ptr
has internal native ptr to specified type
// list Iterator
template <class T>
struct _list_iterator
{
typedef _list_node<T>* link_type;
link_type pnode;
};
// list
template <class T, class Alloc = alloc>
class list
{
public:
typedef _list_iterator<T> iterator;
};
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
3 例子
// 方法 1
#include <iostream>
template <class Iter, class T>
void f_impl(Iter iter, T t) // => para Iter/T: int*/int
{
*iter = 2; // t 是 *iter 旧值 的 copy => t 不变
T tmp;
tmp = 2 * t;
std::cout << *iter << ' ' << tmp << std::endl; // 2 2
}
template<class Iter>
inline void f(Iter iter) // => para Iter: int*
{
f_impl(iter, *iter);
}
int main()
{
int val = 1;
f(&val); // arg: int*
}
// 方法 2
//--- 1. Complex.h
// elem_type of container(of single elem)
#include <iostream>
class Complex
{
private:
int x;
int y;
public:
Complex(): x(0), y(0) {}
Complex(int x1, int y1): x(x1), y(y1) { }
int getReal() const { return x; }
int getImag() const { return y; }
};
std::ostream&
operator << (std::ostream& os, const Complex& c){
return os << c.getReal() << ',' << c.getImag();
}
//--- 2. Iter.h
template<class T>
struct Iter
{
// 1) associated type
typedef T value_type;
// 2) mem data: internal ptr
// note: associated type declare obj
value_type* ptr;
// 3) ctor
Iter(value_type* p = 0)
: ptr(p) { }
// 4) behavior
value_type&
operator* () const { return *ptr; }
};
//--- 3. Alog.h
template <class Iter>
typename Iter::value_type //note: associated type as return type of func
getElem(Iter iter)
{
return *iter;
}
//--- 4. client.cpp
#include "Complex.h"
#include "Iter.h"
#include "Algo.h"
int main ()
{
//(1) iterator point to elem of container(of single elem)
Iter<Complex> iter( new Complex(1,2) );
//(2) algorithm + iter -> operate container
std::cout << getElem(iter)<< std::endl; // 1, 2
}
// 方法 3
//--- 2. Iter.h
template<class T>
struct Iter
{
// 1) associated type
typedef T value_type;
// 2) mem data: internal ptr
// associated type declare obj
value_type* ptr;
// 3) ctor
Iter(value_type* p = 0)
: ptr(p) { }
// 4) behavior
value_type&
operator* () const { return *ptr; }
};
// dif with 2: 为 Iterator class 声明 iterator_traits
template <class Iter>
struct iterator_traits
{
typedef typename Iter::value_type value_type;
};
//--- 3. Alog.h
// difference2: Iter::value_type 变为 iterator_traits<Iter>::value_type
template <class Iter>
typename iterator_traits<Iter>::value_type //note: associated type as return type of func
getElem(Iter iter)
{
return *iter;
}
// 方法 4
//--- 2. Iter.h
template<class T>
struct Iter
{
// 1) associated type
typedef T value_type;
// 2) mem data: internal ptr
// associated type declare obj
value_type* ptr;
// 3) ctor
Iter(value_type* p = 0)
: ptr(p) { }
// 4) behavior
value_type&
operator* () const { return *ptr; }
};
iterator_traits
template <class Iter>
struct iterator_traits
{
typedef typename Iter::value_type value_type;
};
// dif with 3: 2个 traits 偏特化版本: T* 和 const T*
template <class T>
struct iterator_traits<T*>
{
typedef T value_type;
};
template <class T>
struct iterator_traits<const T*>
{
typedef T value_type;
};
//--- 4. client.cpp
#include "Complex.h"
#include "Iter.h"
#include "Algo.h"
int main ()
{
//(1)Iterator 为 smart pointer -> iterator_traits 泛化
Iter<Complex> iter( new Complex(1,2) );
std::cout << getElem(iter)<< std::endl;
//(2)Iterator 为 native pointer -> iterator_traits 偏特化
Complex* pComplex = new Complex(1,2);
std::cout << getElem(pComplex)<< std::endl;
}
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
0 概述
Alexander Stepanov 发现
`算法 不依赖` 于 `数据结构 的 特定实现`,
而 仅仅依赖于 数据结构 的一些 `基本语义属性`,
在此基础上 `构建出 STL`
C++ 标准库 75%左右是 STL,
标准库以 header files 形式呈现
STL之父访谈录
重要网站
www.cpluscplus.com
https://en.cppreference.com/w/
https://gcc.gnu.org
GNU : GNU's Not Unix
类 Unix 设计
GPL: General Public License 广泛开放授权
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;
否则, 无法扩充
#include <iostream>
#include <algorithm> // std::copy_backward / std::max
#include <memory> // std::allocator / std::uninitialized_copy 等 3个func / std::destroy
#include <new.h> // placement new
//------ 1. construct + destory
template <class T>
void
construct(T* p, const T& value)
{
// placement new: 调 copy ctor / T::T(value)
new(p) T(value);
}
// destory 2 个 版本:
// destory an elem /
// elems of a scope(mot std version)
template <class T>
void
destory(T* p)
{
p->~T(); // call dtor
}
template <class ForwardIterator>
void
destory(ForwardIterator first,
ForwardIterator last)
{
for (; first != last; ++first)
destory(&*first);
}
//------ 2. simple_alloc
template<class T, class Alloc>
class simple_alloc
{
public:
static T*
allocate(size_t elem_num)
{
return 0 == elem_num ? 0 :
(T *) Alloc().allocate(elem_num * sizeof(T));
}
static void
deallocate(T* p, size_t elem_num)
{
if (elem_num != 0)
Alloc().deallocate(p, elem_num * sizeof(T));
}
};
//------ 3. vector
template<class T, class Alloc = std::allocator<T> >
class vector
{
public:
//(1) 5 associated type
typedef T value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
//(2) typedef iterator type: T*
typedef value_type* iterator;
protected:
//(3) typedef allocator type
typedef simple_alloc<value_type, Alloc> data_allocator;
//(4) mem data: three pointers to manage vector
iterator start;
iterator finish;
iterator end_of_storage;
//------protected func
//(1) set three pointer to vector
void allocate_fill_init(size_type elem_num, const T& value)
{
start = allocate_fill(elem_num, value);
finish = start + elem_num;
end_of_storage = finish;
}
iterator allocate_fill(size_type elem_num, const T& x)
{
iterator iter = data_allocator::allocate(elem_num);
std::uninitialized_fill_n(iter, elem_num, x);
return iter;
}
//(2) free/释放 vector memory space
void deallocate()
{
if (start)
data_allocator::deallocate(start, size() );
}
//(3) for push_back to use
void insert_aux(iterator position, const T& x);
public: //--- interface
//(1) ctor
//1) default
vector() : start(0), finish(0), end_of_storage(0) { }
//2) elem_num + initialized_value
vector(size_type elem_num, const T& value)
{
allocate_fill_init(elem_num, value);
}
//3) elem_num
explicit vector(size_type elem_num)
{
allocate_fill_init(elem_num, T() );
}
//(2) dtor
~vector()
{
::destory(start, finish);
deallocate();
}
//(3) size/capacity/is_empty
// size() 直接调 begin() end() 实现,
// 好处: 无论 begin() end() 如何定义, size() 实现不变
size_type
size()
{ return size_type( end() - begin() ); }
size_type
capacity()
{ return size_type( end_of_storage - begin() ); }
bool
empty()
{ return begin() == end(); }
//(4) get head/tail iterator
iterator
begin() { return start; }
iterator
end() { return finish; }
//(5) get reference to head/tail/n_th elem
reference
front() { return *begin(); }
reference
back() { return *( end() - 1); }
reference
operator[](size_type index)
{ return *( begin() + index ); }
//(6) push_back(insert into tail + call insert_aux)
void
push_back(const T& x)
{
if (finish != end_of_storage)
{
::construct(finish, x);
++finish;
}
else // fuul load + insert
insert_aux(end(), x);
}
// pop_back
// remove tail elem + ，并调整大小
void
pop_back()
{
--finish;
::destory(finish);
}
//(7) erase elem in position
iterator
erase(iterator position)
{
if (position + 1 != end() )
// move forward(前移) the latter(后面的) elems
std::copy(position + 1, finish, position);
--finish;
::destory(finish);
return position;
}
// erase elems in [first, last)
iterator
erase(iterator first, iterator last);
//(8)
void
insert(iterator position, size_type elem_num, const T& x);
};
//(9)
template <class T, class Alloc>
void vector<T, Alloc>::
insert_aux(iterator position, const T& x)
{
// not full load
if (finish != end_of_storage)
{
//(1) construct tail elem with the front elem
::construct(finish, *(finish - 1) );
//(2) finish updated
++finish;
//(3) move elem: finish - 3, ..., pos -> finish - 2, ..., pos + 1
// copy_back: [pos, finish - 2) -> [ , finish - 1)
std::copy_backward(position, finish - 2, finish - 1);
//(4) fill position_th elem
T x_copy = x;
*position = x_copy;
}
else // full load
{
const size_type
old_size = size();
const size_type
new_size = old_size != 0 ? 2 * old_size : 1;
// (1) allocate new_size elems
iterator new_start = data_allocator::allocate(new_size);
iterator new_finish = new_start;
try
{
//(2) move old elem + insert_elem to new space
// 1) fill before position , [start, position) -> [new_start, new_start + position - start = new_finish)
new_finish = std::uninitialized_copy(start, position, new_start);
// 2) fill position, position -> new_finish
::construct(new_finish, x);
// 3) fill after position , [position, finish) -> [..., ...]
++new_finish;
new_finish = std::uninitialized_copy(position, finish, new_finish);
}
catch (...)
{
::destory(new_start, new_finish);
data_allocator::deallocate(new_start, new_size);
throw;
}
// (3) destory & free old vec space
::destory(begin(), end() );
deallocate();
// (4) modify three pointers to manage new vector space
start = new_start;
finish = new_finish;
end_of_storage = new_start + new_size;
}
}
template <class T, class Alloc>
void vector<T, Alloc>::
insert(iterator position, size_type insert_num, const T& x)
{
if (insert_num != 0)
{
//(1) left_space_size >= insert_bun
if ( size_type(end_of_storage - finish) > insert_num)
{
T x_copy = x;
const size_type elem_num_after_pos = finish - position;
iterator old_finish = finish;
// 利用 9 大 memory func: move elems of scope
// note: std::copy_backward is flexible
if (elem_num_after_pos > insert_num)
{
std::uninitialized_copy(finish - insert_num, finish, finish);
finish += insert_num;
std::copy_backward(position, old_finish - insert_num, old_finish);
std::fill(position, position + insert_num, x_copy);
}
else // <
{
std::uninitialized_fill_n(finish, insert_num - elem_num_after_pos, x_copy);
finish += (insert_num - elem_num_after_pos);
std::uninitialized_copy(position, old_finish, finish);
finish += elem_num_after_pos;
std::fill(position, old_finish, x_copy);
}
}
else //(2) left_space_size < insert_bun => space not enough
{
// size of new scope has different strategy
const size_type old_size = size();
const size_type new_size = old_size + std::max(old_size, insert_num);
iterator new_start = data_allocator::allocate(new_size);
iterator new_finish = new_start;
new_finish = std::uninitialized_copy(start, position, new_start);
new_finish = std::uninitialized_fill_n(new_finish, insert_num, x);
new_finish = std::uninitialized_copy(position, finish, new_finish);
::destory(start, finish);
deallocate();
start = new_start;
finish = new_finish;
end_of_storage = new_start + new_size;
}
}
}
int main()
{
vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
// iter -> 3
vector<int>::iterator iter = vec.begin() + 2;
vector<int>::iterator iter1;
for (iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
{
std::cout << *iter1 << ' ';
std::cout << std::endl;
}
vec.insert(iter, 2, 6);
for (iter1 = vec.begin(); iter1 != vec.end(); ++iter1)
{
std::cout << *iter1 << ' ';
std::cout << std::endl;
}
}
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 插入/删除, 通常是常数时间 - 时间效率高
1 G2.9 版本 可改进 处
标准库团队也不见得都是神, 可能也有设计不合理的地方,
所以 才会一直演进.
同样, 新版本 也不见得一定比 旧版本好
G4.9 里 不合理的继承 就显得乱七八糟
(1) list node pointer 域 必然指向 另一 list node
=> prev/next pointer 没必要用 void*, 使用时 还要转型
// G2.9
template <class T>
struct _list_node
{
typedef void* void_pointer;
void_pointer prev;
void_pointer next;
T data;
};
// 改进后
template <typename T>
struct _list_node
{
_list_node<T>* prev;
_list_node<T>* next;
T data;
};
(2) iterator template para 只用1个 elem type T 即可
第 2/3 template para: Ref / Ptr == T& / T*
//G2.9
template <class T, class Ref, class Ptr>
struct _list_iterator
{
//(1) 5 associated type
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef Ptr pointer;
typedef Ref reference;
//(2) typedef self alias(别名)
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, Ref, Ptr> self;
//(3) typedef list_node pointer type
typedef _list_node<T>* link_type;
//(4) 只 1 个 mem data: a native pointer to list_node
link_type pnode;
};
// 改进 version
template <class T>
struct _list_iterator
{
//(1) 5 associated type
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//(2) typedef self alias
typedef _list_iterator<T> iterator;
typedef _list_iterator<T> self;
//(3) typedef list_node pointer type
typedef _list_node<T>* link_type;
//(4) only one mem data: a native pointer to list_node
link_type pnode;
};
`实际上 G4.9 中就做了上述改进`
2 list node 的 data structure -> 构成 双向链表
template <typename T>
struct _list_node
{
_list_node<T>* prev;
_list_node<T>* next;
T data;
};
3 list iterator 的 data structure
`manage list iterator: 只需要 1 根 node pointer`
// 改进 version
template <class T>
struct _list_iterator
{
//(1) 5 associated type
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//(2) typedef self alias
typedef _list_iterator<T> iterator;
typedef _list_iterator<T> self;
//(3) typedef list_node pointer type
typedef _list_node<T>* link_type;
//(4) only one mem data: a native pointer to list_node
link_type pnode;
//--- mem func
// (1) ctor
// 1) default
_list_iterator() { }
// 2) para type: pointer to list_node
_list_iterator(link_type p) : pnode(p) { }
// (2)copy ctor, para: iterator
_list_iterator(const iterator& iter)
: pnode(iter.pnode) { }
// (3) == !=
bool operator==(const self& iter) const
{ retrun pnode == iter.pnode; }
bool operator!=(const self& iter) const
{ retrun pnode != iter.pnode; }
// (4) * ->
reference operator* () const
{ return (*pnode).data; }
// pnode is pointer => 可用 *p == p_obj
// 再用 mem operator .
// operator-> call operator*
pointer operator-> () const
{ return &( operator*() ); }
// (5) prefix ++
self& operator++()
{
pnode = (link_type)( (*pnode).next );
return *this;
}
// postfix ++
self operator++(int)
{
self tmp = *this;
++*this; // call prefix ++
return tmp;
}
};
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
4 list 的 data structure
manage list: 只需要 1 根 node pointer`
_list_iterator / list 的 mem data 都只有 1个 node pointer
=> sizeof( list对象 ) = 4
为 符合 STL `前开后闭区间 ( 处理时带来很多方便 )` 要求,
让 `list 内部的 node pointer` 指向 `list 尾部 list.end() - 1` 后的 `空白结点 list.end()`
// list source
// ------ allocator.h
#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H
#include <new> // placement new
#include <iostream>
//------ 1. 第 1 级 allocator
class __malloc_alloc
{
private:
// note: func name 本身就是 func address:
// 即 func <=> &func
//(1) new_handler : 为 func pointer type
// new_handler pf : pf 为 func pointer
// void (* pf)() : pf 为 func pointer
typedef void (*new_handler)();
//(2) global handler : record the current func pointer
static new_handler global_handler;
public:
static void* allocate(size_t n)
{
//(3)
set_new_handler(handler); //<=> set_new_handler(&handler);
void* chunk = malloc(n);
// malloc 失败时, 调 oom_malloc()
if (0 == chunk)
chunk = oom_malloc(n);
return chunk;
}
//(4) set_new_handler: 仿 std::set_new_handler
static new_handler set_new_handler(new_handler pf)
{
new_handler previous_handler = global_handler;
// update global handler to be specified func's pointer
global_handler = pf;
return previous_handler;
}
//(5) handler func
static void handler()
{ // 企图 释放 memory
std::cout << "make more memory available\n";
std::set_new_handler(nullptr);
}
//(6)
static void* oom_malloc(size_t n)
{
new_handler local_handler = 0;
void* mem;
// 不断尝试(这里限制次数) 释放, 配置, 释放, 配置
for (int i = 0; i < 3; i++)
{
// 1) 取 the recorded handler func pointer from global_handler
local_handler = global_handler;
if (0 == local_handler)
continue;
// 2) 调 specified handler func
(*local_handler)();
// 3) malloc again
mem = malloc(n);
if (mem)
return mem;
}
}
static void deallocate(void* p, size_t)
{
free(p);
}
};
typedef __malloc_alloc malloc_alloc;
//------ 2. 第 2 级 allocator
//--- 3个 enum
enum
{
ALIGN = 8 // 最小 memory block
};
enum { MAX_BYTES = 128 };
enum { FREE_LIST_NUM = MAX_BYTES / ALIGN }; // 16 条 free_list
class __default_alloc
{
private:
// union 一物二用: 实现 节省 list node 的 pointer 域 空间
union obj
{
union obj* next;
char client_data[1];
};
// --- 4 static mem
// free_list[16] array: 16 free-list
static obj* volatile
free_list[FREE_LIST_NUM];
// memory pool management: 2 pointer
static char* start_free;
static char* end_free;
// accumulate var: request memory from OS 时,
// 用于 下次再 request from OS 时, 附加 request 的量
static size_t heap_size;
// request_mem_blk_bytes -> which free_list: free_list[i]
static size_t freelist_index(size_t request_mem_blk_bytes)
{
return (request_mem_blk_bytes + ALIGN - 1) / ALIGN - 1;
}
// request_mem_blk_bytes 上调至 8(= b1000) 的倍数:
// & 1111 1000 = & ~(ALIGN - 1)
static size_t ROUND_UP(size_t request_mem_blk_bytes)
{
return (request_mem_blk_bytes + ALIGN - 1) & ~(ALIGN - 1);
}
static void* refill(size_t n);
static char* chunk_alloc(size_t n, int& req_blk_num);
public: // 2 interface func
static void* allocate(size_t req_blk_size);
static void deallocate(void* p, size_t n);
};
typedef __default_alloc alloc;
//------ 3. simple_alloc
//------ 3. wrapper class template: simple_alloc
template<class T, class Alloc>
class simple_alloc
{
public:
static T*
allocate(size_t elem_num)
{
return 0 == elem_num ? 0 :
(T *) Alloc::allocate(elem_num * sizeof(T));
}
static void
deallocate(T* p, size_t elem_num)
{
if (elem_num != 0)
Alloc::deallocate(p, elem_num * sizeof(T));
}
};
#endif
// ------ allocator.cpp
#include "allocator.h"
malloc_alloc::new_handler malloc_alloc::global_handler = 0;
//--- 4 static mem data initialize
alloc::obj* volatile
alloc::free_list[FREE_LIST_NUM] = { 0 };
char* alloc::start_free = 0;
char* alloc::end_free = 0;
size_t alloc::heap_size = 0;
void* alloc::allocate(size_t req_blk_size)
{ // client 请求: req_blk_size, 只 请求 1 个 memory blk
obj* volatile* my_free_list;
obj* target_free_list_pobj;
if (req_blk_size > (size_t)MAX_BYTES)
{
// 转向 调 第 1 级 allocator
return (malloc_alloc::allocate(req_blk_size));
}
my_free_list = free_list + freelist_index(req_blk_size);
target_free_list_pobj = *my_free_list;
if (target_free_list_pobj == 0) // list empty
{
// request mem-blk from memory pool
void* res = refill(ROUND_UP(req_blk_size));
return res;
}
// seperate the first mem_blk from target_free_list
*my_free_list = target_free_list_pobj->next;
// void* p = pobj => pobj implicitly converted to void*
return target_free_list_pobj;
}
void* __default_alloc::refill(size_t req_blk_size_align)
{
int req_blk_num = 20;
//(1) allocator 内部 尝试 / 实际 request
// req_blk_num < / = 20 个 区块 from memory pool
// req_blk_num pass by reference to be modified
char* chunk = chunk_alloc(req_blk_size_align, req_blk_num);
obj* volatile* my_free_list;
obj* return_pobj, * current_pobj, * next_pobj;
//(2) 只请求到 1 个 mem_blk
if (0 == req_blk_num || 1 == req_blk_num) // else >= 2
return chunk;
//(3) the first mem_blk to be returned to client
return_pobj = (obj*)chunk;
//(4) other req_blk_num -1 个 mem_blks linked to free_list
my_free_list = free_list
+ freelist_index(req_blk_size_align);
*my_free_list
= next_pobj
= (obj*)(chunk + req_blk_size_align);
// 第 2th ~ req_blk_num th mem_blk linked to list
// the requested req_blk_num 个 mem_blk 是 连续 memory
// loop every mem_blk:
// 1) initialize next_head point to the start
// 2) current_head point to next_head
// 3) next_head updated to point to the real next blk
// => [current_head, next_head) 为 the current blk
// 4) link
for (int i = 0; ; i++)
{
current_pobj = next_pobj;
next_pobj = (obj*)((char*)next_pobj
+ req_blk_size_align);
// 第 2 ~ req_blk_num - 1 个 blk
if (i < req_blk_num - 2)
{
current_pobj->next = next_pobj;
}
else // 第 req_blk_num 个 blk
{
current_pobj->next = 0;
break;
}
}
return return_pobj;
}
char* __default_alloc::
chunk_alloc(size_t req_blk_size_align, int& req_blk_num)
{
char* chunk;
size_t half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
size_t mem_pool_left = end_free - start_free;
//(1) mem_pool_left 够 req_blk_num 个 blk -> 分配 req_blk_num 个
if (mem_pool_left >= half_blks_bytes_to_get)
{
chunk = start_free;
start_free += half_blks_bytes_to_get;
return chunk; // 递归出口
}
else if (mem_pool_left > req_blk_size_align)
{ //(2) 够 n >=1 个 blk => 分配 n 个
req_blk_num = mem_pool_left / req_blk_size_align;
half_blks_bytes_to_get = req_blk_num * req_blk_size_align;
chunk = start_free;
start_free += half_blks_bytes_to_get;
return chunk; // 递归出口
}
else // (3) 不够 1 个 blk: request from OS, molloc will allocate
{
//(4) mem_pool 余量 全 配给 适当 free_list[i]
if (mem_pool_left > 0)
{
// mem_pool 不足 1 个 req_blk:
// 必然有 刚好能 store 该 req_blk 的 某个 free_list
// 头插法 insert into 该 free_list
obj* volatile* my_free_list
= free_list + freelist_index(mem_pool_left);
((obj*)start_free)->next = *my_free_list;
*my_free_list = (obj*)start_free;
}
//(5) 向 OS 请求
size_t bytes_to_get = 2 * half_blks_bytes_to_get
+ ROUND_UP(heap_size >> 4);
start_free = (char*)malloc(bytes_to_get);
if (start_free == 0)
{ // heap memory 不足 -> malloc 失败
// (6) 从 req_blk_size_align 相应 free_list[i] 下一 free_list 开始,
// 循环遍历 后面 free_list[ j > i ]: 可能含 `unused larger 区块`
// larger_blk 必为 req_blk_size_align 整数倍大小
// 若 有
// (7) 拨 1 个 mem_blk 放 mem_pool
// (8) 再 调 自身 chunk_alloc, 向 mem_pool 申请
obj* volatile* my_free_list, * p;
for (size_t size = req_blk_size_align;
size <= MAX_BYTES;
size += ALIGN)
{
my_free_list
= free_list + freelist_index(mem_pool_left);
p = *my_free_list;
if (p)
{
//(7)
*my_free_list = p->next;
start_free = (char*)p;
end_free = start_free + size;
//(8)
return (chunk_alloc(size, req_blk_num));
}
}
//(9)
end_free = 0; // execute here => there are no memory anywhere
// 看 第 1级 allocator 的 out_of_memory 是否 有作用
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
}
//(10) update heap_size
heap_size += bytes_to_get;
//(11) update mem_pool tail
// head 在 前面已 modify
end_free = start_free + bytes_to_get;
//(12) 递归调自己, 以修正 req_blk_num
return chunk_alloc(req_blk_size_align, req_blk_num);
}
}
void __default_alloc::deallocate(void* p, size_t req_blk_size)
{
if (req_blk_size > (size_t)MAX_BYTES)
{
//(1) 调 第1级 allocator
malloc_alloc::deallocate(p, req_blk_size);
return;
}
obj* q = (obj*)p;
obj* volatile* my_free_list;
my_free_list = free_list
+ freelist_index(req_blk_size);
//(2) recycle the freed mem_blk to free-list
q->next = *my_free_list;
*my_free_list = q;
}
//------ list.cpp
#include <memory> // std::data_allocator
#include <new> // placement new
#include <iterator> // std::iterator / std::distance( InputIt first, InputIt last );
#include <iostream>
#include "allocator.h"
//------ construct + destory
template <class T>
void
construct(T* p, const T& value)
{
// placement new: 调 copy ctor / T::T(value)
new(p) T(value);
}
// destory 2 个 版本: an elem/elems_collection
template <class T>
void
destory(T* p)
{
p->~T(); // call dtor
}
template <class ForwardIterator>
void
destory(ForwardIterator first,
ForwardIterator last)
{
for (; first != last; ++first)
destory(&*first);
}
//------ 1. _list_node
template <typename T>
struct _list_node
{
_list_node<T>* prev;
_list_node<T>* next;
T data;
};
//------ 2. _list_iterator
template <class T>
struct _list_iterator
//: std::iterator<std::forward_iterator_tag, T>
{
//(1) 5 associated type
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//(2) typedef self alias
typedef _list_iterator<T> iterator;
typedef _list_iterator<T> self;
//(3) typedef list_node pointer type
typedef _list_node<T>* link_type;
//(4) only one mem data: a native pointer to list_node
link_type pnode;
//--- mem func
// (1) ctor
// 1) default
_list_iterator() { }
// 2) para type: pointer to list_node
_list_iterator(link_type p) : pnode(p) { }
// (2)copy ctor, para: iterator
_list_iterator(const iterator& iter)
: pnode(iter.pnode) { }
// (3) == !=
bool operator==(const self& iter) const
{
return pnode == iter.pnode;
}
bool operator!=(const self& iter) const
{
return pnode != iter.pnode;
}
// (4) * ->
reference operator* () const
{
return (*pnode).data;
}
// pnode is pointer => 可用 *p == p_obj
// 再用 mem operator .
// operator-> call operator*
pointer operator-> () const
{
return &(operator*());
}
// (5) prefix ++
self& operator++()
{
pnode = (link_type)((*pnode).next);
return *this;
}
// postfix ++
self operator++(int)
{
self tmp = *this;
++* this; // call prefix ++
return tmp;
}
};
//------ 3. list
template<class T, class Alloc = alloc >
class list
{
public:
// 4 typedef
typedef _list_node<T>* link_type;
typedef _list_iterator<T> iterator;
typedef T* pointer;
typedef T& reference;
typedef std::size_t size_type;
protected:
typedef _list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> data_allocator;
// only one mem data: list_node_pointer
link_type pnode;
protected: //--- internal func
//(1) allocate/deallocate/construt/destory a node
link_type construct_node()
{
return data_allocator::allocate(1);
}
void free_node(link_type const p)
{
data_allocator::deallocate(p, 1);
}
link_type create_node(const T& x)
{
link_type p = construct_node();
::construct(&p->data, x);
return p;
}
void destory_node(link_type const p)
{
::destory(&p->data);
free_node(p);
}
//(2) only one blank_node:
// 1) only allocate, but not construct
// 2) prev/next both point to itself
void creat_empty_list()
{
pnode = construct_node();
pnode->next = pnode;
pnode->prev = pnode;
}
void clear_empty_list()
{
free_node(pnode);
}
public: // --- interface func
//(1) ctor / dtor
list() { creat_empty_list(); }
~list() { clear_empty_list(); }
//(2) 4 kinds simple funcs
// 1) head/tail
iterator begin()
{
return iterator( (*pnode).next );
}
iterator end()
{
return iterator(pnode);
}
// 2) reference to head/tail
reference front() { return *begin(); }
reference back() { return *( --begin() ); }
// 3) is_empty
bool empty() const
{
return pnode->next == pnode;
}
// 4) size
size_type size() const
{
return std::distance(begin(), end() );
}
//(3) 3 fundamental func => other func
// 1) insert a node before position
iterator insert(iterator position, const T& x)
{
link_type tmp = create_node(x);
// 4 steps
tmp->next = position.pnode;
tmp->prev = position.pnode->prev;
(position.pnode->prev)->next = tmp;
position.pnode->prev = tmp;
return iterator(tmp);
}
// 2) destory_deallocate positioned node
iterator erase(iterator position)
{
link_type next_node = link_type(position.pnode->next);
link_type prev_node = link_type(position.pnode->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destory_node(position.pnode);
return iterator(next_node);
}
// 3) move elems in [first, last) to position_front
void transfer(iterator position, iterator first, iterator last);
//(4) push_back/front to tail_back/head_front
void push_back(const T& x)
{
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
//(5) pop_back/front: remoce head/tail, but not free space
void pop_back()
{
iterator tmp = end();
erase(--tmp);
}
void pop_front()
{
erase( begin() );
}
//(6) destory_deallocate list: only left blank_node
void clear();
//(7) remove consecutive nodes with the same value,
// only left the first
void unique();
//(8) 接合
void splice(iterator position, iterator first, iterator last);
void splice(iterator position, iterator iter);
void splice(iterator position, list& list2);
//(9) 合并 2个递增 list 为 1个 新递增 list
void merge(list<T, Alloc>& list2);
//(10) 逆向重置 list
void reverse();
//(11) sort: 内部用 快排
void sort();
};
//------ 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)
(3) iterator source code
#include <iterator>
#include < memory > // std::allocator
template <class T, class Ref, class Ptr, size_t BufSiz>
struct deque_iterator // 未继承 std::iterator
{
typedef std::random_access_iterator_tag iterator_category;
typedef T value;
typedef Ptr ptr; // T*
typedef Ref reference; // T&
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// iterator self
typedef deque_iterator<T, T&, T*, BufSiz> iterator;
typedef deque_iterator<T, const T&, const T*, BufSiz> const_iterator;
typedef deque_iterator self;
// map_pointer type
typedef T** map_pointer;
//------ 4 mem data
T* cur;
T* first;
T* last;
map_pointer node; //T**: pointer to map node
//------ mem func
//(1) buffer_size()
static size_t
buffer_size()
{
deque_buf_size(BufSiz, sizeof(T) );
}
size_t
deque_buf_size(size_t bufSize, size_t elemSize)
{
return n != 0 ? n : (elemSize < 512 ?
size_t(512 / elemSize) : size_t(1) );
}
//(2) 据 specified pointer to map node,
// 跳到 specified buf, don't update cur
// note: cur 单独 update
void set_node(map_pointer new_node)
{
node = new_node;
first = *new_node; // every new_node != NULL
last = first + difference_type( buffer_size() );
}
//(3) * -> : 针对 cur
reference operator*() const
{ return *cur; }
pointer operator->() const
{ return &( operator*() ); }
//(4) iter1 - iter2: 与 另一 iterator 相距 elem num, maybe negative
difference_type
operator-(const self& iter) const
{
return difference_type( buffer_size() )
* (node - iter.node - 1)
+ (cur - first) + (iter.last - iter.cur);
}
//(5) ++ --
self& operator++()
{
++cur;
if (cur == last)
{
set_node(node + 1);
cur = first;
}
return *this;
}
self& operator++(int)
{ // postfix : std style
self tmp = *this;
++*this;
return tmp;
}
self& operator--()
{
if (cur == first)
{
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self& operator--(int)
{
self tmp = *this;
--*this;
return tmp;
}
//(6) iter+= n( = > < 0 )
// => -= + -
self& operator+=(difference_type n)
{
// 1) 求 与 左边界 的 偏移 offset_to_first(> = < 0)
// equivalent to/but can't write to
// (cur + n) - first: 因 cur + n 实际调 oprator+= 实现
difference_type
offset_to_first = (cur - first) + n;
// 2_1) 偏移后 仍在 同一 buf
if (offset_to_first >= 0 &&
offset_to_first < difference_type( buffer_size() ) )
{
cur += n;
}
else // (>= 0 && >= buffer_size) || ( < 0)
{ // 2_2) 偏移后 不在 同一 buf
// 1> 偏移的 buf/node num
// >= 0 && >= buffer_size 时, easy
// < 0 时, 用 3个边界值 即可 归纳出 通式
// buf = [0, 8)
// offset_to_first
// == -1 应落在 prev buf 7 => -1 / 8 = 0 => 需 再 -1
// == -8 应落在 prev buf 0 => -8 / 8 = -1 => 无需 再 -1
// == -9 应落在 prev prev buf 7 => -9 / 8 => 需 再 -1
// 由 上述 3式 归纳 得
// -(-offset_to_first - 1)/8 - 1 刚好
difference_type offset_node_num =
offset_to_first > 0 ? offset_to_first / difference_type(buffer_size() )
: -difference_type( (-offset_to_first - 1) / buffer_size() ) - 1;
// 2> 跳到 new buf
set_node(node + offset_node_num);
// 3> 跳到 new elem :
// 变形 为 含 带 物理含义的 式子
// 新 cur = 新 first + [ ( 新 cur - 旧 first ) - (新 first - 旧 first) ]
cur = first + (offset_to_first -
offset_node_num * difference_type( buffer_size() ) );
}
return *this;
}
self& operator+(difference_type n)
{
seld tmp = *this;
return tmp += n;
}
self& operator-=(difference_type n)
{
return *this += -n;
}
self& operator-(difference_type n)
{
seld tmp = *this;
return tmp -= n;
}
//(7) operator[]
reference
operator[](difference_type n) const
{
return *(*this + n);
}
//(8) == != <
bool operator==(const self & iter) const
{
return cur == iter.cur;
}
bool operator!=(const self & iter) const
{
return !(*this == x);
}
// 同 buf, 比较 cur; 不同 buf, 比较 map_pointer
bool operator<(const self & iter) const
{
return (node == iter.node) ?
(cur < iter.cur) : (node < iter.node);
}
};
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
(2) source code`
`不要对 class 的 temp obj 用 操作符重载, 要借助于1个 named obj:`
`不要用 *(finish - 1), 而是用 1 个 tmp 记录 之, 再 *tmp`
template <class T, class Alloc = std::allocator<T>, size_t BufSiz = 0 >
class deque
{
public:
typedef deque_iterator<T, T&, T*, BufSiz> iterator;
typedef T value_type;
typedef value_type* poniter;
typedef value_type& reference;
typedef size_t size_type;
protected:
typedef poniter* map_pointer;
// 4 mem data: head/tail iterator + map/map_size
iterator start;
iterator finish; // 其 node mem 所指 buf 可能 valid
map_pointer map;
size_type map_size;
// 2 allocator: map / data
typedef simple_alloc<poniter, Alloc> map_allocator;
typedef simple_alloc<value_type, Alloc> data_allocator;
public:
//(1) ctor
deque(int n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
// allocate map/buf memory -> node/elem 赋值
initialize(n, value);
}
initialize(size_type n, const value_type& value)
{
//1) & 4 mem data assignmet
create_map_and_nodes_mem(n);
//2) [first, last) buf fill value
map_pointer node;
for (node = start.node; node < finish.node; ++node)
std::uninitialized_fill(*node, *node + buffer_size(), value);
//3) last buf's unused emem
std::uninitialized_fill(finish.first, finish.cur, value);
}
create_map_and_nodes_mem(size_type elemNum)
{
//1) allocate map memory
nodes_num = elemNum / buffer_size() + 1;
//2) map_size / map assignmet
map_size = nodes_num + 6; // different strategy
map = map_allocator::allocate(map_size);
//3) valid node put middle
map_poniter node_start
= map + (map_size - nodes_num) / 2;
map_poniter node_finish
= node_start + nodes_num;
//4) every node's value *node assignmemt:
// point to its allocated buf
// allocate nodes_num buf(uninitialized) & pointed to
map_poniter node;
for (node = node_start; node < node_finish; ++node)
*node = data_allocator::allocate( buffer_size() );
//5) start finish assignmet
start.set_node(node_start);
start.cur = start.first;
finish.set_node(node_finish);
finish.cur = finish.first + elemNum % buffer_size();
}
//(2) head/tail_off_by_one/size
iterator begin() { return start; }
iterator end() { return finish; }
// 调 iterator 的 operator-
size_type size() { return finish - start; }
//(3) *head/*tail
reference front() { return *start; }
reference back()
{
iterator tmp = finish;
--tmp;
return *tmp;
}
//(4) push_back
// pass by reference: construct need
// note: 实际 push 的 是 copy of elem
void push_back(const value_type& value)
{
// last buf 有 >=2 个 elem space
// => push_back 前, 不用 先分 1 buf
if (finish.cur != finish.last - 1)
{
::construct(finish.cur, value);
++finish.cur;
}
else
{
// last buf 仅 1 个 elem space:
// 扩 map memory + alocate buf memory
push_back_aux(value);
}
}
push_back_aux(const value_type& value)
{
value_type value_copy = value;
//1) 扩 map memory: 与 扩 vector 思路相近, bufs memory 不变
// 实现略, 头脑中有这个扩 map 的映像, 用时自然能写出
reserve_map_at_back();
//2) last buf 后, 再分 1 buf
*(finish.node + 1) = data_allocator::allocate( buffer_size();
//3) construct cur
::construct(finish.cur, value_copy);
//4) update finish = set_node + update cur
finish.set_node(finish.node + 1);
finish.cur = finish.first;
}
//(5) push_front
void push_front(const value_type& value
{
// first buf 有 >=1 个 elem space => 不用 先分配一块 buf
if (start.cur != start.first)
{
construct(start.cur - 1, value);
--start.cur;
}
else // 无 elem space => 先分 1 buf
{
push_front_aux(value);
}
}
push_front_aux(const value_type& value); // 略, 类 push_back_aux
//(6) 去 tail/head : 必要时, 还要 free the last/first buf
// 否则, 只 destory 相应 elem 而 不 free 它
void pop_back()
{
if (finish.cur != finish.first)
{ // last buf >= 1 elem
//1) move cur pointer forward
// <=> exclude tail elem
// <=> deque valid elem no longer include it
--finish.cur;
//2) destory it but not free it:
// only free whole buf memory
destory(finish.cur);
}
else
{
// free last buf
// finish iterator move forward
// exclude tail elem
// destory it
}
}
void pop_front(); // omit
//(7) clear() 清除 deque
//(8) erase
iterator erase(iterator pos)
{
iterator next = pos;
++next;
difference_type elem_num_before_pos = pos - start;
// pos 前/后 elem 少: 移动 pos 前/后 elem, 覆盖 pos
if (elem_num_before_pos < (size() >> 1) )
{
std::copy_backward(start, pos, next);
pop_front();
}
else
{
std::copy(next, finish, pos);
pop_back();
}
// return 原 pos iterator
return start + elem_num_before_pos;
}
iterator erase(iterator first, iterator last)
{
if (first == start && last == finish)
{
clear();
return finish;
}
else
{
difference_type n = last - first;
difference_type elems_before = first - start;
// 若 clearr 区间 前/后 elen 元少
if (elems_before < (size() - n) / 2)
{
//1) copy 实现 移动 + 覆盖
std::copy_backward(start, first, last);
//2) destory
iterator new_start = start + n;
destory(start, new_start);
//3) free mid bufs memory
for (map_pointer node = start.node; node < new_start.node; ++node)
data_allocator::deallocate(*node, buffer_size());
}
else
{
std::copy(last, finish, first);
//...
}
}
}
//(9) insert specified value to position_front
// return iterator to positioned elem
iterator
insert(iterator position, const value_type& x)
{
// head / tail / middle insert
if (position.cur == start.cur)
{
push_front(x);
return start;
}
else if (position.cur == finish.cur)
{
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
}
else
{
// omit, 见过程图
return insert_aux(position, x);
}
}
};
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
#include <queue>
#include <list>
#include <iostream>
#include <algorithm>
int main()
{
std::queue<int, std::list<int> > que; // 以 list 作 底层容器 的 queue
que.push(1);
que.push(5);
que.push(10);
que.push(15);
std::cout << que.size() << std::endl; //4
std::cout << que.front() << std::endl; //1
std::cout << que.back() << std::endl; //15
que.pop();
std::cout << que.size() << std::endl; //3
std::cout << que.front() << std::endl; //5
}
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 适配器
image.png
image.png
image.png
image.png
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 ) );
网友评论