STL体系结构

六大组件

容器 container

分配器 allocator

适配器 adaptor

算法 algorithm

迭代器 itrator

泛化指针

[)前闭后开区间

o.begin()指向首元素，o.end()指向尾元素的下一个位置

仿函数 functor

OOP and GP

Object-Oriented Programming 面向对象编程

datas 和 methods 封装在一个类中

Generic Programming 泛型编程

datas 和 methods 分开

algorithms 通过 Iterators 操作 containers 中的数据并可使用functors

容器

容器分类

Sequence Containers 序列容器

Arrays 数组

Vector 动态数组

deque 双向队列

List 双向链表

Forward-List 单链表

Associative Containers 关联容器

set 无重复元素的集合

multiset 可有重复元素

map 无重复元素的键值对集合

multimap 可有重复元素

底层结构为红黑树
Unordered Containers 无序容器

unordered set/unordered multiset

unordered map/unordered multimap

底层结构为hashTable-Separate Chaining

容器测试

//测试常用库
#include<ctime>
#include<cstdlib>  //引入qsort,search等等算法

clock_t nowtime = clock(); //clock()函数返回从开启这个程序进程到调用clock()函数的CPU时钟计时单元数，返回单位是毫秒，类型为clock_t

Sequence Containers 序列容器

不便于查找

Array

数组

定义

1 2	#include<array> array<type,size> name; //需要指定定长array的初始大小,size为常量

初始化

通过下标来放置元素

接口测试

array.size(); //容器元素个数
array.front(); //取首元素
array.back(); //取尾部元素
array.data(); //返回容器的首元素地址

Vector

动态数组

定义
1
2
#include<vector>
vector<type> name; //等等
动态扩容一般为扩容为原来的2倍

先创建2倍的内存空间，再逐个元素copy过去

初始化
push_back()

接口测试
1
2
3
4
5
vector.size(); //容器元素个数
vector.front(); //取首元素
vector.back(); //取尾部元素
vector.data(); //返回容器的首元素地址
vector.capacity(); //查看容器可容纳的空间大小

Deque

双向队列

定义
双向扩容,一次扩充一个buffer，并由deque中的指针指向

分段buffer连续,段中存放着连续数据

涵盖了容器适配器stack与queue的功能

stack与queue均操作受限，因此无法使用iterator迭代器，无法调用find方法
1
2
#include<deque>
deque<type> name;
初始化
push_back() //将数据放置在deque中段buffer的结构中

接口测试
1
2
3
4
deque.size(); //容器元素个数
deque.max_size(); //容器所能容纳的最大元素个数
deque.front(); //取首元素
deque.back(); //取尾部元素

List

双向链表

定义
1
2
#include<list>
list<type> name;
初始化
push_back()

接口测试
1
2
3
4
list.size(); //容器元素个数
list.max_size(); //容器所能容纳的最大元素个数
list.front(); //取首元素
list.back(); //取尾部元素
注意:list不提供randomaccessiterator 所以无法调用全局sort方法,需要内部重载

Forward_list

单链表

定义

1 2	#include<forward_list> forward_list<type> name;

初始化

push_front() 头插

接口测试

1 2	forward_list.max_size(); //容器所能容纳的最大元素个数 forward_list.front(); //取首元素

Associative Containers 关联容器

查找效率高

Multiset

定义
1
2
#include<set>
multiset<type>  name;
初始化
1
Multiset.insert(value)  //安插到该安插的位置而非固定头尾
相较于::find(),multiset.find()查找更快,通过(*item)取得值

接口测试
1
2
multiset.size(); //
multiset.max_size(); //

Set

底层为红黑树

定义
1
2
#include<set>
set<type>  name;
初始化
1
Set.insert(value)  //安插到该安插的位置而非固定头尾
接口测试
1
2
set.size(); //
set.max_size(); //
注意: 不允许重复

Multimap

定义

1 2	#include<map> multimap<key_type,value_type> name

初始化

1
2
3

Multimap.insert(pair<key_type,value_type>(key,value)) //使用pair模板对象来封装key-value
//pair.second为value pair.first为key
//不可以用[]做insertion

相较于::find(),obj.find()查找更快，通过(*item).second取得值

接口测试

1 2	multimap.size(); // multimap.max_size(); //

Map

底层为红黑树

定义
1
2
#include<map>
map<key_type,value_type> name
初始化
1
2
map[i] = valve; // map自动执行封装key-value
//Map.insert(pair<key_type,key_value>(key,value));
接口测试
1
2
map.size(); //
map.max_size(); //
注意: 不允许重复，但是该重复指的是key-value重复，仅一个不同另一个相同不算重复

Unordered Containers 无序容器

hash Containers 以hashtable为底层结构

Unordered_multiset

定义

1	unordered_multiset<type> name

初始化

1	Unordered_multiset.insert(value);

接口测试

u_mset.size(); //
u_mset.max_size(); //
u_mset.bucket_count(); //篮子数，存放hash值的数组长度
u_mset.bucket_size(i); //第i个篮子的连接的结点数
u_mset.load_factor(); //负载因子
u_mset.max_bucket_count(); //最大篮子数，存放hash值的数组长度
u_mset.max_load_factor(); //最大负载因子

Unordered_Multimap

定义

1	unordered_multimap<key_type,value_type> name;

初始化

1 2	unordered_multimap.insert(pair<key_type,value_type>(key,value)) //使用pair模板对象来封装key-value //pair.second为value pair.first为key

接口测试

1 2	unordered_multimap.size(); // unordered_multimap.max_size(); //

Unordered_Set

底部为hashtable

Unordered_Map

底部为hashtable

容器源码剖析

Sequence Containers 序列容器

List

环状双向链表

将有一个空结点使该环状双向链表满足前闭后开原则(begin()指向第一个结点,end()指向尾结点的下一个位置)

GCC2.9

组成

结点模板类

指向前一个结点成员的空指针

指向下一个结点成员的空指针

list模板类

指向结点的头指针node

一个list类对象的大小为4byte在GCC2.9编译器下

iterator迭代器模板类成员

…

iterator迭代器模板类

5个不可或缺的typedef类型声明

Link_type 元素类型

Reference 引用类型

Pointer 指针类型

指向结点的指针node

对各种运算符的重载函数

//list_gcc29.h
#ifndef __USER__
	#define __USER__ myy

template<class T>
struct __list_node{
	typedef void* nptr; //空指针比较鸡肋需要进行类型转型gcc4.9对此也进行了改善直接使用指针类型
	nptr pre;
	nptr next;
	T data;
}


template<class T,class Alloc = alloc>
class list {
public:
	typedef __list_node<T> node_type; //可能其他部分使用到了这个结点类型
	typedef node_type* nodeptr;
	typedef list_iterator<T,T&,T*> iterator; //gcc2.9需要传递3个参数gcc4.9对此做了改善只需要传递T类型参数即可
private:
	nodeptr node;
};


template<class T,class Ref,class Ptr>
struct list_iterator {

	//typedef类型声明部分

	typedef list_iterator<T, Ref, Ptr> self;
	typedef __list_node<T>* node_type;

	//必要的5中类型声明
	typedef bidirectional_iterator_tag iterator_category; //迭代器的种类
	typedef T value_type; //数据类型
	typedef Ptr pointer; //指向node类型的指针
	typedef Ref reference; //node类型的引用类型
	typedef ptrdiff_t difference_type; //两个迭代器之间距离的类型

	//- - -

	//运算符重载

    //后置++重载
	//注意返回类型为对象而非引用，所以后置自增无法多次++,例如a++++
	self operator++(int) {
		self temp(*this); //调用拷贝构造函数进行深拷贝，将当前保存为临时对象
		++*this; //当前对象执行已重载的前置自增操作
		return temp; //返回临时对象的拷贝-调用拷贝构造函数
	};

	//前置++重载
	//注意返回类型为引用，所以前置自增可多次++,例如++++a
	self& operator++() {
		node = (node_type)(node->next);
		return *this;
	}; 

	reference operator*() const{
		return (*node).data;
	};

	pointer operator->() const{
		return &(operator*())
	};

private:
	node_type node;
}



#endif // !USER

GCC4.9
相较于2.9的改善
1. 结点指针类型明确不再是空指针
2. 结点继承自一个父类
3. iterator模板参数为1个不再是冗杂的3个
gcc4.9下一个list对象所占的内存为8byte

vs2017下一个list对象所占的内存为12byte

Vector

GCC2.9

组成

三个Iteretor迭代器成员

分别指向首元素,尾元素下一个位置,最后一个内存位置

一个vector对象的内存为12byte

各种运算符的重载

基本操作函数成员

//vector_gcc29.h
#ifndef __user__
	#define __user__ myy

template<class T,class Alloc = alloc>
class vector {
public:
	typedef T value_name;
	typedef value_name* iterator;
	typedef T& reference;
	typedef size_t size_type;

	iterator begin() const{
		return start;
	}

	iterator end() const{
		return finish;
	}

	size_type size() const{
		return size_type(end() - begin());
	}

    bool empty const() {
		return begih() == end();
	}

	size_type capacity() const {
		return size_type(end_storage - begin());
	}

    //连续空间支持下标索引所以需要对[]运算符重载
	reference operator[] const(size_type& s) {
		return *(start + s);
	}

    reference front() const {
		return *begin();
	}

	reference back() const {
		return *(end() - 1);
	}

    void push_back(const T& x) {
		if (end() != end_storage) {
			construct(finish,x); //全局函数
			finish++;
		}
		else {
			insert_aux(end(), x); //插入辅助函数
		}
	}

	void insert_aux(iterator position, const T& x);

protected:
	iterator start;
	iterator finish;
	iterator end_stroage;
};

#endif // !__user__

Iterator

vector的内存为连续空间因此不再使用泛型指针而是采用native pointor

扩容

GCC2.9

当vector满时(end() == end_storage)进行二倍扩容

任何扩容不会原地扩容，因为其后连续空间可能已被占用，只能预先申请新的内存并将原元素copy过去

在插入操作时可能引发扩容操作

使用alloc分配器申请二倍内存空间

在copy原vector元素时完成插入操作而非copy扩容完成后再重新插入

将原vector插入位置position之前的元素先copy到新vector中

执行插入操作

将原vector插入位置position之后的元素再copy到新vector中

删除原内存空间

调整迭代器

template<class T,class Alloc>
void vector<T,Alloc>::insert_aux(iterator position, const T& x) {

	if (end() != end_storage) {
		insert_aux(finish, *(finish - 1));//position位置之后的元素需要后移
		finish++;

		T temp = x;
		copy_backward(position, finish - 2, finish - 1);

		*(position) = temp;
	}
	else {
		const size_type old_size = size();
		const size_type len = ole_size != 0 ? old_size * 2 : 1; //获取新创建空间的长度

		iterator new_start = data_allocator::allocate(len); //分配长度为len的内存空间
		iterator new_finish = new_start; //初始为空

		try {
			new_finish = uninitialized_copy(start, position, new_start); //将原vector中position之前的元素copy到扩容后的新内存

			construct(new_finish, x); //将待插入的值插入到position位置
			new_finish++;

			new_finish = uninitialized_copy(position, finish, new_finish); //将原vector中position之后的元素copy到扩容后的新内存
		}
		catch (...) {
			// "roll back or commit"
			//销毁申请失败的新内存
			destroy(new_start, new_finish);
			data_allocator::deallocate(new_start, len);
			throw;
		}

		//销毁原vector
		destroy(begin(), end());
		deallocate();

		//调整迭代器
		start = new_start;
		finish = new_finish;
		end_storage = new_start + len;
	}
}

Array

数组

GCC2.9

组成

数组成员

迭代器 native pointer

无构造函数析构函数

#pragma once
#include <array>
template <typename _Tp,std::size_t _Nm>
struct Array {

	typedef _Tp value_type;
	typedef _Tp* pointer;
	typedef value_type* iterator;

public: 

	//Array无构造函数析构函数

	iterator begin() {
		return &arr[0];
	}

	iterator end() {
		return &arr[_Nm];
	}

private:
	value_type arr[_Nm ? _Nm : 1]; //若数组长度参数为0默认将长度值为1
};

Forward list

单向链表

无法对 – 运算符重载，所以只能单向移动迭代器

push_front头插

Deque

双向队列

分段有序但是存在是连续空间的假象

结构

map + buffer / 中控 + 缓冲

map

是一个vector，元素类型为指向bufer的指针

buffer
实际存放数据的一段内存

创建deque对象时需要指定buffer大小，若未指定，则使用默认值
1
2
3
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));
}

组成

数据元素大小为40byte 16+16+4+4

-

start迭代器 16byte

-

first指针 - 指向所有buffer中的第一个buffer的起始内存位置

last指针 - 指向所有buffer中的第一个buffer内存的末尾

last = first + difference_type(buffer_size());

cur指针 - 指向所有元素的首元素

map-poninter指针 - 指向map中控vector的首元素

-

finish迭代器 16byte

-

first指针 - 指向所有buffer中的最后一个buffer的起始内存位置

last指针- 指向所有buffer中的最后一个buffer内存的末尾

last = first + difference_type(buffer_size());

cur指针 - 指向所有元素中最后一个元素的下一个位置

map-poninter指针 - 指向map中控vector的尾元素

-

指向map中控的指针 4byte

存储map大小的size_t变量 4byte

-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
template<class T, class Alloc = alloc ,size_t BufSiz=0>
class Deque {
//...
public:

	typedef iterator<T, T&, T*, BufSiz> iterator;
	typedef ptrdiff_t difference_type;

protected:

	typedef T** map_pointer;

public:
	iterator begin() {
		return start;
	}

	iterator end() {
		return finish;
	}

	size_type size() {
		return finish - start;
	}

    iterator insert(iterator pos, const T& x) {
		if (pos.cur == start.cur)
		{
			push_front();
			return start;
		}
		else if (pos.cur==finsh.cur) {
			push_back();
			iterator temp = finsh;
			return --temp;
		}
		else {
			insert_aux(pos, x);
		}
	}
	//deque的元素插入函数
	iterator insert_aux(iterator pos, const T& x) {
		difference_type len = pos - start;
		if (len < size() / 2) {
			push_front(front()); //在最前端插入与第一个元素同值的元素
			copy(...); //pos位置之前的元素前移
		}
		else {
			push_back(back()); //在最后端插入与最后一个元素同值的元素
			copyback(...); //pos位置之后的元素后移
		}
		*pos = x;
		return pos;
	}

    //"连续空间"需要有对[]运算符的重载
    T& operator[] (size_t n) {
        return start[difference_type(n)];
    }

protected:
	iterator start;
	iterator finsh;
	map_pointer map;
	size_type map_size;
//...
};

迭代器组成

first指针

last指针

cur指针

map-poninter指针

对基本运算符的重载

*解引用运算符

取迭代器cur对应的元素
->箭头运算符

取迭代器cur对应的元素的地址
ite1 - ite2

得两迭代器之间的所有元素

分三部分求得

ite2指向的buffer元素

ite1指向的buffer元素

两个迭代器之间的buffer的所有元素

++运算符

“连续空间”下++使ite指向后一个元素

根据cur与边界(first/last)的等值关系来判断是超过buffer界限
–运算符

“连续空间”下++使ite指向前一个元素

根据cur与边界(first/last)的等值关系来判断是超过buffer界限
+=运算符 ite += n

根据偏移量大小正负来判断是否超过buffer界限(前后均有界)

template<class T,class Ref,class Ptr, size_t BufSiz=0>
class iterator {

public:
	typedef random_acsess_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef ptrdiff_t difference_type;

	typedef iterator self;
	typedef T** map_pointer;

public:
	reference operator*() const{
		return *cur;
	}

	pointer operator->() const{
		return &(operator*());
	}

	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));
	}

	difference_type operator- (const self& x) {
		auto bfnums = (node - x.node - 1)*(difference_type)(buffer_size()); //作差的两个迭代器之间的(buffer个数)*(buffer大小)得出之间的元素个数
		auto front = x.last - x.cur; // 被减的迭代器指向的buffer中的元素个数
		auto back = cur - first; //减数迭代器指向的buffer中的元素个数

		return bfnums + front + back; //三者作和得两作差迭代器之间的元素个数
	}

	self& operator++() {

		cur++; //当做连续空间，需要将cur指向下一个元素
		// 若cur++后超过当前buffer范围，则该迭代器需要指向下一个buffer
		if (cur == last) {

			set_node(node + 1); //更新迭代器中first,last，node与buffer相关的特定属性
			cur = first; //重新更新cur指向使得cur指向"连续空间"的下一个元素
		}

		return *this;
	}

	self operator++(int) {

		self temp = *this;
		++*this;
		return *temp;
	}

	self& operator--() {

		// 判断当前cur是否位于边界处，则该迭代器需要指向下一个buffer
		if (cur == first) {

			set_node(node - 1); //更新迭代器中first,last，node与buffer相关的特定属性
			cur = last; //重新更新cur指向使得cur指向"连续空间"的下一个元素
		}

		cur--; //因为buffer的左边界就是首元素所以需要先作判断,并且last指向尾元素的下一个位置,需要--指向尾元素

		return *this;
	}

	self operator--(int) {

		self temp = *this;
		--*this;
		return *temp;

	}

	void set_node(const map_pointer& new_node) {

		node = new_node;
		first = *(new_node);
		last = first + difference_type(buffer_size());
	}

	self& operator+=(difference_type n) {
		difference_type offset = n + (cur - first); //通过原cur位置前的元素与偏移量之和得出的新偏移量判断是否超出单buffer范围

		if (offset >= 0 && offset < difference_type(buffer_size())) {

			cur += n; //未超过且执行的为+=操作则直接移动cur指针
		}
		else {

			difference_type node_offset = offset > 0 ? offset / difference_type(buffer_size()) : -difference_type((-offset - 1) / (buffer_size()); //否则计算跨的buffer个数--node偏移量
			set_node(node + node_offset); //更新迭代器
			cur = first + offset - node_offset * difference_type(buffer_size()); //更新cur使其指向"连续"空间后移n位的元素，通过first+本buffer偏移量指定

		}
                                                                                                                  return *this;
	}

	self operator+(difference_type n) {
		self temp = *this;
		return temp += n;
	}

	self& operator-=(difference_type n) {
		*this += -n;
		return *this;
	}

	self& operator-(difference_type n) {
		self temp = *this;
		return temp -= n;
	}
	                                                                                                            reference operator[] (difference_type n) const {
		return *(*this + n);
	}

private:
	map_pointer map;
	pointer start;
	pointer last;
	pointer cur;
};

常用方法

insert(iterator,const Type&);

插入时候需要判断插入的位置距离头部与尾部的位置来决定头插还是尾插

距离谁近，从哪里插入！

扩容机制

vector扩容后各元素copy到中段，方便buffer的双向扩充而非从新内存的起始开始

Queue

adapter适配器

不提供iterator迭代器以此来防止遍历操作

内含(复用)底层容器(默认deque)，直接使用底层容器的方法来实现queue的方法

//queue
template<class T,class Sequence=deque<T>>
class queue{
...
public:
 typedef Sequence::value_type value_type
 typedef Sequence::size_type size_type
 typedef Sequence::reference reference
 typedef Sequence::const_reference const_reference
protected:
 Sequence c;
public:
 bool empty() {return c.empty();}
 size_type size() const{return c.size();}
 reference front() {return c.front();}
 const_reference front() const {return c.front();}
 reference back() {return c.back();}
 const_reference back() const {return c.back();}
 void push(const value_type& x) {c.push_back(x);}
 void pop() {c.pop_front();}
 ...
}

Stack

adapter适配器

不提供iterator迭代器以此来防止遍历操作

内含(复用)底层容器(默认deque)，直接使用底层容器的方法来实现stack的方法

//stack
template<class T,class Sequence=deque<T>>
class stack{
...
public:
 typedef Sequence::value_type value_type
 typedef Sequence::size_type size_type
 typedef Sequence::reference reference
 typedef Sequence::const_reference const_reference
protected:
 Sequence c;
public:
 bool empty() {return c.empty();}
 size_type size() const{return c.size();}
 reference top() {return c.back();}
 const_reference top() const {return c.back();}
 void push(const value_type& x) {c.push_back(x);}
 void pop() {c.pop_back();}
}

底层容器的选择

理论上说含有对应queue/stack所有方法的转调函数的容器均可以作底层容器如list

但是vector无法作queue的底层容器因为vector不提供queue.pop()的转调函数

set/map均无法作底层容器

Associative Containers 关联容器

Rb_tree 红黑树初识

高度平衡的二叉搜索树

提供iterator迭代器遍历整个红黑树

但是不应使用iterator迭代器去改变元素值，但是map可以因为map容器应提供可更改元素data的迭代器，只是元素的key不可被改变

rb_tree

GCC2.9

部分组成

数据成员大小 4+4+1=9 -> 12 byte 函数对象为仿函数，类中仅有对()操作符的重载，因此大小为0，编译器作1处理，但是应为4的倍数，最近的为12

-

红黑树结点个数

头结点

Compare仿函数

封装通过value值得到key值函数的类

-

GCC4.9

增加了color enum类型的颜色成员

数据成员大小为24byte

-

需要有5个模板参数

key 键的类型

value value对象 = key对象 + data对象

Alloc 分配器

keyofvalue
用于从value取出key值的仿函数

若key = value ，则gcc2.9提供了identity仿函数来返回key值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class Arg,class Result>
struct unary_function {

 typedef Arg argument_type;
 typedef Result result_type;
}

template<class T>
struct identity:public unary_function<T,T> {
 // 1.需要公用继承unary_function
 // 2.identity为GCC2.9提供的其他编译环境需要将定义内置于对应容器类中
 // 3.返回值为const类型标明key值不允许被改变
const T& operator() (const T& x) const {
    return x;
}
}
compare 封装key对象比较大小的仿函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class Arg1,class Arg2,class Result>
struct binary_function {

 typedef Arg1 first_argument_type;
 typedef Arg2 second_argument_type;
 typedef Result result_type;
}

template<class T>
struct less:public binary_function<T,T,T> {
 // 需要公用继承binary_function
bool operator() (const T& x,const T& y) const {
    return x < y;
}
}
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<class Key,
	class Value,
	class Keyofvalue,
	class Compare,
	class Alloc = alloc
>
class rb_tree {
protected:

	typedef __rb_tree_node<Value>* rb_tree_node;
public:

	typedef rb_tree_node* link_type;
private:

	size_type node_count; //红黑树结点个数
	link_type header; //头结点
	Compare key_compare; //函数对象 functor
};
接口函数

insert_unique() 插入元素不可重复，若重复不会插入元素

insert_equal() 插入元素可重复

Set/Multiset

以rb_tree为底层结构

key = value

set调用的insert接口为insert_unique()

Multiset调用的insert接口为insert_equal()

以set为例

重要组成

底层容器红黑树

const迭代器不允许更改元素的key与data

>template<class Key,class Compare = less<Key>,class Alloc=alloc>
>class set {
>//...
>public:
typedef Key Value_Type;
typedef Key Key_Type;

typedef Compare Key_Compare;
typedef Compare Value_Compare;


struct identity :public unary_function<T, T> {

	const T& operator(const T& x) const {
		return x; //其实x这里传入的是value，再由value取key
	}
}

>private:
typedef rb_tree<Key_Type, Value_Type, identity, Key_Compare,Alloc> rbt;
rbt r;

>public:
typedef typename rbt::const_iterator iterator; //使用const_iterator保证无法通过iterator改变元素值

>};

Map/Multimap

以rb_tree为底层结构

均将key与data封装为一个pair对象作为value

Map调用的insert接口为insert_unique()

map还提供了对[key]运算符的重载,存在key指定的元素则返回data值，不存在则insert插入元素

Multimap调用的insert接口为insert_equal()

以map为例

重要组成

底层容器红黑树

迭代器不允许更改元素的key但可以更改元素的data

template<class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
	//...
public:
	typedef Key Key_Type;
	typedef T Data_Type;

	typedef pair<const Key_Type, Data_Type> Value_Type; //保证key无法被更改但是data可以

	typedef Compare Key_Compare;

	struct selectlst : unary_function<value_type, Key_Type> {
     const Key_Type& operator(const value_type& x) const{
         return x.first;
     }
 }


public:
	typedef typename rbt::iterator iterator;

private:
	typedef rb_tree<Key_Type, Value_Type, selectlst, Key_Compare, Alloc> rbt;
	rbt r;
};

Unordered Containers 无序容器

hashtable

buckets vector + node buckets数为质数

hashtable hashmap详解本文略

类结构基本组成

五个模板参数

相较于rb_tree多了一个hashfuc，用于计算obj对应的hash值

-

…数据成员大小为 1+1+1+12+4 = 19 -> 20 byte

内部维护一个vector容器，存放指向链结点的指针

-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// buckets vector + node

template<class T>
struct __hash_node {

	//GCC2.9中node为单向链表
	__hash_node* next;
	T data;
};

//

template<class Value,
	class Key,
	class Hashfun,
	class ExtractKey,
	class EqualKey,
	class Alloc=alloc
>
class hashtable {
//...

public:

	typedef Hashfun hasher;

	typedef EqualKey key_equal;
	typedef size_t size_type;

private:

	hasher hash;
	ExtractKey get_key;
	key_equal equals;

	size_type node_sums; //存放所有结点元素数的寄存器

    typedef __hash_node<Data> node;    
    vector<node*, alloc> buckets;

};
迭代器

迭代器需要支持加减操作因此不仅需要有指向结点的指针还需要有返回中控vector的指针

hashtable的迭代器相较于rb_tree其允许通过迭代器改变结点的data但是不允许改变key，因为key是hash计算的依据
1
2
3
4
5
6
7
8
9
10
11
12
template<class Value,
	class Key,
	class Hashfun,
	class ExtractKey,
	class EqualKey,
	class Alloc = alloc
>
class __hashtable_iterator {
	//...
	__hash_node* next; //指向结点的指针
	hashtable* bk; //指回vector的指针
};

扩容

当node_sums结点个数大于buckets边界值时会进行2倍扩容并重新进行hash计算

注意:buckets.size()扩容大小在GCC2.9中并不是一定为2的整数倍，而是2的整数倍附近的质数，初始53

hashfunc and hashcode

模板特化完成个类型对象->size_t类型的转换

注意:Gcc2.9中 std模板库并没有提供对hash<std::string>的定义目前已经有了
1
template<class Key> hash {}

Allocators 分配器

Allocator测试

为容器分配内存，不同分配器有不同的分配方式

内部包含一个allocate函数来分配内存，一个deallocate来删除内存并且需要知道起初分配的内存大小

operator new/delete 与malloc/free

malloc分配的内存模型

一对cookie

一对debug头

struct -size对应的部分

填充字节

operator new/delete 的底层实现就是malloc/free

allocator

一个类模板,重要的两个函数

pointer allocator(size_t)

void deallocator(pointer,size_t)

原型并不规范但是值得注意的是一般分配器的deallocator需要知道回收的内存大小才能进行回收，脱离容器直接使用很不方便

不同编译器对allocator的处理

VC6 STL 对allocator的使用与实现

// Visual c++ Builder Compiler

#include<xmemory> // 需要引入对应头文件
// VC6+的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计

// ...
int*p=allocator<int>().allocator(size,(void*)0);
allocator<int>().deallocator(p,size);
// 脱离容器直接使用分配器进行内存分配

VC6+的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计

BC5 STL 对allocator的使用与实现

// Borland C++ Builder Compiler

#include<memory.stl> // 需要引入对应头文件

// ...
int*p=allocator<int>().allocator(size); // 第二个指针参数这里为默认参数省略
allocator<int>().deallocator(p,size);
// 脱离容器直接使用分配器进行内存分配

BC++ 的allocator只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计

GCC2.9
GCC2.9 的allocator仍只是以::operator new和::operator delete完成allocate()和deallocate()，没有任何特殊设计
1
2
3
// GNU Compiler C++ Builder Compiler

#include<defalloc.h>
但是GCC2.9库中虽然有allocator但是实际并不使用该类模板做分配器，实际采用的是效率更高的alloc
1
2
3
4
5
#include<stl_alloc.h>
// 脱离容器直接使用分配器进行内存分配
// ...
int*p=alloc::allocate(size);
alloc::deallocate(p,size);
alloc内存管理

尽量减少malloc的次数

尽量使得为容器元素分配的内存不带cookie

具体先略，理解模糊

GCC4.9

GCC4.9实际使用的仍是以::operator new和::operator delete完成allocate()和deallocate()

1 2	#include<bits/allocator.h> #include<bits/new_allocator.h>

但是仍然可选择使用GCC2.9的alloc分配器

#include<memory> // 内含std::allocator
// 欲使用std::allocator以外的分配器需要自行#include<ext\...>

// extension allocators 中的__pool_alloc就是GCC2.9的alloc分配器
// 使用
#include<ext\pool_allocator.h>
vector<int,__gnu_cxx::__pool_alloc<string>> vec;

Iterator 迭代器

迭代器的设计原则

至少需要具备5个associated关联类型

需要回答算法的提问，某些算法中会使用到其中的类型

Class iterator

以类封装的iterator可以自己定义associated type

cl_iterator

模板类内部对关联类型作定义

template<class T>
struct cl_iterator {
	typedef bidirectional_iterator_tag iterator_category; //迭代器的种类
	//bidirectional为双向链表iterator类型
	typedef T value_type; //数据类型
	typedef Ptr pointer; //指向node类型的指针
	typedef Ref reference; //node类型的引用类型
	typedef ptrdiff_t difference_type; //两个迭代器之间距离的类型
}

algorithm

直接通过迭代器本身来获取关联类型

template<class I>
void algorithm(I first,I last) {
	typedef typename I::category v1;
}

Native pointer

native pointer是一种退化的iterator，没有能力自己定义associated type

所以algorithm无法直接通过迭代器本身获取关联类型

Iterator Triats

”萃取机“以偏特化使得以上两种iterator类型均满足设计原则

for cl_iterator

在已定义cl_cl_iterator迭代器的情况下可直接使用已定义的

template<class T>
struct iterator_traits {
	//...
	typedef typename T::category iterator_category;
	typedef typename T::value_type value_type;
	typedef typename T::pointer pointer;
	typedef typename T::reference reference;
	typedef typename T::difference_type difference_type;
	//...
};

for native pointer

区分const pointer与no_const pointer

//no_const pointer 
template<class T>
struct iterator_traits<T*> {
	//...
	typedef random_access_iterator_tag iterator_category; //迭代器的种类
	//bidirectional为双向链表特有iterator类型
	typedef T value_type; //数据类型
	typedef T* pointer; //指向node类型的指针
	typedef T& reference; //node类型的引用类型
	typedef ptrdiff_t difference_type; //两个迭代器之间距离的类型
	//...
};

//const pointer特殊在取得的value_type不希望为const T
template<class T>
struct iterator_traits<const T*> {
	//...
	typedef random_access_iterator_tag iterator_category; //迭代器的种类
	//bidirectional为双向链表特有iterator类型
	typedef T value_type; //数据类型
	typedef T* pointer; //指向node类型的指针
	typedef T& reference; //node类型的引用类型
	typedef ptrdiff_t difference_type; //两个迭代器之间距离的类型
	//...
};

algorithm

通过”萃取机”来间接获取迭代器的关联类型

template<class I,...>
void algorithm(...) {
	typedef iterator_traits<I>::category v1;
}

typename 后面声明的字符串作类型处理


## Algorithm - STL中的算法

> function template
>
> Algogithms 对 Containers进行操作，必须由Iterators提供容器的一些性质信息，而Iterators也必须能够回答算法的这些提问

### Iterator_category

#### 五大迭代器种类以及继承关系

> struct input_iterator_tag
>
> -
>
> struct forward_iterator_tag : input_iterator_tag
>
> struct bidirectional_iterator_tag :  forward_iterator_tag
>
> struct random_acess_iterator_tag : bidirectional_iterator_tag
>
> -
>
> struct output_iterator_tag
>
> > write-only 不允许使用该迭代器读取数据

#### 类型名称

> ```c++ 
> #include<typeinfo>
> typeid(iterator).name()  //获得对应迭代器的类型名称
> //不同编译环境下有不同的类型名称，不过核心部分相同，一些编号不同

容器的迭代器种类

input_iterator_tag

iostream

-

forward_iterator_tag

hashtable

单向链表forward_list

bidirectional_iterator_tag

rb_tree

双向链表list

random_acess_iterator_tag

array

vector

deque

-

output_iterator_tag

ostream

Iterator_category对Algorithm的影响

distance

//distance 计算两个迭代器之间的距离
template<class iterator>
iterator_traits<iterator>::difference_type distance(iterator ite1,iterator ite2) {
 typedef typename iterator_traits<iterator>::iterator_category category; //获取category类型
 //通过__distance完成对类型不同迭代器的distance操作，需要传入临时类型对象
 return __distance(ite1,ite2,category());
}

template<class iterator>
iterator_traits<iterator>::difference_type __distance(iterator ite1,iterator ite2,random_access_iterator_tag) {
 return ite2 - ite1;
}

template<class iterator>
iterator_traits<iterator>::difference_type __distance(iterator ite1,input_iterator) {
 typename iterator_traits<iterator>::difference_type n = 0;
 while(ite1 != ite2) {
     ite++;
     n++;
 }
 return n;
}

advance

//advance 移动指针
template<class iterator,class distance>
void advance(iterator& ite,distance dis) {
 typedef typename iterator_traits<iterator>::iterator_category category; //获取category类型
 //通过__advance完成对类型不同迭代器的advance操作，需要传入临时类型对象
 return __advance(ite,dis,category());
}

template<class iterator,class distance>
void advance(iterator& ite,distance dis,input_iterator) {
	while(--n) {
     ite++;
 }
}

template<class iterator,class distance>
void advance(iterator& ite,distance dis,bidirectional_iterator_tag) {
	if(n>0) {
     while(--n) {
     ite++;
 }
 }else {
     while(++n) {
     ite--;
 }
 }
}

template<class iterator,class distance>
void advance(iterator ite,distance dis,random_access_iterator_tag) {
	ite += dis;
}

注意:算法只能够暗示该算法需要接收的模板迭代器类型，无法控制或者说限制调用时传入的模板类型

算法部分源码剖析

accumulate

累积运算将指定范围的数据进行累积运算并将结果返回

#include <numeric> //std::accumulate

class<class InputIterator,class T,class BinaryOperator>
T accumulate(InputIterator first,InputIterator last,T init,BinaryOperator binary_op) {
    for(;first!=last;first++) {
        init = binary_op(init,*first);
    }
    return init;
}

//调用
int init = 0;
int num[] = {10,20,30};
accumulate(num,num+3,init);

//binary_op可以传入函数入口地址，或者仿函数对象，或者不传入使用默认的二元操作函数plus<>();

for_each

遍历操作将指定指定范围的每个数据进行相同操作

#include<algorithm> //std::for_each

template<class InputIterator,class Function>
Function for_each(InputIterator first,InputIterator last,Function f) {
    for(;first!=last;++first) {
        f(*first);
    }
    return f;
}

replace,replace_if,replace_copy

对指定指定范围内的数据进行替代与拷贝

replace 指定范围的数据使用新值替代指定的旧值

replace_if 指定范围的数据满足条件的替换需要传入一个可返回true/false的函数对象

replace_copy 对指定范围的数据进行拷贝，等于指定值时使用新值替代否则原样拷贝

count,count_if

对指定指定范围内的数据进行计数

count 计数等于指定值的元素个数

count_if 计数满足指定条件的元素个数

序列容器没有内置的count,count_if函数重载

关联式容器内置有对count,count_if函数的重载

//count
template<class InputIterator,class T>
typename iterator_traits<InputIterator>::difference_type count(InputIterator first,InputIterator last,const T& value) {
typename iterator_traits<InputIterator>::difference_type n = 0;
 for(;first!=last;++first) {
     if(*first==value) {
         n++;
     }
 return n;
 }
}

//count_if
template<class InputIterator,class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first,InputIterator last,Predicate pre) {
    
typename iterator_traits<InputIterator>::difference_type n = 0;
 for(;first!=last;++first) {
     if(pre(*this)) {
         n++;
 	}
 return n;
 }
}

find,find_if

对指定指定范围内的数据进行循序式查找

find 查找等于指定值的元素

find_if 查找满足指定条件的元素

序列容器没有内置的find,find_if函数重载

关联式容器内置有对find,find_if函数的重载
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//find
template<class InputIterator,class T>
InputIterator find(InputIterator first,InputIterator last,const T& value) {
 for(;first!=last;++first) {
     if(*first==value) {
         return first;
     }
 }
}

//find_if
template<class InputIterator,class Predicate>
InputIterator find_if(InputIterator first,InputIterator last,Predicate pre) {
    
 for(;first!=last;++first) {
     if(pre(*this)) {
		return first;
 	}
 }
}

sort

对指定指定范围内的数据进行排序

暗示要求的迭代器类型为random_acess_iterator_tag，所以其他容器无法调用该方法

list,forward_list内置有对sort函数的重载

其余容器没有内置的sort函数重载

关联容器内的元素已经是”有序”的不要再去调用sort排序了

binary_search

对指定指定范围内的有序数据进行二分查找

//内部实际为调用lower_bound/upper_bound
//lower_bound(first,last,val); 返回不违反当前排序状态的情况下val能插入的最低点
//upper_bound(first,last,val); 返回不违反当前排序状态的情况下val能插入的最高点
template<class ForwardIterator,class T>
bool binary_search(ForwardIterator first,ForwardIterator last,const T& value) {
	first = lower_bound(first,last,value);
    return (first!=last && !(val<*first))
}

Functors 仿函数

只为算法服务，提供规范标准

STL标准库中Functors的基本种类

算数类

//+
template<class T>
struct plus:public binary_function<T,T,T> {
    T operator() (const T& x, const T& y) {
        return x + y;
    }
};

逻辑运算类

//&&
template<class T>
struct logic_and:public binary_function<T,T,T> {
    T operator() (const T& x, const T& y) {
        return x && y;
    }
};

相对关系类

//==
template<class T>
struct equal_to:public binary_function<T,T,bool> {
    bool operator() (const T& x, const T& y) {
        return x == y;
    }
};

GNU C++独有的Functors的种类

keyofvalue

// identity
template<class T>
struct identity :public unary_function<T, T> {
	const T& operator() (const T& x) const {
		return x; //其实x这里传入的是value，再由value取key
	}
};

//selectlst
template<class T1,class T2>
struct pair() {
    
    pair():first(T1()),second(T2()){}
    pair(const T1& a,const T2& b):first(a),second(b){}
    
    typedef T1 first_type;
    typedef T2 second_type;
    
    T1 first;
    T2 second;
};

template<class Pair>
struct selectlst : unary_function<Pair, typename Pair::first_type> {
	const typename Pair::first_type& operator() (const Pair& x) const{
    	return x.first;
	}
};

Functors的可适配(adaptable)条件

Functors必须继承unary_function或者binary_function中的一个

因为父类中typedef的类型会被适配器提问到

//运算只有一个操作数
template<class Arg,class Result>
struct unary_function {

 typedef Arg argument_type;
 typedef Result result_type;
}

//运算具有两个操作数
template<class Arg1,class Arg2,class Result>
struct binary_function {

 typedef Arg1 first_argument_type;
 typedef Arg2 second_argument_type;
 typedef Result result_type;
}

Adapter 适配器

复合 + “改造”

Container Adapters

复合了底层容器的”容器”

Stack,Queue

//stack
template<class T,class Sequence=deque<T>>
class stack{
...
public:
    typedef Sequence::value_type value_type
    typedef Sequence::size_type size_type
    typedef Sequence::reference reference
    typedef Sequence::const_reference const_reference
protected:
    Sequence c;
public:
    bool empty() {return c.empty();}
    size_type size() const{return c.size();}
    reference top() {return c.back();}
    const_reference top() const {return c.back();}
    void push(const value_type& x) {c.push_back(x);}
    void pop() {c.pop_back();}
}

//queue
template<class T,class Sequence=deque<T>>
class queue{
...
public:
    typedef Sequence::value_type value_type
    typedef Sequence::size_type size_type
    typedef Sequence::reference reference
    typedef Sequence::const_reference const_reference
protected:
    Sequence c;
public:
    bool empty() {return c.empty();}
    size_type size() const{return c.size();}
    reference front() {return c.front();}
    const_reference front() const {return c.front();}
    reference back() {return c.back();}
    const_reference back() const {return c.back();}
    void push(const value_type& x) {c.push_back(x);}
    void pop() {c.pop_front();}
    ...
}

Functor Adapters

复合了底层Functor的”Functor”,本身也具有原Functor的性质，只不过叫成了Functor Adapters

binder2nd

绑定二元操作functor的第二个参数为指定值

实际为一个一元操作符的Functor

//count_if
template<class InputIterator,class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first,InputIterator last,Predicate pre) {

typename iterator_traits<InputIterator>::difference_type n = 0;
for(;first!=last;++first) {
if(pre(*this)) {
n++;
	}
return n;
}
}

//调用
int n = count_if(v1.first,v1.last,bind2nd(less<int>(),40));

//bind2nd<>
//辅助函数 用于使用更为简易的参数创建并返回binder2nd<Operation>适配器对象
//创建binder2nd<>对象的类型参数为functor类型，但是普通用户很难知道摸个functor的类型是什么
//对于函数模板,编译器会根据实参传入的对象推断其类型
class<class Operation,class T>
typename binder2nd<Operation> bind2nd(const Operation& op,const T& x) {
tydef typename Operation::second_type arg2_type;
return binder2nd<Operation>(op,arg2_type(x));
}

//binder2nd<>
//为了使该适配器也是adaptable的可是配的，因此该适配器也要继承对应父类模板，来回答问题
class<class Operation>
struct binder2nd:public unary_function<typename Operation::first_argument_type,typename Operation::result_type> {
public:

binder2nd(const Operation& x,typename Operation::second_argument_type y):op(x),value(y){}

typename Operation::result_type operator()(const typename Operation::first_argument_type& x) {
  return op(x,value);
}
protected:
Operation op;
//使用value记录用于原functor的需要绑定的参数
typename Operation::second_argument_type value;
}

not1

取否

//count_if
template<class InputIterator,class Predicate>
typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first,InputIterator last,Predicate pre) {

typename iterator_traits<InputIterator>::difference_type n = 0;
for(;first!=last;++first) {
if(pre(*this)) {
n++;
	}
return n;
}
}

//调用
int n = count_if(c1.first,c1.last,not1(bind2nd(less<int>(),40)));

//not1
template<class Predicate>
unary_negate<Predicate> count_if(const Predicate& pre) const{
    return unary_negate<Predicate>(pre);
}

template<class Predicate>
struct unary_negate:public unary_function<typename Predicate::first_argument_type,bool> {
public:
    //单个参数的为了禁止隐式转换而是用explicit修饰符
    explicit unary_negate(const Predicate& pre):op(pre){}
protected:
    Predicate op;
public:
    bool operator()(const typename Predicate::first_argument_type& x) {
    	return !op(x);    
    }
}

bind

c++11提供的新型适配器

std::bind可以绑定

functions

function objects

member functions _1必须是某个object地址

data members _1必须是某个object地址
1
2
3
4
5
6
using namespace std::placeholder; //adds visibility of _1,_2 占位符

int n = count_if(v1.first,v1.last,bind2nd(less<int>(),40));
//等价于
auto fn_ = bind(less<int>(),_1,40);
int n = count_if(v1.first,v1.last,fn_);

Iterator Adapters

Reverse_iterator

逆向”迭代器”

rbegin(); 返回指向正向容器尾元素的迭代器

rend(); 返回指向正向容器首元素上一个位置的迭代器

++实现从rbegin() -> rend()的遍历
1
2
3
4
5
6
7
8
//reverse_iterator为适配器
reverse_iterator rbegin() {
return reverse_iterator(end());
}

reverse_iterator rend() {
return reverse_iterator(begin());
}

>template<class Iterator>
struct reverse_iterator {
public:
 //为了使该适配器仍可适配-改造 仍需要具备迭代器基本的5个关联类型
 typedef typename iterator_traits<Iterator>::iterator_category category;
   	typedef typename iterator_traits<Iterator>::value_type value_type; //数据类型
   	typedef typename iterator_traits<Iterator>::pointer pointer; //指向node类型的指针
	typedef typename iterator_traits<Iterator>::reference reference; //node类型的引用类型
	typedef typename iterator_traits<Iterator>::difference_type difference_type; //两个迭代器之间距离的类型

 typedef Iterator iterator_type;
     typedef reverse_iterator<Iterator> self;
   public:
    //可使用正向迭代器初始化逆向迭代器也可使用逆向迭代器初始化
 reverse_iterator(const Iterator& x):current(x){}
    reverse_iterator(const self& x):current(x.current){}
   
    //取出相应的正向迭代器
     iterator_type base() const{
        return current;
    }
   
    //逆向迭代器返回对应正向迭代器的前一位的值
     reference operator*() const{
        self temp = current;
        return *--temp;
    }
    pointer operator->() const{
        return &(operator*())
    }
    self& operator++(){
        --current;
        return *this;
    }
    self& operator--() {
        ++current;
        return *this;
    }
    self operator+(const value_type& x) {
        return self(current - x);
    }
    self operator-(const value_type& x) {
        return self(current + x);
    }
   protected:
    Iterator current;

   }

inserter

copy

a copy to b
copy(a.begin(),a.end(),b.begin());

参数12指定a中copy的范围

参数3指定指向目的内存的起始迭代器

但是参数3为默认迭代器时必须保证b有充足的内存空间因为copy底层为逐个元素的赋值操作

inserter适配器

inserter适配器对迭代器的赋值操作进行了重载，使赋值操作包含insert方法

看似赋值实则插入

//inserter
template<class Container,class Iterator>
insert_iterator<Container> inserter(const Container& x,const Iterator& y) {
    typedef typename Container::iterator iter;
    //需要对传入的迭代器类型进行校验，进行类型转型，失败则提早停止预防运行出错
    return insert_iterator<Container>(x,iter(y));
}

template<class Container>
struct insert_iterator{
public:
    insert_iterator(Container& x,const typename Container::iterator i):container(&x),ite(i){}
    typedef output_iterator_tag iterator_type;
    
    insert_iterator<Container>& operator= (const Container::value_type& x) {
        ite = container -> insert(ite,x);
        ++ite;
        return *this;
    }
protected:
    Container* container;
    typename Container::iterator ite;
}

X适配器

ostream_iterator

绑定cout输出流对象,在执行copy操作时可以将被copy的元素输出

啥也不是，就一个有赋值运算符重载的一个玩意儿

template<class T,class charT=char,class traits=char_traits<charT>>
struct ostream_iterator {

public:
    //...
	typedef basic_ostream<charT, traits> ostream_type;
	typedef charT char_type;
	typedef traits traits_type;

	ostream_iterator(ostream_type& s) :out_stream(&s), delim(0) {}
	ostream_iterator(ostream_type& s,const charT* delimm) :out_stream(&s), delim(delimm) {}
	ostream_iterator(const ostream_iterator<T>& x):out_stream(x.out_stream), delim(x.delim) {}

	~ostream_iterator() {}

	ostream_iterator<T>& operator=(const T& value) {
		*out_stream << value;
		if (delim != 0) {
			*out_stream << delim;
		}
		return *this;
	}

	ostream_iterator<T>& operator*() {
		return *this;
	}

	ostream_iterator<T>& operator++ () {
		return *this;
	}
	ostream_iterator<T>& operator++ (int) {
		return *this;
	}
protected:
    //内含指向标准输出流对象的指针和分隔符的记录
	basic_ostream<charT, traits>* out_stream;
	const charT* delim;
};

//调用
vector<int> v{ 1,2,3,4,5 };
ostream_iterator<int> out(cout, ",");
copy(v.begin, v.end, out);

istream_iterator

绑定cin输入流对象

当创建istream_iterator<>对象时已经在读取数据了

vector<int> c{ 1,2,3,4,5 };
istream_iterator<int> iit(cin),eos; //读取用户输入的数据
//eos 未绑定输入流对象输入做结束标志用
copy(iit,eos,inserter(c,c.begin())); //将用户输入的数据插入到指定容器中去
//同样也需要对=,++,*做重载操作

STL Surround

hash function

两大型式

functor

class CustomerHash {
    size_type operator()(const Customer& Customer) const{
        return ...;
    }
}

//使用
unorderedset<Customer,CustomerHash> cus;

function

size_type CustomerHash(const Customer& Customer) {
        return ...;
    }
//使用
unorderedset<Customer,size_type(*)(const Customer&)> cus(20,CustomerHash);

An universal hash function

1	std::hash<datatype>()(data)

目前标准库中已经有了用于每种基本类型的hashcode计算functor

而对于自定义对象的hashcode计算不能仅仅为各数据成员的hashcode计算值之和

通过可变类型参数实现hash_val的参数类型与参数数量的任意

#include<functional> //引入相应的头文件

class CustomerHash {
	std::size_t operator()(const Customer& c) const {
		return hash_val(c.first, c.second, c.third);
	}
};

//计算hashcode的函数模板
template<class T>
void hash_combine(std::size_t& seed, const T& val) {
	seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

//辅助接口函数
template<class... Types>
std::size_t hash_val(const Types&... args) {
	std::size_t seed = 0;
	hash_val(seed, args...);
	return seed;
}

template<class T, class... Types>
void hash_val(std::size_t& seed, const T& val, const Types&... args) {
	hash_combine(seed, val);
	hash_val(seed, args...);
}

template<class T>
void hash_val(std::size_t& seed, const T& val) {
	hash_combine(seed, val);
}

Tuple

元组不同数据类型数据的组合

Interface testing

//tuple对象的创建
tuple<string, int, int> t("123",10,11);
auto t2 = make_tuple("123");

//对象成员的获取
//get<num>(tuple_obj) num为从0开始的序号索引 
int i = get<1>(t);
int a, b;
string c;

//tie(args...) = tuple_obj 元素绑定
//实现用args参数"绑定"tuple中的元素 赋值性的绑定 即绑定后值变化互不影响
tie(c, a, b) = t;
//eg:
get<0>(t) = "5";
cout << c << endl;
//结果仍为123

//stl中tuple对运算符的重载
//t < t2
//t = t2;

//获取tuple中元素个数
typedef tuple<string, int, int TupleType
cout << tuple_size<TupleType>::value << endl;

//获取某个元素的类型
//...


//获取tuple的head元素
string s = t.head(); // s="123"
//获取tuple的tail部分tuple对象
auto tail = t.tail(); // tail = tuple<int, int> t(10,11)
//获取tail的head元素
int se = tail.head();
//值得注意的是head(),tail()在c++17中不再使用该名称

Internal structure - G4.8

通过可变类型参数可动态拆分特性而构建的一个继承体系结构

即每一个数据类型的数据单独封装为一个类

//tuple对象的创建
tuple<int, float, string> t(41,6.3,"nico");

//tuple
//通过可变参数的可动态拆分特性递归实现继承体系
template<class Head,class... Tail>
class tuple<Head,Tail...> : private tuple<Tail...> {
public:
    typedef tuple<Tail...> inherited;
    
    tuple() {}
    tuple(const Head& a,const Tail&... args):m_head(a),inherited(args...){}
    
    //返回tuple对象的head元素
    Head head() {
        return m_head;
    }
    
    //通过上转型为父类类型截断本类数据
    //返回不含m_head的含tail部分的tuple对象
    inherited& tail() {
        return *this;
    }
protected:
    Head m_head;
};

//当递归至父类为tuple<>时作停止递归的处理
template<>
class tuple<> {};

继承图示

Type triats

它所提供的判断功能，在编译期间可以检查出是否是正确的类型，以便能编写更为安全的代码。

Interface testing

G2.9

1 2	//询问 __type_traits<int>::has_trivial_copy_constructor //return 0/1

C++11

1 2	//询问 is_copy_constructible<T>::value //return 0/1

Structure G2.9

//可以询问萃取机对应类型的某些性质类型从而做出判断
template<class T>
struct __type_traits {
    typedef __true_type this_dummy_member_must-be_first;
    typedef __false_type has_trivial_default_constructor;
    typedef __false_type has_trivial_copy_constructor;
    typedef __false_type has_trivial_assignment_constructor;
    typedef __false_type has_trivial_destructor;
    typedef __false_type is_POD_type;
}
//POD - plain old data
//trivial 不重要的/平凡的
//特化
template<>
struct __type_traits<int> {
    typedef __true_type has_trivial_default_constructor;
    typedef __true_type has_trivial_copy_constructor;
    typedef __true_type has_trivial_assignment_constructor;
    typedef __true_type has_trivial_destructor;
    typedef __true_type is_POD_type;
}

//询问
__type_traits<int>::has_trivial_copy_constructor

Structure C++11

type traits categories

Primary type categories

is_array

is_class
Type properties

is_abstract

is_const
Type features

is_copy_constructible

is_move_constructible
Composite type categories

is_compound

is_object

is_void

将类型丢给is_void萃取机可判断是否为void类型

is_void -> __is_void_helper<…>::type -> false_type/true_type ->表示继承关系

//remove_cv去除const与volatile类型的影响,remove_cv本身也是萃取机
template<class T>
struct is_void : public __is_void_helper< typename remove_cv<T>::type >::type
{};

//泛化
template<class T>
struct __is_void_helper : public false_type{};

template<class T>
struct remove_cv {
   	typedef typename remove_const< typename remove_volatile<T>::type >::type type;
}
//特化
template<>
struct __is_void_helper<void> : public true_type{};

template<class T>
struct remove_const {
    typedef T type;
}
//特化
template<class T>
struct remove_const<T const> {
    typedef remove_const< typename remove_volatile<T>::type >::type type;
}

template<class T>
struct remove_volatile {
    typedef T type;
}
//特化
template<class T>
struct remove_volatile<T volatile> {
    typedef T type;
}

Moveable elements

移动构造函数

浅拷贝，仅拷贝指针且拷贝后切断原对象的指向即将原对象的指针设为NULL

确保movecopy后原对象不再使用，所以一般用临时对象做movecopy

拷贝构造函数

深拷贝

vector中的movecopy

深拷贝

调用std::__uninitialized_copy_a(…) 即copy函数来进行逐个元素的赋值

浅拷贝

vector中的三个指针进行简单的swap()交换 ·