STL_容器 containers

2023-09-28 10:56:58

容器containers

任何特定的数据结构都是为了实现某种特定的算法。STL容器即是将运用最广的一些数据结构实现出来。
根据数据在容器中的排列特性，将数据结构分为序列式和关联式两种。

序列式容器 Sequence containers

C++ 内建:array( build-in)
标准的：vector list deque
非标准：slist
配接器：stack queue
以算法实现：heap(内涵一个vector ) priority-queue(内涵heap)
序列容器，其中的元素都可序（prdered）,但未必有序。

vector

vector数据安排和操作方式和array 相似，唯一的区别是空间的运用更加灵活。
array 是静态空间，一旦配置之后不能改变（使用者改变时，需要自己设定新的空间，并且拷贝然后再归还空间。）
vector是动态空间，随着元素的加入，它的内部机制会扩充空间，以容纳新的元素。
vector 实现技术关键在于对大小的控制及重新配置，是数据移动效率

迭代器

vector 维护的是一个连续线性空间。所以不论及元素，型别是什么，普通指针都可以作为容器的迭代器，而且满足所有条件。
vector 提供 random access iterator 迭代
迭代器所支持的功能，普通指针都支持
使用时vector<int>::iterator ivite ivite 就是int *
插入删除会造成原迭代器失效

数据结构

vector 数据结构采用连续线性空间
使用 start finish 指向迭代器以使用的空间 end_of_storage 指向备用空间的末尾
容量（capacity）: 配置空间可能比实际需求空间更大一些，以备将来扩充空间：容量永远大于等于大新
增加元素时，如果超过当时的容量，则容量会扩充至两倍。如果两倍容量仍不足，就扩张至足够大的容量。

内存管理 constructor , push_back

vector 构造有多种

// 允许指定空间大小并附加初值
vector(size_type n,const T& value)
// 连续空间初始化
int iv[5] = {1,2,3,4,5};
list<int> ls(iv,iv+5)

push_back 元素增加也影响内存
配置原则检查，备用空间。有直接分配。没有备用空间，原空间大小为0，则配置一个元素。如果原大小不为零，则配置原大小的两倍。前半段用来放置原数据。后半段准备用来放置新数据。
注意：动态增加大小，并不是在原空间之后连续新的空间。而是以原大小的两倍配置另一块儿交大的空间，然后将原内容拷贝过来。然后在原内容之后勾到新的元素。因为是空间是新的。所以空间一旦重新配置，所有指向源容器的迭代器就都失效了。因为原容器中的内容已经换了一个地址储存。

元素操作

void push_back(const T&x);
void pop_back() // 将尾端元素去掉并调整大小
iterator erase(iterator first,iterator last) // 清除[first,last) 中的内容，并将后面的内容放入
iterator erase(iterator pos) // 清除指定的 指向清除后的一个
void clear() // 清除所有元素
void insert(iterator pos,size_type n ,const T&x) // 从pos 开始插入n个x

list

非连续空间的现行结构链表。内部使用的节点。SGI STL 中是双向链表

迭代器

不能再使用普通指针作为迭代器，因为结点不保证在存储空间中连续
迭代器必须可以指向list 结点，并完成递增，递减，取值，成员存取
STL list 是一个双向链，list 提供bidirectional iterator
重要特性：因为指向空间的地址不变，所有插入删除不会导致原迭代器失效

数据结构

SGI STL 不仅是一个双向链表。，而且还是一个环状双向链表
只需要一个指针就可以呈现整个链表
因为有前开后闭原则，只需要一个标记，可以在环装链表的尾端加入一个空白结点表示结束迭代器就可以了

内存管理

// constructor
list() // 生成空的空白链表，有一个空结点
void push_back(const T&x) // 在结尾插入一个链表
iterator insert(iterator pos,const T& x){
	link_type tmp = crette_node(x); // 产生一个结点内容为x
	// 调整双指针插入
	tmp->next = pos.node;
	tmp->prev = pos.node->prev;
	(link_type(pos.node->prev))->next = tmp;
	pos.node->prev = tmp;
	return tmp;
}

元素操作

// push_front
void push_front(const T& x) //头插入
// push_back
void push_back(const T& x)// 尾插入
// erase
iterator erase(iterator pos) // 移除输入 返回下一个
// pop_front
void pop_front() // 移除头结点
// pop_back
void pop_back() // 移除尾结点
// clear
void clear() // 清除所有结点
// remove
void remove(const T& value) // 删除值为value 的结点
// unique
void unique() // 移除连续相同保留一个
// splice
void splice(iterator pos,list & x) // 将x 拼接到pos 之前
// merge
void merge(list x) // 合并两个增项链表  x 合并到merge
// reverse
void reverse() // 逆序链表
// sort
void sort() // 链表排序

deque

vector 是单项开口的连续线性空间，deque 是一种双向开口的连续线性空间
双向开口，意思是可以在头尾两端分别做元素的插入和删除操作;deque (双端队列)

deque 和 vector 差异

deque 允许常数时间内对头端进行元素的插入和移除操作
deque 没有容量的概念，空间是动态，以链状结合到一起的
deque 也支持ramdon access iterator 但是迭代器不是普通的指针，比vector 复杂，进行排序操作为了提高效率，可以先复制到哦vector 利用STL sort 算法，在复制回deque

中控器

deque 在逻辑上看是连续的线性空间，同样的连续空间C++ 中有array vector

空间成长性

array 空间不可成长
vector 可成长但是：事实是
（1）另寻觅更大的空间
（2）将原数据复制过去
（3）释放原空间三步再加上每次配置新空间都留下一些余裕，成长代价是高昂的
deque 是一段一段连续空间构成的，有必要在前后配置空间，就配置一段新的连续空间，串联在空间的头尾。并且提供随机存取，避开重新配置，复制，释放，但是特点是迭代器复杂

map

分段连续空间的保证map (node 结点元素表，每个node 都可以指向另一段较大的连续空间——缓冲区)
缓冲区deque 存放实际内容空间SGI STL 可以指定大小，默认0使用512bytes 大小
map 型别是T** 指向指针的指针，指向的指针指向型别为T 的一块空间
map 使用满了STL 支持重新分配更多的结点

迭代器

支持ramdon access iterator 支持operator[] (偏移加间接引用)
维持deque 是分段连续空间，迭代器operator++ 和 operator-- 完成这个复杂操作
完成功能：指出缓冲区在哪，判断是否在缓冲区边缘，跳跃到上一个或者下一个缓冲区，了解控制map 保存的信息
缓冲区大小：维持在512kb 的整数倍，保存元素大小个数
遇到边缘判定是否需要跳到下一个缓冲区
迭代器有当前结点 start finsh 中有（结点的cur first last node(指向map)）
迭代器具有四个参数cur first last node

数据结构

是一个逻辑上连续，实际分段的连续空间
维护start finsh 一个指向第一个缓冲区第一个结点，一个指向最后一个缓冲区最后一个元素结点map 不足时需要分配一个更大的map

内存管理

// ctor 构造
deque<int,alloc,8> ideq(20,9); // 缓冲区大小为8个元素，保留20个元素空间，初始值都为9
// 尾添加
void push_back(const value_type& t)
// 头添加
void push_front(const value_type& t)

map 空间不足时

配置一块新的空间
将原map 拷贝到新的空间
释放原map
设定新的map 起始与大小

元素操作

// find
iterator find(iterator frist,iterator last,const T& value)
// pop_back // 析构，是该缓冲区最后一个结点时释放缓冲区空间
void pop_back(){
	if(finish.cur != finish.first){
		--finish.cur; // 调整指针，相当于删除最后一个元素
		destroy(finish.cur); // 将最后元素析构
	}
	else{
		// 缓冲区没有任何元素时
		pop_back_aux() ; // 释放缓冲区
	}
}
// pop_front
void pop_front()
// clear
void clear() // 保留一个缓冲区，无任何元素，恢复到初始状态
// erase
iterator eraser(iterator pos) // 删除某个元素
// insert
iterator insert(iterator pos,const value_type& x) // 在pos 之前插入元素 x

stack

stack 是一种先进后出的数据结构不允许遍历
SGI 中有有两种可以实现的底层数据结构，SGI 中一般称stack 为容器配接器
以某种容器（SGI 中deque 或 list）完成所有工作，具有这种修改某物接口，形成另一种风貌之性质者，称为配姐器
底层有双端队列或者链表实现
stack 没有迭代器

bool empty() // 判断是否为空
size_type size()  // 多少元素
reference top()   // 返回栈顶元素值
const_reference top() 
void push(const value_type& x)  // 存入
void pop() // 弹出

queue

queue 先进先出数据结构
底层容器也有两种 deque 和 list 所有queue 也是容器配接器

bool empty() // 判断是否为空
size_type size()  // 多少元素
reference front()   // 返回元头素值
const_reference front() 
reference  back()   // 返回尾元素值
const_reference back() 
void push(const value_type& x)  // 存入
void pop() // 弹出

heap(implicit representation)

heap 不属于STL 容器组件，可以说是一种算法，是priority queue 的助手
priority queue （优先队列）：允许用户以任何次序将任何元素推入容器，但是取出一定是从优先权最高的（也就是数值最高的元素）开始取
binary max heap 正式具有这样的特性，适合作为优先队列的底层机制

priority queue 优点（与二叉搜索树）：

binary search tree 的输入需要足够的随机性
binary search tree 实现不容易
priority queue 的复杂度在queue 和 binary search tree 之间

binary heap 是一种完全二叉树（除了最底层的叶子结点之外，是填满的，最底层的叶子结点，由左至右又不得有空隙）

存储结构

因为完全二叉树的性质，设计时可以使用array 作为存储结构
设计当数组0号元素设为无穷大（或无穷小）（SGI STL 中使用的不是该技巧），从1号元素开始存储根节点：当完全二叉树结点处于i 时，该节点的左结点为2i 又结点为2i+1 父亲结点一定位于i/2 （取整）以array 表述tree 为隐式表达法

实现一个优先队列工具，只需要: 一个array 和一组堆heap 算法
因为array 具有无法动态改变大小的缺点，堆的存储空间使用vector

分类

heap 可以分为 max-heap 和min-heap 两种
max-heap 每个结点的键值都大于或等于其子节点的键值，最大值在根节点，并且总是位于底层array 或者 vector 的起头处（SGISTL 支持）
min-heap 每个节点的键值都小于或等于其子节点的键值，最小值在根节点，并且总是位于底层array 或者 vector 的起头处

heap 算法

heap算法：用来插入元素，删除元素，取极限值，将一整整租数据排列成一个heap

push_heap 插入元素

为了满足完全二叉树条件，新加入的元素一定要放在最下一层作为叶子结点，并且填补在由左至右的第一个空格，也就是 把新的元素，插入在vector 的 end() 处
为了新元素符合其位置：满足max-heap 每个结点的键值都大于或等于其子节点键值，执行上溯（percolate up）程序：
percolate up (上溯)：将新结点拿来与其父结点比较，，如果其键值（key）比父节点大，就父子对换位置，一直上溯直到不需要对换或者直到根节点为止
percolate up 上溯操作

template <class RandomAccessIterator,class Distance,class T>
void __push_heap(RandomAccessIterator first,Distance holeIndex,Distance topIndex,T value){
/*
	first 底层空间第一个位置
	holeIndex 新值位置，待交换的结点位置
	topindex 根节点位置
	value 新值
	// 第一个值在0 索引位置
*/
	Distance parent = (holeIndex - 1) / 2; // 父节点的值
	while(holeIndex > topIndex && *(first+parent) < valu){
		// 不是根节点 且 父亲值小于新值
		// max-heap 实现
		*(first + holeIndex) = * (first + parent); // 待交换的位置给父亲的值
		holeIndex = parent; // percolate up: 待交换位置变为父亲
		parent = (hodeIndex - 1)/2; // 待交换位置的父亲	
	} // 直到持续到顶，或者满足heap 的特性
	*(first + holeIndex) = value; // 令待交换位置为新的值，完成插入操作
}

pop_heap

弹出时将根节点弹出，用最下层最右边的结点补充到弹出的位置，保证完全二叉树性质
为保证max-heap 次序特性，执行 percolate down 下溯程序：
percolate down 下溯：将待交换结点和较大的子节点对换，并且持续下放，直到叶结点为止，然后将前述被割舍的元素给放到叶结点，在对这个结点执行一次上溯 percolate up
percolate down 下溯
adjust 调整

template <class RandomAccessIterator ,class Distance , class T>
void __adjust_heap(RandomAccessIterator first,Distance holeIndex,Distance len,T value){
/*
first 数组第一个位置
holeIndex 待交换位置
len 全部元素的范围
value 待交换的值 
*/
	Distance topIndex = holeIndex;
	Distance secondChild = 2 * holeIndex + 2; // 待交换结点右结点的值
	while(secondChild < len){
		// 比较待交换结点左右两个子值，然后以secondChild 代表较大子节点
		if(*(first + secondChild) < *(first + (secondChild - 1))){
			secondChild --;
		}
		// percolate down:令较大子值为待交换的位置，待交换位置下移至较大的子节点位置
		*(first + holeIndex) = *(first + sencondChild);
		holeIndex = secondChild;
		// 找到新待交换结点右结点
		sencondChild = 2 * (secondChild + 1);
	}
	if(secondChild == len)	{ // 没有右子节点，只有左子节点
		// percolate down：令左子值为待交换值，在待交换值下移至左子节点除
		*(first + holeIndex) = *(first + (sencondChild -1));
		holeIndex = secondChild - 1;
	}
	//在执行一次percolate up 操作
	__push_heap(first,holeInex,topIndex,value);
}

sort_heap

如果持续对整个heap做pop_heap 操作，每次操作范围从后向前缩减一个元素（因为pop_heap会把键值最大的元素放在底部容器的最尾端），整个程序执行完就有一个递增序列

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,RandomAccessIterator last){
	while(last - first > 1)
	{
		pop_heap(first,last -- );
	]
}

make_heap

将一段现有的数据( vector )转化为一个heap

template<class RandomAccessIterator,class T,class Distance>
void __make_heap(RandomAccessIterator first,RandomAccessIterator last, T * ,Distance *){
	if(last - first < 2) return ;
	Distance len = last - first;
	// 找出第一个需要重排的子树头部，以parent 标出
	// perlocate down 计算
	Distance parent = (len - 2)/2;
	while(true){
		// 重新调整以parent 为首子树
		__adjust_heap(first,parent,len,T(*(first + parent)));
		if(parent == 0) return;
		parent--;
	}
}

priority_queue

一个拥有权值观念的queue 允许加入新元素，移除旧元素，审视元素值
是一种容器配接器，内部权值，内部是max-heap 存储空间vector

// 使用
#include <queue>

priority_queue<int> ipq(ia,ia+9);
bool empty()
size_type size()
const_reference top()
void pop()
void push(const value_type& x)

slist

单向链表SGI STL 提供
迭代器是forward iterator
优势：单向链表所消耗空间更小，某些操作更快，元素操作不使迭代器失效
STL 习惯插入时会将新元素插入指定元素之前
但是单向链表前插入会从头开找，所有slist 提供insert_after() erase_after()
不提供push_back() 只有push_front() 元素次序与插入元素相反

关联容器 Associative containers

非公开：RB-tree
标准的：set map multiset multimap(内部都有RB-tree)
非标准：hashtable hash_set hash_map hash_multiset hash_multimap(hash_ 内部都有hashtable)

标准STL 关联容器分为set(集合)和map(映射表)两大类，以及两大类的衍生题，multiset(多键集合)和multimap(多键映射表) 。这些容器的底层机制均使用RB-tree(红黑树)完成，RB-tree 也是一个独立的容器，但是不开放给外界使用

SGI STL 提供标准规格之列的关联容器：hash table（散列表）：和以散列表为底层机制的hash_set（散列集合），hash_map（散列映射表)，hash_multiset(散列多键集合)，hash_multimap(散列多键映射表)

关联容器：观念上类似关联使数据库（实际上比关联式数据库简单）：每笔数据（每个元素）都有一个键值（key）和一个实值（value）,当元素被插入到关联式容器中时，容器内部结构（可能是RB-tree,也可能是hash-table）便依照其键值大小，以某种特定的规律将这个元素放到合适的位置，关联式容器没有所谓的头尾（只有最大元素和最小元素），所以不会有所谓的push_bakc() push_front() pop_back() pop_front() begin() end() 这样的操作

标准关联式容器内部一般是平衡二叉树，以便提供良好的搜索效率（AVL-tree RB-tree AA-tree）STL 中广泛使用RB-tree
关联容器查找时，应尽量使用容器提供的查找函数。因为算法提供的查找函数只是循环搜索。

内部存储结构为RB-tree 的容器

树

树是一种基础的数据结构：几乎所有的操作系统都将文件存放在树状结构中。几乎所有的编译器都需要实现一个表达式树。文件压缩所使用的哈夫曼算法要用到树状结构。数据库存储的内部结构也是树型的。
红黑树是一种广泛运用，可以提供良好的搜索效率的树状结构。

一些术语

树由节点nodes和边edges构成。
根节点：整棵树有一个最上端的节点。
方向性的边：每个节点可以拥有具有方向性的边，用来和其它节点相连。
父节点 parent：连接中位于上方的节点。
子节点：连接中位于下方的节点。
叶结点 leaf：无子节点称作叶节点。
二叉树：子节点最多只允许存在两个的树
兄弟结点siblings：具有相同父节点的两个节点。
根节点到任意节点具有唯一路径。
路径长度：路径所经过的边数。
深度：根节点到任意节点的路径长度。
根节点的深度永远是0
高度：某节点到其叶子结点的路径长度称为该结点的高度。
结点大小size：该节点所有子代节点，包括自己的节点点总数。

二叉树

任何节点最多只允许两个子节点，这两个子节点成为左子节点和右子节点。
可以说一个二叉树如果不为空，便是由一个根节点和左右两棵子树构成的。左右两棵子树可能为空。
编译器表达式树和哈弗曼编码树都是二叉树

二叉搜索树

所谓二叉搜索树可提供对数时间的元素访问和插入。节点放置规则是任何一个节点的键值一定大于其左子树中的每一个节点的键值。并且小于它右子树中的每一个节点的键值；

操作：
查找元素：对数时间，
插入元素：可以从根节点开始，遇到键值较大的就向左，遇到键值较小的就向右一直到尾端。
删除元素：可以分成两个情况。如果只有一个子节点，就将子节点换到删除节点的位置。如果有两个子节点，就把右子树中最小的节点（从柚子节便开始一直向左走走到终端），替换到删除节点的位置。

平衡二叉搜索树

不平衡可能导致搜索效率低下。
平衡：没有任何一个节点过深
不同的平衡条件可能造出不同的效率表现，以及实现难度的不同。
特殊的数据结构：AVL-tree , RB-tree ,AA-tree 一般效率上可以提搞25%左右
平衡二叉搜索树都比不平衡的二叉搜索数实现复杂。插入和删除结点的平均时间也较长。但是可以避免急难应付的高度不平衡的情况。总是保证某种程度的平衡。也使得搜寻时间平均较少。

AVL tree

平衡条件：任何节点左右子树高度相差最多为1
插入和删除节点可能会影响树的平衡。按照定义，每个节点都应该具有平衡的特性。那么只有插入点到根结点路径上的各个节点可能被改变平衡状态。所以只需要调整，最深的那个节点。就可以使整棵树重新获得平衡。
调整被影响的节点中最深的节点。是重要的。
最深的那个节点，最多拥有两个子节点。平衡被破坏，就意味着总有两颗子树高度相差变为了2。那么破坏平衡的情况就可能分为四种

左左——插入点位于被影响平衡最深的节点的左节点的左子树。
左右——插入点位于被影响平衡最深的节点的左节点的右子树
右左——插入点位于被影响平衡最深的节点的右节点的左子树
右右——插入点位于被影响平衡最深的节点的右节点的子右树

通过旋转可以将树恢复平衡，针对四种被影响的情况，可以有两种旋转方式。单旋和双旋
单旋一次旋转：将不平衡的，节点的，不平衡侧的子节点点作为根节点。
双旋：两次单旋组成：左右不平衡的树先不平衡的左子树的右树左旋在整个不平衡的左树右旋
外侧插入：左左和右右：使用单旋解决
内侧插入：左右和右左：使用双旋解决

RB-tree 红黑树

SGI STL 唯一实现的一种搜索树。用作标准关联容器底层。
同样使用单旋和双旋修正操作，但是平衡条件与AVL 树不同
平衡条件：
1. 每个节点不是红色的，就是黑色的。
2. 根节点黑色的。
3. 如果当前节点为红色，它的子节点为黑色。（任意两个红色节点不相邻）
4. 任何一个节点到NULL(树尾端) 的任何路径上，所含黑色的节点数必须相同。
5. NULL(树尾端节点)视为黑色节点——黑哨兵
为保证平衡不满足上述条件。就调整颜色，并旋转树型。

根据规则四新节点初始颜色为红色。新节点的父节点必须为黑色。不符合的就调整颜色，并旋转树型

操作：
查找：宏辉叔可能有不平衡状态，高度差相差大1红黑树的平衡性弱于AVL 树。但是红黑树通常能够导致良好的平衡状态。经验告诉我，红黑树的搜索平均效率和AVL树几乎相等
插入和删除：可以分为多种情况，按情况讨论编写。
节点设计：color parent left right 四个元素 + 加上指向元素值得指针

RB-tree 迭代器

有型别，前进，后退，提领，成员访问等操作
SGI 设计时将迭代器实现分为两层(基层迭代器和正规迭代器)
基层迭代器：实现了increment(增长) decrement(缩减功能) 给正规迭代器使用，这两个功能符号二叉搜索树排列规则
是双向迭代器：访问操作部分类似于list

红黑树空间操作

红黑树的构造方式有两种，一种是以现有的红黑树复制一个新的红黑树，另一种是产生一颗空空如也的树

iterator __insert(base_ptr x,base_ptr y,const value_type& v);
link_type __copy(link_type x,link_type p);
void __erase(link_type x);
void init() // 产生一个结点空间 使得颜色为红色，左右指针指向自己

基础操作

Compare key_comp() const ; // 键值比较
iterator begin() // RB 树起头最左最小结点处
iterator end() // RB 树的终点
bool empty() const // 结点树是否 等于 0
size_type size() const // 结点元素个数
size_type max_size() const() // 默认没有使用-1
pair<iterator,bool> insert_unique(const value_type& x) // 插入，保证结点值唯一
iterator insert_equal(const value_type& x) // 允许重复插入
iterator find(const Key & k) // 查找key

set

集合

特性

所有元素都会根据元素的键值自动被排序。
元素的键值就是实值，实值就是键值。
不允许有两个元素相同的键值。
不可以通过迭代器改变set元素值。也是因为实值就是键值

迭代器

迭代器不允许写入操作，是一种constant iterator(相对于 mutable iterator)
和链表具有相同的性质。当客户端对他进行元素新增操作或者删除操作时，操作之前的迭代器。依然有效（处理被删除元素的迭代器）
STL 为set/multiset 提供了一组算法 set_intersection(交集) set_union(联集)，set_difference(差集)，set_symmetric_difference(对称差集)
几乎所有的集合操作行为都是转调用红黑树的操作行为而已。

各种操作

set<int> iset() // 支持使用数组进行初始化 也可以使用容器初始化
set<int>::iterator ite=set.begin() // 迭代器
key_compare key_comp() // 键值比较
value_compare value_comp() // 值比较
iterator begin() const;
iterator end() const;
reverse_iterator rbegin() const
reverse_iterator rend() const
bool empty() const
size_type size() // 集合元素个数
size_type max_size() 
void swap(set<key,Compare,Alloc>&x)
insert() //插入
void erase() 
void clear()
iterator find(const key_type& x) const // 查找元素
size_type count(const key_type & x) const // x 在集合中的数目
iterator lower_bound (const key_type& x)const
iterator upper_bound(const key_type& x)const
pair<iterator,iterator> equal_range(const key_type& x) const
/*
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
equal_range()二分查找 返回std::pair对象，其first和second成员都成为迭代器，且分别指向输入序列中所有值等于 val 的元素所组成的子序列的起始及末尾（即最后一个元素之后的位置）位置。
*/

map

映射表

特性

所有元素都会根据元素的键值自动被排序
map 都是pair 同时拥有实值和键值
pair 第一元素视为键值，第二元素被视为实值
map 允许两个元素拥有相同的键值

struct pair{
	T1 first;
	T2 second;
}

迭代器

和list 具有差不多的性质
迭代器既不是constant iterator 也不是一种mutable iterator
同样map 的各种操作也是使用红黑树的操作
SGI STL map 以红黑树为底层机制，每个节点的内容是一个pair pair.first 是键值 pair.second 是value

各种操作

支持operator[] 操作

//value_type  是 pair<const Key,T>
// key_type   是 键值型别
// data_type  是 值类型型别

pair<iterator,bool> insert(const value_type& x)
map<string,int>::iterator ite = map.begin();
ite->first // 键值
ite->second; // 数值
pair<iterator,bool> insert(const value_type& x);
key_compare key_comp() // 键值比较
value_compare value_comp() // 值比较
iterator begin() const;
iterator end() const;
reverse_iterator rbegin() const
reverse_iterator rend() const
bool empty() const
size_type size() // 集合元素个数
size_type max_size() 
void swap(map<key,Compare,Alloc>&x)
insert() //插入
void erase() 
void clear()
iterator find(const key_type& x) const // 查找元素
size_type count(const key_type & x) const // x 在集合中的数目
iterator lower_bound (const key_type& x)const
iterator upper_bound(const key_type& x)const
pair<iterator,iterator> equal_range(const key_type& x) const
/*
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
equal_range()二分查找 返回std::pair对象，其first和second成员都成为迭代器，且分别指向输入序列中所有值等于 val 的元素所组成的子序列的起始及末尾（即最后一个元素之后的位置）位置。
*/

multiset

set的含义是集合，它是一个有序的容器，里面的元素都是排序好的，支持插入，删除，查找等操作，就像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。 set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同
删除：如果删除元素a,那么在定义的比较关系下和a相等的所有元素都会被删除
base.count( a )：set能返回0或者1，multiset是有多少个返回多少个．
Set和multiset都是引用头文件,复杂度都是logn
mutiset 和 set 的主要区别在于插入时机制不同， count 返回不同

multimap

允许同一个键值对应多个实值
如果使用 multimap 容器，几乎可以肯定它会包含键重复的元素；否则，就应该使用 map。一般来说，我们想访问给定键对应的所有元素。成员函数 equal_range() 就可以做到这一点。它会返回一个封装了两个迭代器的 pair 对象，这两个迭代器所确定范围内的元素的键和参数值相等。——元素值在返回对象的first 和 second 之间
equal_range()
返回一个范围，该范围包括容器中与k相等的键的所有元素。
multimap 不支持operator[] 因为键值不对应唯一实值
const 返回键键值对应元素值得个数

// 遍历同一个键值的所有实际的值
auto pr = mmap.equal_range("Ann");//遍历所有键为 Ann 的元素
if(pr.first != end(people))
{
    for (auto iter = pr.first ; iter != pr.second; ++iter)
         cout << iter->first << " " << iter->second << endl;
}

内部存储结构为hash-table的容器

hash 结构已统计作为基础，hash table(散列表) 的数据结构，树形结构需要插入元素具有随机性，散列表以统计学作为基础不依赖元素随机性
在插入搜寻删除时也具有常数平均时间

hash table

可以对任何有名项提供·存取和删除操作
操作对象是有名项也可以理解为，字典数据结构
如果使用数据记录元素可能产生两个问题需要解决

数组空间大小占用内存的问题
字符串做索引即使转化为ASII 码也会造成索引值过大的问题

避免数组空间使用过大，可以使用某种映射函数，将大数映射为小数（映射函数）

哈希冲突解决

哈希冲突：将大数映射到小数，会产生不同元素被映射到相同位置，具有相同索引问题

可以使用线性探测，二次探测，开链法等解救冲突问题
不同方法实现容易，但是导出查找效率不同

线性探测

负载系数：元素个数除以表格大小
负载系数除非使用开链法，否则永远在0~1 之间，否则存不下
线性探测：插入，发生哈希冲突，循环往下一个位置寻找，到达尾端就绕到头部继续寻找，知道找到可用空间为止：查找，计算位置与所需元素不符，就循环向后找，直到找到或者遇到空格元素：删除，使用惰性删除，只删除标记号，实际删除等待表格重新整理rehashing 在进行（因为hash table 每一个元素不仅代表自己，也关系到其他元素的排列）

线性探测：需要表格足够大，每个元素都是独立的，但是坏的情况可能遍历整个哈希表寻找，产生 primary clustering (主集团问题) 插入时在连续已经使用过的表格遍历，造成主集团越来越长

二次探测

二次指二次方，对主集团问题进行优化，发生冲突时使用尝试H + i^2 的方式尝试寻找空间
但是二次探测可以解决主集团问，但是可能产生次集团问题（插入时所探测的位置也相同，形成某种浪费），也可以使用复式散列（double hashing）解决问题

开链法（拉链法）

在每一个哈希表格中维护一个list ,发生冲突时在list 上执行元素的插入，搜寻，删除等操作，list 搜寻只是线性操作，如果list 够短速度还是够快的
SGI STL hash table 使用的就是开链法解决哈希冲突

SGI STL hash table

底层空间使用哪个 vector 维护buckets 聚合体，使哈希表具有动态扩张能力，每一个bucket 是list 是hash 自行维护的hash table node

迭代器

hash table 迭代器没有向后操作，hash table 也没有定义所谓的逆向迭代器

底层空间

hash function 全是仿函数在stl_hash_fun.h 中有数个现成的哈希函数

SGL STL 设计中以质数设计哈希表大小，设置28个质数（呈现大约两倍的关系）创建时在质数中找最接近并大于的质数作为哈希表的大小
哈希表初始元素值为0 （null 指针）

表格重建

新增元素后元素个数与哈希表大小比较，大于就重建
需要将旧的哈希表中的元素加入新的哈希表，可以考据一开始就使空间足够大
53 是hash table 提供的第一质数
4294967291 STL 提供的最后一个质数

元素型别

SGI STL 无法处理string double float 类型的元素

hash_set

与set 类似但是hash_set 不在提供自动排序，使用set 为的就是可以快速搜索元素
hash_set 可能有假排序的现象（创建空间默认够大足够离散，从hash table 表头开始遍历，就会出现假排序的现象）
默认缺省大小为100 SGL STL 会自动调整到较为接近的且较大的质数上 193 使用数据小于193 时就会出现假排序

size_type size() const 
size_type max_size() const
bool empty() const
void swap(hash_set & hs)
iterator begin()
iterator end()
pair<iterator,bool> insert()
iterator find(const key_type& key) const
size_type count(const key_type& key) const
pair<iterator,iterator> equal_range(const key_type&key) const
erase()
void resize()
size_type bucket_count() const // 桶数目
size_type max_bucket_count() const // 最大桶数目
size_type elems_in_bucket(size_type n) const

hash_map

与map 类似但是hash_map不在提供自动排序，使用set 为的就是可以快速搜索元素
hash_map 可能有假排序的现象（创建空间默认够大足够离散，从hash table 表头开始遍历，就会出现假排序的现象）
默认缺省大小为100 SGL STL 会自动调整到较为接近的且较大的质数上 193 使用数据小于193 时就会出现假排序

size_type size() const 
size_type max_size() const
bool empty() const
void swap(hash_map & hm)
iterator begin()
iterator end()
pair<iterator,bool> insert()
iterator find(const key_type& key) const
size_type count(const key_type& key) const
pair<iterator,iterator> equal_range(const key_type&key) const
erase()
void resize()
size_type bucket_count() const // 桶数目
size_type max_bucket_count() const // 最大桶数目
size_type elems_in_bucket(size_type n) const

hash_multiset 与 hash_multimap

性质同上，支持重复元素插入而以

码农公寓

容器containers

序列式容器 Sequence containers

vector

迭代器

数据结构

内存管理 constructor , push_back

元素操作

list

迭代器

数据结构

内存管理

元素操作

deque

deque 和 vector 差异

中控器

空间成长性

map

迭代器

数据结构

内存管理

元素操作

stack

queue

heap(implicit representation)

存储结构

分类

heap 算法

push_heap 插入元素

pop_heap

sort_heap

make_heap

priority_queue

slist

关联容器 Associative containers

内部存储结构为RB-tree 的容器

树

一些术语

二叉树

二叉搜索树

平衡二叉搜索树

AVL tree

RB-tree 红黑树

RB-tree 迭代器

红黑树空间操作

基础操作

set

特性

迭代器

各种操作

map

特性

迭代器

各种操作

multiset

multimap

内部存储结构为hash-table的容器

hash table

哈希冲突解决

线性探测

二次探测

开链法（拉链法）

SGI STL hash table

迭代器

底层空间

表格重建

元素型别

hash_set

hash_map

hash_multiset 与 hash_multimap

相关文章