STL 重点知识详解笔记

STL版本情况

stl是一个框架,将数据结构和算法进一步抽象

容器、迭代器、算法

STL历史

  • 1979年创造C++年代却不支持泛型,第一个支持泛型的是Ada,但Ada在美国国防工业以外未被广泛接受

  • 1987年Alexander开发出Ada Library,接下来看到C++如此火热于是试验了多种架构和算法公式,先以C完成,后再以C++完成

  • 1992年Meng Lee加入了Alex的项目成为早期STL另一位主要贡献者
  • 1993年贝尔实验室的Andrew Koenig在1993年知道这个研究计划后邀请Alex ander于11月ANSI/ISO c++标准委员会议上展示观念
  • 1994年1月25日Alexander完成了提案报告提交到委员会,3月份在圣地亚哥会议,STL活得很好回响,投票结果压倒性给予提案机会
  • 1998年STL正式成为9月C++标准规格,原本stream,string以template重写

STL六大组件

  • 容器(containers):各种数据结构(vector,list,deque,set,map)

    用以存放数据

  • 算法(algorithms):常用算法如sort,search,copy,erase(抹去)…..

  • 迭代器(iterators):扮演容器和算法之间的胶合剂,所谓的泛型指针

  • 仿函数(functors):行为类似函数,可作为算法的某种策略

  • 配接器(adapter):一种修饰容器或仿函数或迭代器接口的东西

  • 配置器:负责空间配置与管理

GNU开放精神

1
2
3
4
全世界所有STL实现版本由Alexander,meng lee完成
这份原始代码由惠普公司拥有,每个头文件都有一份声明
允许任何人运用,拷贝,传播,修改,贩卖这些代码,无需付费
唯一的条件就是必须将该份声明置于使用者新开发的文件内。

这种开源精神就是open source

1
2
此开源精神来源于美国人理察.史托曼,他认为私藏源代码是一种违反人性的罪恶行为
开放分享源代码便可以让其他人从中学习,并回馈给原始作者

GNU 代表GNU is Not Unix,Unix是当时计算机界主流操作系统,由AT&T 贝尔实验室创造,原本只是学术型产品,AT&T将它分享给许多研究人员，但是所有研究使得这个产品越来越美好，于是AT&T开始考虑追加投资并要求不得公开或透露UNIX源代码,想从中获利,并赞助伯克利大学继续强化Unix,导致后来发展成BSD以及FreeBSD,OpenBSD,NetBSD

1
2
3
4
5
Unix类操作系统:FreeBSD、Solaris、MacOSX这都属于Unix类操作系统。
确切的说FreeBSD是BSD内核的操作系统
而MacOSX与Solaris都是基于FreeBSD演化而来的操作系统。
Linux操作系统:Linux本身来说不是一个操作系统,而是内核
所有基于linux内核的系统统称为linux

Stallman认为AT&T对大学的赞助只是微薄的施舍,于是进行反奴役计划称之为GNU

GNU早期计划是Gcc和EMacs,一个C/C++编译器,还有一个文本编辑器

GNU计划晚期著名的软件则由1991年芬兰人Linux Torvalds开发的Linux操作系统

GNU以GPL(广泛开放授权)来保护乘员:使用者可以阅读修改GPL软件的源代码,但是使用者要传播借助GPL软件而完成的软件必须遵守GPL规范,这类精神主要强迫人们分享并回馈他们对GPL软件的改善

后期衍生了不同的授权包括:Library GPL,Lesser GPL,Apache License,BSD License等,它们的共同原则就是“开放源代码”

空间配置器(Allocator)

隐藏在一切组件背后,默默工作付出

整个STL操作对象都存放容器,容器需要配置空间存放资源

迭代器(Iterator)

迭代器扮演重要角色,将数据容器和算法分开彼此独立设计,再以胶合剂撮合一起,class template和function templates可分别达成目标

容器(Container)

C++ STL 的实现：

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
1.vector      底层数据结构为数组 ，支持快速随机访问

2.list            底层数据结构为双向链表，支持快速增删

3.deque       底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问
deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1] --> [堆2] -->[堆3] --> ...
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

4.stack        底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5.queue     底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）

6.priority_queue     的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

7.set                   底层数据结构为红黑树，有序，不重复

8.multiset         底层数据结构为红黑树，有序，可重复 

9.map                底层数据结构为红黑树，有序，不重复

10.multimap    底层数据结构为红黑树，有序，可重复

11.hash_set     底层数据结构为hash表，无序，不重复

12.hash_multiset 底层数据结构为hash表，无序，可重复 

13.hash_map    底层数据结构为hash表，无序，不重复

14.hash_multimap 底层数据结构为hash表，无序，可重复

  • 序列式容器

    • array
    • vector
    • dequeue
    • list
    • forward_list

    这类都通过数组或者指针链表

  • 关联类容器

    • set
    • map
    • multiset(类似hashset)
    • multimap(类似hashmap,第三方库已经起好,为避免冲突不起此类名字)

    关联式都是通过二叉树方式实现,set和map默认都是红黑树

  • 无序容器

    • unordered_map
    • unordered_set
    • unordered_multimap
    • unordered_multiset

    无序容器都是通过hash_table,哈希表

其他重要数据结构:stack,queue,priority_queue

字符串string,也是一个container

如果存入是否布尔值可用位集合:bitset

1
2
3
regex rand

thread async future time
  • 1:容器可以复制(copy)或者搬移(move)(隐含的条件是在拷贝和搬移的过程中没有副作用)

基本数据类型:bool char int double pointer reference function

  • 2:元素可被赋值操作来复制和搬移

  • 3:元素是可销毁的,析构不能使private,而且析构函数不允许抛出异常

    对于序列式容器,元素必须有默认的构造函数

    对于某些操作,元素需要定义== std::find

    对于关联式容器,排序准则默认是<, > std::less

    无顺序容器,必须要提供一个hash函数 也需要==符号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
> stl容器里面存的是元素的值而不是引用?

bool char int double 基本存的是元素的值


> 那自己定义的类也是存值而不是引用?

class Player自定义的类,也要定义==符号,拷贝

player的大小也大,而且有些信息是独有的

所以存指针也是ok的,也可以用智能指针存入容器



> stl对于错误怎么处理?

stl的设计原则是效率优先,安全为次

异常?stl自己却不怎么采用

类似vector在移动元素,可能会引发元素的异常,所以具体的异常考虑STL没法考虑全

还是得靠开发自己以当时处境去处理各自的异常

总结

  • 向量(vector)连续存储的元素

  • 列表(list) 由节点组成的双向链表，每个结点包含着一个元素

  • 双队列(deque) 连续存储的指向不同元素的指针所组成的数组

  • 集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序

  • 多重集合(multiset) 允许存在两个次序相等的元素的集合

  • 栈(stack) 后进先出的值的排列

  • 队列(queue) 先进先出的执的排列

  • 优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列

  • 映射(map) 由{** const 键，值}**对组成的集合，以某种作用于键对上的谓词排列

  • 多重映射(multimap) 允许键对有相等的次序的映射

容器通用接口

类接口编程通过模板或者类派生

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
tempalte <typename T>
void containerAllInterface(T &a, T&b){
    T c;
    T d(a); //容器值的构造拷贝,值拷贝过去
    T e = a; //等号值拷贝
    T f(std::move(a)); //右值引用 a不存在什么全部迁移到f 不是拷贝
    b.begin(); //返回迭代器的头
    b.end(); // 返回迭代器的尾
    T g(b.begin(), b.end());  //g可以通过迭代器的模式值拷贝出来 

    b.size();// 表示当前container的元素数量
    //###############    只有一个forward_list不提供此功能
    
    b.empty();//也不考虑forward_list,等价于return b.size() != 0
    b.max_size(); //最大存储值
    if (b == c){
        //先比较数量,再通过begin迭代器判断值是否一样
    }
    if (b != c){
        //当然如上比较是否不一样等价于 !(b == c)
    }
    if(b < c){
        //###############    unordered_set unordered_map无顺序无法进行此类操作
    }
    
    e.swap(g); //还提供e和g元素互换 
    // std::array对于swap的算法时间复杂度是线性的
    //对于其他container都是O(1)非常高效
    
    swap(e, g);//全局函数 对于其他也是O(1),但是std::array还是线性的
    
    e.cbegin();// 相对于等于 const_iterator(); 等于const引用
	e.begin(); //如果e是const引用那也是const引用的begin，否则就是通常的引用
    
    e.cend();//如上
    
    e.clear();//清空所有元素,调用元素的析构函数
    //###############    std:array也不存在clear
}

array

array 是固定大小的顺序容器，它们保存了一个以严格的线性顺序排列的特定数量的元素。

方法 含义
begin 返回指向数组容器中第一个元素的迭代器
end 返回指向数组容器中最后一个元素之后的理论元素的迭代器
rbegin 返回指向数组容器中最后一个元素的反向迭代器
rend 返回一个反向迭代器，指向数组中第一个元素之前的理论元素
cbegin 返回指向数组容器中第一个元素的常量迭代器（const_iterator）
cend 返回指向数组容器中最后一个元素之后的理论元素的常量迭代器（const_iterator）
crbegin 返回指向数组容器中最后一个元素的常量反向迭代器（const_reverse_iterator）
crend 返回指向数组中第一个元素之前的理论元素的常量反向迭代器（const_reverse_iterator）
size 返回数组容器中元素的数量
max_size 返回数组容器可容纳的最大元素数
empty 返回一个布尔值，指示数组容器是否为空
operator[] 返回容器中第 n（参数）个位置的元素的引用
at 返回容器中第 n（参数）个位置的元素的引用
front 返回对容器中第一个元素的引用
back 返回对容器中最后一个元素的引用
data 返回指向容器中第一个元素的指针
fill 用 val（参数）填充数组所有元素
swap 通过 x（参数）的内容交换数组的内容
get（array） 形如 std::get<0>(myarray)；传入一个数组容器，返回指定位置元素的引用
relational operators (array) 形如 arrayA > arrayB；依此比较数组每个元素的大小关系 
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

void arrayPart(){
    //array实际上是对C/C++语言中原生数组进行封装
    //namespace std{
    // template<typename T, size_t N>
    // class array;
	//}
    //特点,内存分配在栈上(stack)它利用了C/C++数组, 绝对不会重新分配扩大减少容量,随机访问元素
    std::array<int, 100> a;
    std::array<int, 100> b = {};
    
    int abc[100]; //存放的内容没有初始化
    std::array<int, 100> a; //这里也没有初始化
    std::array<int, 100> b = {};//这里初始化100个0
    std::cout << a.size() << "\n" << b.size() << std::endl;

    std::array<int, 5> obj = {1, 2, 3, 4, 5};
    std::array<int, 2> obj2 = {1, 3};

    std::cout << "empty:" << a.empty() << std::endl;
    std::cout << "size:" << a.size() << std::endl;
    std::cout << "max_size " << a.max_size() << std::endl;

	auto data = obj;
    data.swap(obj);

    

}

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
data.begin();
data.end();
data.cbegin(); //const 迭代器头
data.cend(); //const 迭代器尾

data.rbegin();
data.rend();
//begin end 从头到尾, r就从end到begin

for (auto iterator = data.cbegin(); iterator != data.cend(); iterator ++) {
	std::cout << *(iterator) << std::endl;
}

元素访问

1
2
3
4
5
6
7
//直接拿某个元素, array直接取下标
std::array<char, 100> carr;
strcpy(&carr[0], "helloWorld\n");
printf("%s", &carr[0]);

std::cout << "front: " << obj.front() << std::endl;
std::cout << "back: " << data.back() << std::endl;

array是固定大小,无法进行插入元素操作

vector

vector 是表示可以改变大小的数组的序列容器。

方法 含义
vector 构造函数
~vector 析构函数，销毁容器对象
operator= 将新内容分配给容器，替换其当前内容，并相应地修改其大小
begin 返回指向容器中第一个元素的迭代器
end 返回指向容器中最后一个元素之后的理论元素的迭代器
rbegin 返回指向容器中最后一个元素的反向迭代器
rend 返回一个反向迭代器，指向中第一个元素之前的理论元素
cbegin 返回指向容器中第一个元素的常量迭代器（const_iterator）
cend 返回指向容器中最后一个元素之后的理论元素的常量迭代器（const_iterator）
crbegin 返回指向容器中最后一个元素的常量反向迭代器（const_reverse_iterator）
crend 返回指向容器中第一个元素之前的理论元素的常量反向迭代器（const_reverse_iterator）
size 返回容器中元素的数量
max_size 返回容器可容纳的最大元素数
resize 调整容器的大小，使其包含 n（参数）个元素
capacity 返回当前为 vector 分配的存储空间（容量）的大小
empty 返回 vector 是否为空
reserve 请求 vector 容量至少足以包含 n（参数）个元素
shrink_to_fit 要求容器减小其 capacity（容量）以适应其 size（元素数量）
operator[] 返回容器中第 n（参数）个位置的元素的引用
at 返回容器中第 n（参数）个位置的元素的引用
front 返回对容器中第一个元素的引用
back 返回对容器中最后一个元素的引用
data 返回指向容器中第一个元素的指针
assign 将新内容分配给 vector，替换其当前内容，并相应地修改其 size
push_back 在容器的最后一个元素之后添加一个新元素
pop_back 删除容器中的最后一个元素，有效地将容器 size 减少一个
insert 通过在指定位置的元素之前插入新元素来扩展该容器，通过插入元素的数量有效地增加容器大小
erase 从 vector 中删除单个元素（position）或一系列元素（[first，last)），这有效地减少了被去除的元素的数量，从而破坏了容器的大小
swap 通过 x（参数）的内容交换容器的内容，x 是另一个类型相同、size 可能不同的 vector 对象
clear 从 vector 中删除所有的元素（被销毁），留下 size 为 0 的容器
emplace 通过在 position（参数）位置处插入新元素 args（参数）来扩展容器
emplace_back 在 vector 的末尾插入一个新的元素，紧跟在当前的最后一个元素之后
get_allocator 返回与vector关联的构造器对象的副本
swap(vector) 容器 x（参数）的内容与容器 y（参数）的内容交换。两个容器对象都必须是相同的类型（相同的模板参数），尽管大小可能不同
relational operators (vector) 形如 vectorA > vectorB；依此比较每个元素的大小关系

vector是c++98中引入的动态数组

特点随机访问元素,末端添加删除元素效率非常高

但是前端和中间效率低下,当超过容器容量会重新分配

初始化

1
2
3
4
5
6
7
8
9
10
using Group = std::vector<float>;

Group a;
Group b = a;
Group c(a);
Group d(10); // 10个float
Group e(10, 1.0f); //10个float,每个值是1.0f
Group f(e.begin(), e.end());//传入迭代器
Group g({1.0f, 2.0f, 3.0f});//c++11初始化的值直接赋值, initialize list
Group h = {1.0f, 2.0f ,3.0f ,4.0f};//c++11初始化的值直接赋值, initialize list

通用接口

1
2
3
4
5
6
d.empty();
d.size();//当前的vector中含有元素数量值
d.max_size();//返回容器可容纳的最大元素数
d.capacity();//保证不重分配的情况下最多能装入多少元素
d.reserve(100);//请求 vector 容量至少足以包含 n（参数）个元素
d.shrink_to_fit();//要求容器减小其 capacity（容量）以适应其 size（元素数量）

赋值

1
2
b = g;
b.assign(3, 1.0f);// {1.0f, 1.0f, 1.0f};

交换

1
2
3
4
5
6
7
8
9
10
b.swap(a); //vector 高效且不抛出异常,对于container除了array,其他的交换全都是交换指针,把内容全部交换过来
// 类似如下
struct A{
    int * data;
    void swap(A& rhs){
    int* temp = rhs.data;
    rhs.data = data;
    data = temp;
    }
};

元素访问

1
2
3
4
5
6
b[0];
b.at(0); //[]不去检查越界,at会检测是否越界并且抛出out_of_range
b.front();//如果vector是空的情况下,会直接dumped
//array的话会预先分配,所以不会出现这个问题
b.back();
b.pop_back();//移除元素,也要判定是否不为空

移除新增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//移除
b.pop_back();//移除元素,也要判定是否不为空
b.erase(b.begin());//只移除头部,然后返回下一个位置的元素
b.erase(b.begin(), b.end()); //位置区间移除,返回下一个位置的元素
b.push_back(1.0f); //尾部增加

b.insert(b.end(), 100.0f);//在某个位置插入1000.f
b.insert(b.end(), 10, 100.0f);//在某个位置插入10个1000.f
b.insert(b.end(), b.begin(), b.end());//在某个位置插入一个区间,用拷贝方式复制过来

b.emplace(b.end(), 10.f);//和insert在基本类型上是一样的
b.emplace_back(10.0f);//和push_back在基本类型上是一样

b.resize(10);// 强行调整大小,如果调小直接干掉数据
b.resize(100, 1.0f);//调整vector的大小,默认以1.0f填充

b.clear();//清空所有元素,并调用元素的析构函数,但是capacity不会变
b.shink_to_fit();//清空元素之后,vector容量也降下来

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
data.begin();
data.end();
data.cbegin(); //const 迭代器头
data.cend(); //const 迭代器尾

data.rbegin();
data.rend();
//begin end 从头到尾, r就从end到begin

for (auto iterator = data.cbegin(); iterator != data.cend(); iterator ++) {
	std::cout << *(iterator) << std::endl;
}

vector异常

  • push_back发生异常对vector不会变化
  • pop_back绝对不会出现异常
  • 元素move/copy没有异常的话, erase insert emplace emplace_back push_back不会有异常
  • swap clear 不会有异常

vector不要用bool

deque

deque（[‘dek]）（双端队列）是double-ended queue 的一个不规则缩写。deque是具有动态大小的序列容器，可以在两端（前端或后端）扩展或收缩。

1
2
3
4
5
6
7
deque和vector一样,采用线性表，与vector唯一不同的是，deque采用的分块的线性存储结构
每块大小一般为512字节，称为一个deque块，所有的deque块使用一个Map块进行管理
每个map数据项记录各个deque块的首地址
这样以来，deque块在头部和尾部都可已插入和删除元素，而不需要移动其它元素。

使用push_back()方法在尾部插入元素，使用push_front()方法在首部插入元素，使用insert()方法在中间插入元素。
一般来说，当考虑容器元素的内存分配策略和操作的性能时，deque相对vectore更有优势。
方法 含义
deque 构造函数
push_back 在当前的最后一个元素之后 ，在 deque 容器的末尾添加一个新元素
push_front 在 deque 容器的开始位置插入一个新的元素，位于当前的第一个元素之前
pop_back 删除 deque 容器中的最后一个元素，有效地将容器大小减少一个
pop_front 删除 deque 容器中的第一个元素，有效地减小其大小
emplace_front 在 deque 的开头插入一个新的元素，就在其当前的第一个元素之前
emplace_back 在 deque 的末尾插入一个新的元素，紧跟在当前的最后一个元素之后

deque是c++98引入的动态数组(dynamic array)

1
2
3
4
namespaces std{
    template<typename T, typename Allocator = allocator<T>>
    class deque;
}

特点随机访问元素

末端和头部添加删除元素效率高,中间删除和添加元素效率低

元素的访问和迭代比vector要慢,迭代器不能使普通的指针

通用接口

1
2
3
4
5
6
7
8
d.empty();
d.size();//当前的vector中含有元素数量值
d.max_size();//返回容器可容纳的最大元素数

//不提供以下方法
//d.capacity();
//d.reserve(100);
d.shrink_to_fit();//要求容器减小其 capacity（容量）以适应其 size（元素数量）

赋值

1
2
b = g;
b.assign(3, 1.0f);// {1.0f, 1.0f, 1.0f};

交换

1
2
3
4
5
6
7
8
9
10
b.swap(a); //类似vector
// 类似如下
struct A{
    int * data;
    void swap(A& rhs){
    int* temp = rhs.data;
    rhs.data = data;
    data = temp;
    }
};

元素访问

1
2
3
4
5
b[0];
b.at(0); //[]不去检查越界,at会检测是否越界并且抛出out_of_range
b.front();//如果vector是空的情况下,会直接dumped
//array的话会预先分配,所以不会出现这个问题
b.back();

大多数功能和vector类似

deque的clear是释放空间的

移除新增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//移除
b.pop_back();//移除元素,也要判定是否不为空
b.erase(b.begin());//只移除头部,然后返回下一个位置的元素
b.erase(b.begin(), b.end()); //位置区间移除,返回下一个位置的元素
b.push_back(1.0f); //尾部增加

b.insert(b.end(), 100.0f);//在某个位置插入1000.f
b.insert(b.end(), 10, 100.0f);//在某个位置插入10个1000.f
b.insert(b.end(), b.begin(), b.end());//在某个位置插入一个区间,用拷贝方式复制过来

b.emplace(b.end(), 10.f);//和insert在基本类型上是一样的
b.emplace_back(10.0f);//和push_back在基本类型上是一样

b.resize(10);// 强行调整大小,如果调小直接干掉数据
b.resize(100, 1.0f);//调整vector的大小,默认以1.0f填充

b.clear();//清空所有元素,并调用元素的析构函数,但是capacity不会变
b.shink_to_fit();//清空元素之后,vector容量也降下来

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
data.begin();
data.end();
data.cbegin(); //const 迭代器头
data.cend(); //const 迭代器尾

data.rbegin();
data.rend();
//begin end 从头到尾, r就从end到begin

for (auto iterator = data.cbegin(); iterator != data.cend(); iterator ++) {
	std::cout << *(iterator) << std::endl;
}

forward_list

forward_list（单向链表）是序列容器，允许在序列中的任何地方进行恒定的时间插入和擦除操作。

方法 含义
forward_list 返回指向容器中第一个元素之前的位置的迭代器
cbefore_begin 返回指向容器中第一个元素之前的位置的 const_iterator

特点几乎跟list一致,不支持随机访问函数,访问头部速度快

特点不支持随机访问元素,访问头部元素速度快

forward_list和自己手写的C-style singly linked list相比

没有任何时间和空间上的额外开销,任何性质如果和这个目标抵触,我们放弃该特征

任何位置插入删除元素都很快,常量时间完成

插入和删除不会造成迭代器失效

对于异常支持的好,出现异常对于forward_list而言,要不成功,要不什么影响没有

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using Group = std::forward_list<float>;
Group a;
Group b = a;
Group c(a);
Group d(10); // 10个float
Group e(10, 1.0f); //10个float,每个值是1.0f
Group f(e.begin(), e.end());//传入迭代器
Group g({1.0f, 2.0f, 3.0f});//c++11初始化的值直接赋值, initialize list
Group h = {1.0f, 2.0f ,3.0f ,4.0f};//c++11初始化的值直接赋值, initialize list

d.empty();
//d.size();不支持,如果维护一个计数,导致空间或时间上的额外开销,与目标抵触,所以放弃此特征
d.max_size();

b = g;
b.assign(3, 1.0f);// {1.0f, 1.0f, 1.0f};
b.assign(g.begin(), g.end());
b.assign({1.0f, 2.0f ,3.0f});

//b[0]; b.at(0);不支持
b.front();
//b.back();不支持

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
data.begin();
data.end();
data.cbegin(); //const 迭代器头
data.cend(); //const 迭代器尾

data.before_begin();//返回指向第一个元素的前面位置 不是合法位置
data.cbefore_begin();//返回const第一个元素有效的前面位置 不是合法位置
//这些只为了自身的算法
//auto iter = a.before_begin();
// *iter //undenfined


//data.rbegin();不支持不提供
//data.rend();不支持不提供
//begin end 从头到尾, r就从end到begin

for (auto iterator = data.cbegin(); iterator != data.cend(); iterator ++) {
	std::cout << *(iterator) << std::endl;
}

新增移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//移除
b.pop_back();//移除元素,也要判定是否不为空

b.erase_after(b.before_begin());//只移除头部,然后返回下一个位置的元素
b.erase_after(b.before_begin(), b.end());//位置区间移除,返回下一个位置的元素

b.push_back(1.0f); //尾部增加

b.insert_after(b.before_begin(), 100.0f);//在某个位置插入1000.f
b.insert_after(b.before_begin(), 10, 100.0f);//在某个位置插入10个1000.f


b.emplace(b.end(), 10.f);//和insert在基本类型上是一样的
b.emplace_back(10.0f);//和push_back在基本类型上是一样

b.resize(10);// 强行调整大小,如果调小直接干掉数据
b.resize(100, 1.0f);//调整vector的大小,默认以1.0f填充

b.clear();//清空所有元素,并调用元素的析构函数,但是capacity不会变
b.shink_to_fit();//清空元素之后,vector容量也降下来

其他函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto iterBegin = a.begin();
std::advance(iterBegin, 4);//iterBegin移动4步

a.pop_back();
if(!a.empty())a.pop_back();

b.push_back(10.0f);
b.pop_back();
b.push_front(1.2f);
b.emplace_front(1.3f);

auto iter = b.insert(b.end(), 100.0f);
iter = b.insert(b.end(), 10, -10.0f);
b.insert(b.end(), h.begin(), h.end());
b.emplace(b.end(), 10.0f);
b.emplace_back(10.0f);
b.resize(10);
b.resize(100, 1.0f);

算法

1
2
3
4
5
6
7
8
9
10
11
12
b.remove(1.0f);
b.remove_if([](auto v(return v > 100.0f;)));

//b.reverse(); 不支持逆转 1 2 3 4 -> 4 3 2 1
b.sort();// 不支持< 排序
b.merge(g); //合并

b.unique();//需要排好序的 去重 附近重复的去掉
// 1 1 2 3 3 4 -> 1 2 3 4
// 1 1 2 2 1 1  3 4 -> 1 2 1 3 4

b.splice(c.begin(), b);//把b的一块插入到c的某个位置上

list

list，双向链表，是序列容器，允许在序列中的任何地方进行常数时间插入和擦除操作，并在两个方向上进行迭代。

c++98引入,双向串联

不支持随机访问函数,访问头部和尾部速度快

在任何位置插入删除元素都很快,常量时间完成

插入和删除不会造成迭代器失效

对于异常支持的好,出现异常对于list而言,要不成功,要不什么影响没有

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using Group = std::list<float>;
Group a;
Group b = a;
Group c(a);
Group d(10); // 10个float
Group e(10, 1.0f); //10个float,每个值是1.0f
Group f(e.begin(), e.end());//传入迭代器
Group g({1.0f, 2.0f, 3.0f});//c++11初始化的值直接赋值, initialize list
Group h = {1.0f, 2.0f ,3.0f ,4.0f};//c++11初始化的值直接赋值, initialize list

d.empty();
d.size();
d.max_size();

b = g;
b.assign(3, 1.0f);// {1.0f, 1.0f, 1.0f};
b.assign(g.begin(), g.end());
b.assign({1.0f, 2.0f ,3.0f});

//b[0]; b.at(0);不支持
b.front();
b.back();

迭代器

1
2
3
4
5
6
7
8
9
10
11
12
data.begin();
data.end();
data.cbegin(); //const 迭代器头
data.cend(); //const 迭代器尾

data.rbegin();
data.rend();
//begin end 从头到尾, r就从end到begin

for (auto iterator = data.cbegin(); iterator != data.cend(); iterator ++) {
	std::cout << *(iterator) << std::endl;
}

新增移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//移除
b.pop_back();//移除元素,也要判定是否不为空
b.erase(b.begin());//只移除头部,然后返回下一个位置的元素
b.erase(b.begin(), b.end()); //位置区间移除,返回下一个位置的元素
b.push_back(1.0f); //尾部增加

b.insert(b.end(), 100.0f);//在某个位置插入1000.f
b.insert(b.end(), 10, 100.0f);//在某个位置插入10个1000.f
b.insert(b.end(), b.begin(), b.end());//在某个位置插入一个区间,用拷贝方式复制过来

b.emplace(b.end(), 10.f);//和insert在基本类型上是一样的
b.emplace_back(10.0f);//和push_back在基本类型上是一样

b.resize(10);// 强行调整大小,如果调小直接干掉数据
b.resize(100, 1.0f);//调整vector的大小,默认以1.0f填充

b.clear();//清空所有元素,并调用元素的析构函数,但是capacity不会变
b.shink_to_fit();//清空元素之后,vector容量也降下来

其他函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
auto iterBegin = a.begin();
std::advance(iterBegin, 4);//iterBegin移动4步

a.pop_back();
if(!a.empty())a.pop_back();

b.push_back(10.0f);
b.pop_back();
b.push_front(1.2f);
b.emplace_front(1.3f);

auto iter = b.insert(b.end(), 100.0f);
iter = b.insert(b.end(), 10, -10.0f);
b.insert(b.end(), h.begin(), h.end());
b.emplace(b.end(), 10.0f);
b.emplace_back(10.0f);
b.resize(10);
b.resize(100, 1.0f);

算法

1
2
3
4
5
6
7
8
9
10
11
12
b.remove(1.0f);
b.remove_if([](auto v(return v > 100.0f;)));

b.reverse();//逆转 1 2 3 4 -> 4 3 2 1
b.sort();// < 排序
b.merge(g); //合并

b.unique();//需要排好序的 去重 附近重复的去掉
// 1 1 2 3 3 4 -> 1 2 3 4
// 1 1 2 2 1 1  3 4 -> 1 2 1 3 4

b.splice(c.begin(), b);//把b的一块插入到c的某个位置上

stack

stack 是一种容器适配器，用于在LIFO（后进先出）的操作，其中元素仅从容器的一端插入和提取。

结构

queue

queue 是一种容器适配器，用于在FIFO（先入先出）的操作，其中元素插入到容器的一端并从另一端提取。

结构

queue有入队push（插入）、出队pop（删除）、读取队首元素front、读取队尾元素back、empty，size这几种方法

priority_queue

示例

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
#include <iostream>
#include <queue>
using namespace std;

int main()
{

    priority_queue<int> pq;

    pq.push(1);
    pq.push(3);
    pq.push(2);
    pq.push(8);
    pq.push(9);
    pq.push(0);

    cout << "size: " << pq.size() << endl;

    while(pq.empty() != true)
    {
        cout << pq.top() << endl;
        pq.pop();
    }
    return 0;
}

set

set 是按照特定顺序存储唯一元素的容器。

是c++98的二叉树数据结构,红黑树结构

特点

  • 元素自动排序

  • 插入和删除查找,O(logN) 1000次查找只需要20

  • 元素必须支持严格的弱顺序

    1
    2
    3
    4
    5
    //1: x < y == true, y < x == false
    //2: X < Y == true, y < z ==true, x < z == true
    //3: x < x == false
    //4: a == b, b == c, c == a
    //不能改变元素的值

辅助类

1
2
3
4
5
6
7
namespace std{
    template<typename T1, typename T2>
    struct pair{
        T1 first,
        T2 second,
    };
}

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using Group = std::set<float>;
Group a;
Group b = a;
Group c(a);
Group d(c.begin(), c.end());
Group g({1.0f, 4.0f, 3.0f});
// 1.0f 3.0f 4.0f
Group h = {1.0f, 2.0f, 3.0f};

d.empty();
d.size();
d.max_size();


auto keycomp = c.key_comp();
auto valuecomp = c.value_comp();

//赋值
b = g;


//交换
b.swap(a);
std::swap(a, b);

迭代器

1
2
3
4
5
6
7
8
9
// 迭代器
a.begin();
a.end();
a.cbegin();
a.cend();
a.rbegin();
a.rend();
a.crbegin();
a.crend();

算法

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
//算法
//数量查找
// set count 0 不存在, 1 存在这样的值 ,同样类型的值只保留一个
// multiset count >= 0 , 会找多个与set不同
auto num = a.count(1.0f);

//find 寻找  迭代器返回
auto findIter = a.find(1.0f);
if (findIter == a.end()){
//not find
} else {
//find
std::cout << *findIter << std::endl;
}

auto lower = a.lower_bound(1.0f); //返回低端部分,比如插入1.0f,lower_bound的位置,能不能插入成功不一定
if(lower != a.end()){
    if(*lower == 1.0f){
	    // has 1.0f
    }
}
//说白了就是 >= 的值

auto high = a.upper_bound(1.0f); //返回高端部分,最后一个可插入点
//而upper_bound就是 > 的值

auto range = a.equal_range(1.0f); 
//而equal_range返回的是pair,一个是lower,一个是upper

auto eraseIter = b.erase(b.begin());
eraseIter = b.erase(b.begin(), b.end());

auto state = b.insert(100.0f); //返回一个pari,<Iterator,bool>
//第一个迭代器,第二个布尔值
auto insertIter = b.insert(c.begin(), c.end());
b.emplace(10.0f);
b.emplace_hint(b.end(), 100.0f);

示例

multiset

是c++98的二叉树数据结构

结构

map

map 是关联容器，按照特定顺序存储由 key value (键值) 和 mapped value (映射值) 组合形成的元素。红黑树结构

set，multisets，map，multimap使用相同的内部结构，因此可以将set和multiset当成特殊的map和multimap，只不过set的value和key指向的是同一元素

方法 含义
map 构造函数
begin 返回引用容器中第一个元素的迭代器
key_comp 返回容器用于比较键的比较对象的副本
value_comp 返回可用于比较两个元素的比较对象，以获取第一个元素的键是否在第二个元素之前
find 在容器中搜索具有等于 k（参数）的键的元素，如果找到则返回一个迭代器，否则返回 map::end 的迭代器
count 在容器中搜索具有等于 k（参数）的键的元素，并返回匹配的数量
lower_bound 返回一个非递减序列 [first, last)（参数）中的第一个大于等于值 val（参数）的位置的迭代器
upper_bound 返回一个非递减序列 [first, last)（参数）中第一个大于 val（参数）的位置的迭代器
equal_range 获取相同元素的范围，返回包含容器中所有具有与 k（参数）等价的键的元素的范围边界（pair< map<char,int>::iterator, map<char,int>::iterator >）

特点

key是const的key

构造

迭代器

算法

示例

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
// cont/mapl.cpp

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main()
{
   /*create map/associative array
    *-keys are strings
    *-values are floats
    */
   typedef map<string,float> StringFloatMap;

   StringFloatMap stocks;      // create empty container

   //insert some elements
   stocks["BASF"] = 369.50;
   stocks["VW"] = 413.50;
   stocks["Daimler"] = 819.00;
   stocks["BMW"] = 834.00;
   stocks["Siemens"] = 842.20;

   //print all elements
   StringFloatMap::iterator pos;
   for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
       cout << "stock: " << pos->first << "\t"
            << "price: " << pos->second << endl;
   }
   cout << endl;

   //boom (all prices doubled)
   for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
       pos->second *= 2;
   }

   //print all elements
   for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
       cout << "stock: " << pos->first << "\t"
            << "price: " << pos->second << endl;
   }
   cout << endl;

   /*rename key from "VW" to "Volkswagen"
    *-only provided by exchanging element
    */
   stocks["Volkswagen"] = stocks["VW"];
   stocks.erase("VW");

   //print all elements
   for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
       cout << "stock: " << pos->first << "\t"
            << "price: " << pos->second << endl;
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
stock: BASF price: 369.5
stock: BMW price: 834
stock: Daimler price: 819
stock: Siemens price: 842.2
stock: VW price: 413.5

stock: BASF price: 739
stock: BMW price: 1668
stock: Daimler price: 1638
stock: Siemens price: 1684.4
stock: VW price: 827

stock: BASF price: 739
stock: BMW price: 1668
stock: Daimler price: 1638
stock: Siemens price: 1684.4
stock: Volkswagen price: 827

multimap

简介

C++ stl Multimap 和C++ stl map 很相似，但是MultiMap允许重复的元素。

　map和multimap会根据key对元素进行自动排序，所以根据key值搜寻某个元素具有良好的性能，但是如果根据value来搜寻效率就很低了。

同样，自动排序使得你不能直接改变元素的key，因为这样会破坏正确次序，要修改元素的key，必须先移除拥有key的元素，然后插入拥有新的key/value的元素，从迭代器的观点来看，元素的key是常数，元素的value是可以直接修改的。

C++ stl Multimap的基本操作类成员函数列表介绍如下:

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
begin()返回指向第一个元素的迭代器
clear()删除所有元素

count()返回一个元素出现的次数

empty()如果multimap为空则返回真

end()返回一个指向multimap末尾的迭代器

equal_range()返回指向元素的key为指定值的迭代器对

erase()删除元素

find()查找元素

get_allocator()返回multimap的配置器

insert()插入元素

key_comp()返回比较key的函数

lower_bound()返回键值>=给定元素的第一个位置

max_size()返回可以容纳的最大元素个数

rbegin()返回一个指向mulitmap尾部的逆向迭代器

rend()返回一个指向multimap头部的逆向迭代器

size()返回multimap中元素的个数

swap()交换两个multimaps

upper_bound()返回键值>给定元素的第一个位置

value_comp()返回比较元素value的函数

示例

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
// cont/mmap1.cpp

 #include <iostream>
 #include <map>
 #include <string>
 #include <iomanip>
 using namespace std;

 int main()
 {
     //define multimap type as string/string dictionary
     typedef multimap<string,string> StrStrMMap;

     //create empty dictionary
     StrStrMMap dict;

     //insert some elements in random order
     dict.insert(make_pair("day","Tag"));
     dict.insert(make_pair("strange","fremd"));
     dict.insert(make_pair("car","Auto"));
     dict.insert(make_pair("smart","elegant"));
     dict.insert(make_pair("trait","Merkmal"));
     dict.insert(make_pair("strange","seltsam"));
     dict.insert(make_pair("smart","raffiniert"));
     dict.insert(make_pair("smart","klug"));
     dict.insert(make_pair("clever","raffiniert"));

     //print all elements
     StrStrMMap::iterator pos;
     cout.setf (ios::left, ios::adjustfield);
     cout << ' ' << setw(10) << "english "
          << "german " << endl; 
     cout << setfil('-') << setw(20) << ""
          << setfil(' ') << endl;
     for (pos = dict.begin(); pos != dict.end(); ++pos) {
         cout << ' ' << setw(10) << pos>first.c_str()
              << pos->second << endl;
     }
     cout << endl;

     //print all values for key "smart"
     string word("smart");
     cout << word << ": " << endl;

     for (pos = dict.lower_bound(word);
          pos != dict.upper_bound(word); ++pos) {
             cout << " " << pos->second << endl;
     }

     //print all keys for value "raffiniert"
     word = ("raffiniert");
     cout << word << ": " << endl;
     for (pos = dict.begin(); pos != dict.end(); ++pos) {
         if (pos->second == word) {
             cout << " " << pos->first << endl;
         }
     }
 }

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
english   german
--------------------
car       Auto
clever    raffiniert
day       Tag
smart     elegant
smart     raffiniert
smart     klug
strange   fremd
strange   seltsam
trait     Merkmal

smart:
	elegant
raffiniert
	klug
raffiniert:
	clever
	smart

unordered_set

unordered_set与与unordered_map相似

unordered_set它的实现基于hashtable,它的结构图仍然可以用下图表示,这时的空白格不在是单个value,而是set中的key与value的数据包

有unordered_set就一定有unordered_multiset.跟set和multiset一样,一个key可以重复一个不可以

结构

unordered_set是一种无序集合,既然跟底层实现基于hashtable那么它一定拥有快速的查找和删除，添加的优点.基于hashtable当然就失去了基于rb_tree的自动排序功能

unordered_set无序,所以在迭代器的使用上,set的效率会高于unordered_set

基本操作

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//定义
unordered_set<int> c1;

//operator=
unordered_set<int> c2;
c2 = c1;



//判断是否为空
c1.empty();

//获取元素个数 size()
c1.size();

//获取最大存储量 max_size()
c1.max_size();



//返回头迭代器 begin()
unordered_set<int>::iterator ite_begin = c1.begin();

//返回尾迭代器 end()
unordered_set<int>::iterator ite_end = c1.end();

//返回const头迭代器 cbegin()
unordered_set<int>::const_iterator const_ite_begin = c1.cbegin();

//返回const尾迭代器 cend()
unordered_set<int>::const_iterator const_ite_end = c1.cend();

//槽迭代器
unordered_set<int>::local_iterator local_iter_begin = c1.begin(1);
unordered_set<int>::local_iterator local_iter_end = c1.end(1);




//查找函数 find() 通过给定主键查找元素
unordered_set<int>::iterator find_iter = c1.find(1);
    
    //value出现的次数 count() 返回匹配给定主键的元素的个数
    c1.count(1);

//返回元素在哪个区域equal_range() 返回值匹配给定搜索值的元素组成的范围
pair<unordered_set<int>::iterator, unordered_set<int>::iterator> pair_equal_range = c1.equal_range(1);

//插入函数 emplace()
c1.emplace(1);

//插入函数 emplace_hint() 使用迭代器
c1.emplace_hint(ite_begin, 1);

//插入函数 insert()
c1.insert(1);

//删除 erase()
c1.erase(1);//1.迭代器 value 区域

//清空 clear()
c1.clear();

//交换 swap()
c1.swap(c2);



//篮子操作 篮子个数 bucket_count() 返回槽（Bucket）数
c1.bucket_count();

//篮子最大数量 max_bucket_count() 返回最大槽数
c1.max_bucket_count();

//篮子个数 bucket_size() 返回槽大小
c1.bucket_size(3);

//返回篮子 bucket() 返回元素所在槽的序号
c1.bucket(1);

//    load_factor    返回载入因子，即一个元素槽（Bucket）的最大元素数
c1.load_factor();

//    max_load_factor    返回或设置最大载入因子
c1.max_load_factor();


//    rehash    设置槽数
c1.rehash(1);

//    reserve    请求改变容器容量
c1.reserve(1000);



//hash_function() 返回与hash_func相同功能的函数指针
auto hash_func_test = c1.hash_function();

//key_eq() 返回比较key值得函数指针
auto key_eq_test = c1.key_eq();

示例

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <iostream>
#include <unordered_set>
using namespace std;

namespace wzj001{
    void coutUnorderedSet(std::unordered_set<int>& m, string funcName) {
        std::unordered_set<int>::iterator it;
        std::cout << funcName << ": ";
        for ( it = m.begin(); it != m.end(); it++ )
            std::cout << *it << " ";
        std::cout << std::endl;
    }
    
    void initUnorderSet(unordered_set<int>& tmp)
    {
        for(int i = 0; i < 10; i++)
            tmp.insert(i);
    }
    
    string turnBoolToString(bool tmp)
    {
        return tmp ? "true" : "false";
    }
    
    void basicOperationUnorderedSet()
    {
        //定义
        std::unordered_set<int> c;
        // 普通插入,返回pair<迭代器,插入是否成功>
        pair<unordered_set<int>::iterator, bool> c_insert = c.insert(1);
        cout << "指向key的迭代器: " << *c_insert.first  << "   插入是否成功 "<< turnBoolToString(c_insert.second)<<endl;
        pair<unordered_set<int>::iterator, bool> c_insert2 = c.insert(2);
        cout << "指向key的迭代器: " << *c_insert2.first << "   插入是否成功 "<< turnBoolToString(c_insert2.second)<<endl;
        pair<unordered_set<int>::iterator, bool> c_insert3 = c.insert(1);
        cout << "指向key的迭代器: " << *c_insert3.first << "   插入是否成功 "<< turnBoolToString(c_insert3.second)<<endl;
        
        //按指定区域插入
        std::unordered_set<int> c_insert_region;
        c_insert_region.insert(c.begin(), c.end());
        coutUnorderedSet(c_insert_region, "按指定区域插入");
        
        //构造插入
        std::unordered_set<int> c_emplace;
        c_emplace.emplace(1);
        c_emplace.emplace(2);
        c_emplace.emplace(3);
        coutUnorderedSet(c_emplace, "构造插入");
        
        //迭代器插入
        std::unordered_set<int> c_emplace_hint;
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 1);
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 2);
        c_emplace_hint.emplace_hint(c_emplace_hint.begin(), 3);
        coutUnorderedSet(c_emplace_hint, "迭代器插入");
        
        //删除
        std::unordered_set<int> c_erase;
        initUnorderSet(c_erase);
        coutUnorderedSet(c_erase, "初始化c_erase");
        //指定位置删除
        c_erase.erase(c_erase.begin());
        coutUnorderedSet(c_erase, "指定位置删除");
        
        //指定key删除
        c_erase.erase(8);
        coutUnorderedSet(c_erase, "指定key删除");
        
        //指定区域删除
        c_erase.erase(c_erase.begin(), c_erase.end());
        coutUnorderedSet(c_erase, "指定区域删除");
        
        //交换
        c.swap(c_emplace);
        coutUnorderedSet(c, "交换");
        
    }
    
    void unorderSetElementLookup()
    {
        //查找
        std::unordered_set<int> c_find;
        initUnorderSet(c_find);
        std::unordered_set<int>::iterator find_iter = c_find.find(10);
        if(find_iter != c_find.end())
        {
            cout<< "找到元素 : "<< *find_iter << endl;
        }
        else
            cout<< "没找到 !"<< endl;
        
        cout << "value出现次数 :" <<c_find.count(1)<< endl; //set key不可重复
        
        pair<std::unordered_set<int>::iterator, std::unordered_set<int>::iterator> tmp = c_find.equal_range(5);
        
        if(tmp.first != c_find.end()&& tmp.second != c_find.end())
        {
            cout << "该值所在区间为[" << *tmp.first << "," << *tmp.second << "]" << endl;
        }
    }
    
    void unorderSetBuckets()
    {
        //篮子操作
        std::unordered_set<int> c_buckets;
        initUnorderSet(c_buckets);
        cout << "篮子个数: "    << c_buckets.bucket_count()<< endl;
        cout << "篮子大小: " << c_buckets.bucket_size(1) << endl;
        cout << "最大篮子个数: " << c_buckets.max_bucket_count() << endl;
        cout << "该值所在篮子序号: " << c_buckets.bucket(3) << endl;
    }
    
    void unorderSetHashPolicy()
    {
        std::unordered_set<int> c_;
        cout << "负载: "<< c_.load_factor()<< endl;
        initUnorderSet(c_);
        cout << "负载: "<< c_.load_factor()<< endl;//使用的篮子数/篮子总数  默认的篮子数为11
        cout << "最大负载: "<< c_.max_load_factor() << endl;
        c_.reserve(100);//预设篮子数 ,但是还没有设定
        c_.rehash(3);//设定篮子数
    }
    
    void unorderSetObservers()
    {
        std::unordered_set<int> c_;
        initUnorderSet(c_);
        std::unordered_set<int>::hasher xxx = c_.hash_function();
        std::unordered_set<int>::key_equal zzz = c_.key_eq();
        cout << "hash_func: " << xxx(11111) << endl;
        cout << "key_eq: " << turnBoolToString(zzz(11111,11111)) << endl;
    }
}

int main()
{
    wzj001::basicOperationUnorderedSet();
    wzj001::unorderSetElementLookup();
    wzj001::unorderSetBuckets();
    wzj001::unorderSetHashPolicy();
    wzj001::unorderSetObservers();
}

unordered_multiset

简介

不排序的关联容器类，key和value为相同值，key不需要唯一。支持forward迭代器。

unordered_map

简介

unordered_set、unodered_multiset、unordered_map、unodered_multimap都是无序容器，都是以哈希表实现的。

因为用了hashtable所以查找,插入,删除时间复杂为1

效率惊人

元素是无序的,如果是要按照一定顺序遍历则不能提供

可能空间使用上会比红黑树之前的map用的多一点

元素在一千万以下set的性能不能unordered_set,但是基于一千万以上
unordered_set性能却不如set,因为key会用重复,所以要调整

一般存玩家信息和玩家物品能达到百万级已经不得了,如果得顺序不需要建议还是用上unordered无序容器 

1
using Group = std::unordered_map<int std::string>;

带上hash算法

需要做个模板特化

要带上这个hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
namespace std{
    tempate<> struct hash<Position>{
        size_t operator()(const Position& p)const{
            //return p.x() + p.y();
            //(0, 4) (1, 3)
            //(2, 2),(3, 1)
            //return hash(p.x())^hash(p.y());
            //两个int做hash然后异或
            
            auto key = hash<int>(p.x());
            hash_combine(key, p.y());
            return key;
            //这样的hash冲突较小,boost库的实现
            //
        }
    }
}

unordered_multimap

简介

unordered_set、unodered_multiset、unordered_map、unodered_multimap都是无序容器，都是以哈希表实现的。

tuple

元组是一个能够容纳元素集合的对象。每个元素可以是不同的类型。

算法(Algorithms)

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// 简单查找算法，要求输入迭代器（input iterator）
find(beg, end, val); // 返回一个迭代器，指向输入序列中第一个等于 val 的元素，未找到返回 end
find_if(beg, end, unaryPred); // 返回一个迭代器，指向第一个满足 unaryPred 的元素，未找到返回 end
find_if_not(beg, end, unaryPred); // 返回一个迭代器，指向第一个令 unaryPred 为 false 的元素，未找到返回 end
count(beg, end, val); // 返回一个计数器，指出 val 出现了多少次
count_if(beg, end, unaryPred); // 统计有多少个元素满足 unaryPred
all_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都满足 unaryPred
any_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否任意（存在）一个元素满足 unaryPred
none_of(beg, end, unaryPred); // 返回一个 bool 值，判断是否所有元素都不满足 unaryPred

// 查找重复值的算法，传入向前迭代器（forward iterator）
adjacent_find(beg, end); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 end
adjacent_find(beg, end, binaryPred); // 返回指向第一对相邻重复元素的迭代器，无相邻元素则返回 end
search_n(beg, end, count, val); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 end
search_n(beg, end, count, val, binaryPred); // 返回一个迭代器，从此位置开始有 count 个相等元素，不存在则返回 end

// 查找子序列算法，除 find_first_of（前两个输入迭代器，后两个前向迭代器） 外，都要求两个前向迭代器
search(beg1, end1, beg2, end2); // 返回第二个输入范围（子序列）在爹一个输入范围中第一次出现的位置，未找到则返回 end1
search(beg1, end1, beg2, end2, binaryPred); // 返回第二个输入范围（子序列）在爹一个输入范围中第一次出现的位置，未找到则返回 end1
find_first_of(beg1, end1, beg2, end2); // 返回一个迭代器，指向第二个输入范围中任意元素在第一个范围中首次出现的位置，未找到则返回end1
find_first_of(beg1, end1, beg2, end2, binaryPred); // 返回一个迭代器，指向第二个输入范围中任意元素在第一个范围中首次出现的位置，未找到则返回end1
find_end(beg1, end1, beg2, end2); // 类似 search，但返回的最后一次出现的位置。如果第二个输入范围为空，或者在第一个输入范围为空，或者在第一个输入范围中未找到它，则返回 end1
find_end(beg1, end1, beg2, end2, binaryPred); // 类似 search，但返回的最后一次出现的位置。如果第二个输入范围为空，或者在第一个输入范围为空，或者在第一个输入范围中未找到它，则返回 end1

// 其他只读算法，传入输入迭代器
for_each(beg, end, unaryOp); // 对输入序列中的每个元素应用可调用对象 unaryOp，unaryOp 的返回值被忽略
mismatch(beg1, end1, beg2); // 比较两个序列中的元素。返回一个迭代器的 pair，表示两个序列中第一个不匹配的元素
mismatch(beg1, end1, beg2, binaryPred); // 比较两个序列中的元素。返回一个迭代器的 pair，表示两个序列中第一个不匹配的元素
equal(beg1, end1, beg2); // 比较每个元素，确定两个序列是否相等。
equal(beg1, end1, beg2, binaryPred); // 比较每个元素，确定两个序列是否相等。

// 二分搜索算法，传入前向迭代器或随机访问迭代器（random-access iterator），要求序列中的元素已经是有序的。通过小于运算符（<）或 comp 比较操作实现比较。
lower_bound(beg, end, val); // 返回一个非递减序列 [beg, end) 中的第一个大于等于值 val 的位置的迭代器，不存在则返回 end
lower_bound(beg, end, val, comp); // 返回一个非递减序列 [beg, end) 中的第一个大于等于值 val 的位置的迭代器，不存在则返回 end
upper_bound(beg, end, val); // 返回一个非递减序列 [beg, end) 中第一个大于 val 的位置的迭代器，不存在则返回 end
upper_bound(beg, end, val, comp); // 返回一个非递减序列 [beg, end) 中第一个大于 val 的位置的迭代器，不存在则返回 end
equal_range(beg, end, val); // 返回一个 pair，其 first 成员是 lower_bound 返回的迭代器，其 second 成员是 upper_bound 返回的迭代器
binary_search(beg, end, val); // 返回一个 bool 值，指出序列中是否包含等于 val 的元素。对于两个值 x 和 y，当 x 不小于 y 且 y 也不小于 x 时，认为它们相等。

// 只写不读算法，要求输出迭代器（output iterator）
fill(beg, end, val); // 将 val 赋予每个元素，返回 void
fill_n(beg, cnt, val); // 将 val 赋予 cnt 个元素，返回指向写入到输出序列最有一个元素之后位置的迭代器
genetate(beg, end, Gen); // 每次调用 Gen() 生成不同的值赋予每个序列，返回 void
genetate_n(beg, cnt, Gen); // 每次调用 Gen() 生成不同的值赋予 cnt 个序列，返回指向写入到输出序列最有一个元素之后位置的迭代器

// 使用输入迭代器的写算法，读取一个输入序列，将值写入到一个输出序列（dest）中
copy(beg, end, dest); // 从输入范围将元素拷贝所有元素到 dest 指定定的目的序列
copy_if(beg, end, dest, unaryPred); // 从输入范围将元素拷贝满足 unaryPred 的元素到 dest 指定定的目的序列
copy_n(beg, n, dest); // 从输入范围将元素拷贝前 n 个元素到 dest 指定定的目的序列
move(beg, end, dest); // 对输入序列中的每个元素调用 std::move，将其移动到迭代器 dest 开始始的序列中
transform(beg, end, dest, unaryOp); // 调用给定操作（一元操作），并将结果写到dest中
transform(beg, end, beg2, dest, binaryOp); // 调用给定操作（二元操作），并将结果写到dest中
replace_copy(beg, end, dest, old_val, new_val); // 将每个元素拷贝到 dest，将等于 old_val 的的元素替换为 new_val
replace_copy_if(beg, end, dest, unaryPred, new_val); // 将每个元素拷贝到 dest，将满足 unaryPred 的的元素替换为 new_val
merge(beg1, end1, beg2, end2, dest); // 两个输入序列必须都是有序的，用 < 运算符将合并后的序列写入到 dest 中
merge(beg1, end1, beg2, end2, dest, comp); // 两个输入序列必须都是有序的，使用给定的比较操作（comp）将合并后的序列写入到 dest 中

// 使用前向迭代器的写算法，要求前向迭代器
iter_swap(iter1, iter2); // 交换 iter1 和 iter2 所表示的元素，返回 void
swap_ranges(beg1, end1, beg2); // 将输入范围中所有元素与 beg2 开始的第二个序列中所有元素进行交换。返回递增后的的 beg2，指向最后一个交换元素之后的位置。
replace(beg, end, old_val, new_val); // 用 new_val 替换等于 old_val 的每个匹配元素
replace_if(beg, end, unaryPred, new_val); // 用 new_val 替换满足 unaryPred 的每个匹配元素

// 使用双向迭代器的写算法，要求双向选代器（bidirectional iterator）
copy_backward(beg, end, dest); // 从输入范围中拷贝元素到指定目的位置。如果范围为空,则返回值为 dest；否则，返回值表示从 *beg 中拷贝或移动的元素。
move_backward(beg, end, dest);  // 从输入范围中移动元素到指定目的位置。如果范围为空,则返回值为 dest；否则,返回值表示从 *beg 中拷贝或移动的元素。
inplace_merge(beg, mid, end); // 将同一个序列中的两个有序子序列合并为单一的有序序列。beg 到 mid 间的子序列和 mid 到 end 间的子序列被合并，并被写入到原序列中。使用 < 比较元素。
inplace_merge(beg, mid, end, comp); // 将同一个序列中的两个有序子序列合并为单一的有序序列。beg 到 mid 间的子序列和 mid 到 end 间的子序列被合并，并被写入到原序列中。使用给定的 comp 操作。

// 划分算法，要求双向选代器（bidirectional iterator）
is_partitioned(beg, end, unaryPred); // 如果所有满足谓词 unaryPred 的元素都在不满足 unarypred 的元素之前，则返回 true。若序列为空，也返回 true
partition_copy(beg, end, dest1, dest2, unaryPred); // 将满足 unaryPred 的元素拷贝到到 dest1，并将不满足 unaryPred 的元素拷贝到到 dest2。返回一个迭代器 pair，其 first 成员表示拷贝到 dest1 的的元素的末尾，second 表示拷贝到 dest2 的元素的末尾。
partitioned_point(beg, end, unaryPred); // 输入序列必须是已经用 unaryPred 划分过的。返回满足  unaryPred 的范围的尾后迭代器。如果返回的迭代器不是 end，则它指向的元素及其后的元素必须都不满足 unaryPred
stable_partition(beg, end, unaryPred); // 使用 unaryPred 划分输入序列。满足 unaryPred 的元素放置在序列开始，不满足的元素放在序列尾部。返回一个迭代器，指向最后一个满足 unaryPred 的元素之后的位置如果所有元素都不满足 unaryPred，则返回 beg
partition(beg, end, unaryPred); // 使用 unaryPred 划分输入序列。满足 unaryPred 的元素放置在序列开始，不满足的元素放在序列尾部。返回一个迭代器，指向最后一个满足 unaryPred 的元素之后的位置如果所有元素都不满足 unaryPred，则返回 beg

// 排序算法，要求随机访问迭代器（random-access iterator）
sort(beg, end); // 排序整个范围
stable_sort(beg, end); // 排序整个范围（稳定排序）
sort(beg, end, comp); // 排序整个范围
stable_sort(beg, end, comp); // 排序整个范围（稳定排序）
is_sorted(beg, end); // 返回一个 bool 值，指出整个输入序列是否有序
is_sorted(beg, end, comp); // 返回一个 bool 值，指出整个输入序列是否有序
is_sorted_until(beg, end); // 在输入序列中査找最长初始有序子序列，并返回子序列的尾后迭代器
is_sorted_until(beg, end, comp); // 在输入序列中査找最长初始有序子序列，并返回子序列的尾后迭代器
partial_sort(beg, mid, end); // 排序 mid-beg 个元素。即，如果 mid-beg 等于 42，则此函数将值最小的 42 个元素有序放在序列前 42 个位置
partial_sort(beg, mid, end, comp); // 排序 mid-beg 个元素。即，如果 mid-beg 等于 42，则此函数将值最小的 42 个元素有序放在序列前 42 个位置
partial_sort_copy(beg, end, destBeg, destEnd); // 排序输入范围中的元素，并将足够多的已排序元素放到 destBeg 和 destEnd 所指示的序列中
partial_sort_copy(beg, end, destBeg, destEnd, comp); // 排序输入范围中的元素，并将足够多的已排序元素放到 destBeg 和 destEnd 所指示的序列中
nth_element(beg, nth, end); // nth 是一个迭代器，指向输入序列中第 n 大的元素。nth 之前的元素都小于等于它，而之后的元素都大于等于它
nth_element(beg, nth, end, comp); // nth 是一个迭代器，指向输入序列中第 n 大的元素。nth 之前的元素都小于等于它，而之后的元素都大于等于它

// 使用前向迭代器的重排算法。普通版本在输入序列自身内部重拍元素，_copy 版本完成重拍后写入到指定目的序列中，而不改变输入序列
remove(beg, end, val); // 通过用保留的元素覆盖要删除的元素实现删除 ==val 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_if(beg, end, unaryPred); // 通过用保留的元素覆盖要删除的元素实现删除满足 unaryPred 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_copy(beg, end, dest, val); // 通过用保留的元素覆盖要删除的元素实现删除 ==val 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
remove_copy_if(beg, end, dest, unaryPred); // 通过用保留的元素覆盖要删除的元素实现删除满足 unaryPred 的元素，返回一个指向最后一个删除元素的尾后位置的迭代器
unique(beg, end); // 通过对覆盖相邻的重复元素（用 == 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique (beg, end, binaryPred); // 通过对覆盖相邻的重复元素（用 binaryPred 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique_copy(beg, end, dest); // 通过对覆盖相邻的重复元素（用 == 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
unique_copy_if(beg, end, dest, binaryPred); // 通过对覆盖相邻的重复元素（用 binaryPred 确定是否相同）实现重排序列。返回一个迭代器，指向不重复元素的尾后位置
rotate(beg, mid, end); // 围绕 mid 指向的元素进行元素转动。元素 mid 成为为首元素，随后是 mid+1 到到 end 之前的元素，再接着是 beg 到 mid 之前的元素。返回一个迭代器，指向原来在 beg 位置的元素
rotate_copy(beg, mid, end, dest); // 围绕 mid 指向的元素进行元素转动。元素 mid 成为为首元素，随后是 mid+1 到到 end 之前的元素，再接着是 beg 到 mid 之前的元素。返回一个迭代器，指向原来在 beg 位置的元素

// 使用双向迭代器的重排算法
reverse(beg, end); // 翻转序列中的元素，返回 void
reverse_copy(beg, end, dest);; // 翻转序列中的元素，返回一个迭代器，指向拷贝到目的序列的元素的尾后位置

// 使用随机访问迭代器的重排算法
random_shuffle(beg, end); // 混洗输入序列中的元素，返回 void
random_shuffle(beg, end, rand); // 混洗输入序列中的元素，rand 接受一个正整数的随机对象，返回 void
shuffle(beg, end, Uniform_rand); // 混洗输入序列中的元素，Uniform_rand 必须满足均匀分布随机数生成器的要求，返回 void

// 最小值和最大值，使用 < 运算符或给定的比较操作 comp 进行比较
min(val1, va12); // 返回 val1 和 val2 中的最小值，两个实参的类型必须完全一致。参数和返回类型都是 const的引引用，意味着对象不会被拷贝。下略
min(val1, val2, comp);
min(init_list);
min(init_list, comp);
max(val1, val2);
max(val1, val2, comp);
max(init_list);
max(init_list, comp);
minmax(val1, val2); // 返回一个 pair，其 first 成员为提供的值中的较小者，second 成员为较大者。下略
minmax(vall, val2, comp);
minmax(init_list);
minmax(init_list, comp);
min_element(beg, end); // 返回指向输入序列中最小元素的迭代器
min_element(beg, end, comp); // 返回指向输入序列中最小元素的迭代器
max_element(beg, end); // 返回指向输入序列中最大元素的迭代器
max_element(beg, end, comp); // 返回指向输入序列中最大元素的迭代器
minmax_element(beg, end); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素
minmax_element(beg, end, comp); // 返回一个 pair，其中 first 成员为最小元素，second 成员为最大元素

// 字典序比较，根据第一对不相等的元素的相对大小来返回结果。如果第一个序列在字典序中小于第二个序列，则返回 true。否则，返回 fa1se。如果个序列比另一个短，且所有元素都与较长序列的对应元素相等，则较短序列在字典序中更小。如果序列长度相等，且对应元素都相等，则在字典序中任何一个都不大于另外一个。
lexicographical_compare(beg1, end1, beg2, end2);
lexicographical_compare(beg1, end1, beg2, end2, comp);