STL(标准模板库)

概念: STL:标准模板库,是C++标准库的重要组成部分,STL,英文全称 standard template library,中文可译为标准模板库或者泛型库,其包含有大量的模板类和模板函数,STL 是一些容器、算法和其他一些组件的集合,所有容器和算法都是总结了几十年来算法和数据结构的研究成果,注意,这里提到的容器,本质上就是封装有数据结构的模板类,例如 list、vector、set、map 等,
由概念便可以知道,STL中的所有数据结构都是以模板的方式创建的
容器(数据结构),算法(算法),迭代器(算法访问容器元素的工具),
C++ STL 一共提供了六大组件,包括 容器,算法,迭代器,仿函数,配接器和配置器 ,彼此可以组合套用。
容器通过配置器取得数据存储空间;
算法通过迭代器存取容器内容;
仿函数可以协助算法完成不同的策略变化;
配接器可以应用于容器、仿函数和迭代器。

  1. 容器:包括各种数据结构,如vector,queue, deque,,set, map,用来存放数据,分为序列式容器和关联式容器,实现的角度来讲是一种类模板。
容器可分为:序列式容器,关联式容器
序列式:容器中的元素有顺序关系
关联式:容器中的元素不要求有顺序关系
2、算法:各种常用的算法,问题的解法,如sort (插入,快排,堆排序), search (二分查找),从实现的角度来讲是一种方法模板。
3、迭代器:从实现的角度来看,迭代器是一种将 operator,operator->,operator++,operator-等指针相关操作赋予重载的类模板,所有的 STL 容器都有自己的迭代器。是容器和算法的粘合剂,算法要通过迭代器才可以访问容器中的元素,迭代器会通过自己的方法找到容器中的元素,
4、仿函数:从实现的角度看,仿函数是一种重载了 operator() 的类或者类模板。可以帮助算法实现不同的策略。
5、配接器:一种用来修饰容器或者仿函数或迭代器接口(参数)的东西。
6、配置器:负责空间配置与管理,从实现的角度讲,配置器是一个实现了动态空间配置、空间管理,空间释放的类模板。

vector(向量)
怎么使用:
  1. 包含头文件vector和命名空间std
vector 容器以类模板 vector( T 表示存储元素的类型)的形式定义在 头文件中,并位于 std 命名空间中。
  1. 五种创建容器方法:
(1)先创建空容器,再添加容器容量和元素
(2)创建的同时初始化容器元素
vector v5{a,b,c...}
vector v5={a,b,c...}
  1. 创建的同时指定容器容量,不给出容器元素
vector v4[n][]永远代表个数
说明:包含n个重复执行了值初始化的对象(即值为0)
  1. 创建的同时指定容器容量和重复元素
vector myv(n)和vectormyv[n]; vectormyv[n]是vector类型的数组。
vectormyv(n)是建立一个vector类型的类对象(容器),在这个类对象中初始化10个int类型的数据空间。

注意,注意,注意:
所有容器的类型,比如vector 仅仅表示变量的中存储的元素的类型。
vector myv; //myv中存放vector容器
vector> myv; //容器中存放vector>类型容器。
vector myv和vector myv[n]的区别 一个是变量,一个是数组。
vector类型的变量才具有vector的函数。
数组中的元素才是vector类型的变量,才具有vector的函数。

理解这些一定要记住:
容器的本质------类
要注意:建立的是一个类对象还是一个保存类对象的数组。
变量或者数组中保存的是一个个的类

vector的下标访问 vector中重载了[ ],所以也可以用下标访问vector容器的元素。

vector v3(n,val)
说明:包含n个重复的val元素
(5)通过存储元素类型相同的其它 vector 容器,也可以创建
的 vector 容器,例如:
vector v1
vector v2(v1)()永远代表复制
vector v2 = v1

如果不想复制其它容器中所有的元素,可以用一对指针或者迭代器来指定初始值的范围,例如:
纯文本复制
  1. int array[]={1,2,3};
  2. std::vectorvalues(array, array+2); //values 将保存{1,2}
  3. std::vectorvalue1{1,2,3,4,5};
  4. std::vectorvalue2(std::begin(value1),std::begin(value1)+3); //value2保存{1,2,3}

下面配合《STL源码剖析》的源码观看:
vector 源码属性(本质): 模板类
所有vector的函数都包含在vector类中
所以通过vector建立的对象,都是类对象。

vector的迭代器 要注意区分迭代器和迭代器的数据类型:
迭代器的数据类型:
本质上就是模板参数的类型,只是结果typedef再次声明出来的另一个名字,方便对容器元素进行操作。
迭代器:
迭代器就是迭代器对象
迭代器是通过迭代器类型定义出来的指针变量(迭代器对象),也可以是函数返回的迭代器指针。
本质上:就是一个普通指针,是模板参数类型的指针《STL源码》看源码
vector的迭代器指向元素地址,对迭代器解引用就是元素值。

vector的数据结构 内存空间
注意:vector的内存空间是连续的内存空间,(不像list容器是不连续内存,用链表来实现连接)
vector模板类中定义了三个迭代器,分别指向vector容器内存空间的头,已经使用的空间的尾,可用空间的尾。--看源码




vector模板的成员函数:
函数成员
函数功能
begin()
返回指向容器中第一个元素的迭代器。
end()
返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
【STL(标准模板库)】rbegin()
返回指向最后一个元素的迭代器。
rend()
返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()
和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend()
和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin()
和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend()
和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size()
返回实际元素个数。
max_size()
返回元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
resize()
改变实际元素的个数。resize(10):指定容量,不指定多出来的元素,系统默认用0代替(注意:此时被0代替的位置也有元素0);resize(10,23):指定容量,多出来的用23填补;如果指定的容量比原来小,多出来的则被删除,被删除的迭代器将失效
capacity()
返回当前容量.(不是容量元素个数),capacity 一般大于size的原因是为了避免 每次增加数据时都要重新分配内存,所以一般会 生成一个较大的空间,以便随后的数据插入,capacity返回的是以元素个数为单位的容量
empty()
判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
reserve()
为容器预留容量空间(注意预留的是容量空间,不要拿size()的返回值和reserve()的返回值作比较)。容器每一次存储新的内存,都会从新开辟新的空间如果提前知道容器元素个数和容器容量,可以提前为容器预留容量空间,reserve只适用于vector和string
shrink _to_fit()
将内存减少到等于当前元素实际所使用的大小。
operator[ ]
重载了 [ ] 运算符,可以向访问数组中元素那样,通过下标即可访问甚至修改 vector 容器中的元素。
at()
使用经过边界检查的索引访问指定位置的元素。
front()
返回第一个元素的引用。
back()
返回最后一个元素的引用。
data()
返回指向容器中第一个元素的指针。
assign()
用新元素替换原有内容。
push_back()
一次在序列的尾部添加一个元素。注意:这些插入和删除的函数没有返回值,push,pop
pop_back()
移出序列尾部的元素。注意:vector没有pop_front()函数
所以想要删除vector容器的首元素就要使用erase函数,erase删除一个元素之后,之后的元素就会补上来,不会空出留着这个位置。<在数组实现队列中使用>。
队列的实现用list更好,因为list有pop_front函数。
insert()
在指定的位置插入一个或多个元素。(page--125),可以有两个,三个参数,两个代表插入一个,三个代表插入n个。
erase()
移出一个元素或一段元素。erase(v1.begin(),v1.end()),移除元素的位置后面的元素会自动补上。可以一个参数,也可以两个,迭代器类型参数。注意:erase返回删除元素之后的元素的迭代器,而不是被删除元素的迭代器。
clear()
移出所有的元素,容器内存大小不变。(看源码page--124)
swap()
交换两个容器的所有元素,参数是一个容器名(类对象),两个容器的元素不一样也可以成功交换。
emplace()
在指定的位置直接生成一个元素。只能有两个参数(position,x),第一个是迭代器,第二个是插入的值。
emplace_back()
在序列尾部生成一个元素。
find()分两种
一种是头文件中定义的三个函数的find(),一种是容器内部定义的以指定数值为参数的find().
三个参数的find也可以用来查找容器中的数据,但是效率不高,所以最好使用容器内部定义的find.
如果元素存在,返回元素迭代器,不存在返回end()的迭代器。
find(ite.begin(),ite.end(),要寻找的参数)
指定一段寻找的区间,去寻找某一个元素。

find(值)
#include #include #include using namespace std; int main() { list inst={1,23,4,4}; if(find(inst.begin(),inst.end(),23)!=inst.end()) cout<<"23"<

注意头文件:algorithm
vector的容量 vector对象刚建立,没赋值时,size=capacity=0; .
vector容器扩张原则:len = size()!=0?2*size():1;
如果原来的容器的大小不为0,扩展两倍的容量,扩展之后赋值元素到新地址,释放就地址。
vector什么时候会进行扩容 看源码可知:当push_back()时,判断要插入的位置已经是最后一个可用位置的的时候就会进行扩容。
vector以及其他容器扩容的集中情况
push_back,insert,emplace都会自动扩容,即使刚开始没有容量。
但是注意一种情况:不能利用[ ]插入值的形式给容器扩容,对于一个还没有建立任何空间的容器对象,不能企图用[ ]为期插入数据,否则就是段错误,因为这个对象虽然有了地址,但是其存储数据的地址没有分配,系统不知道要存放在哪。
#include #include using namespace std; int main(){ vector vec; cout<<"push_back:"<
文章图片

容器容量不变,但是可以向超出容量范围的地址插入数据
[ ]的访问原则
访问容器或者数组本身分配所得的内存内的数据,这样才是安全的

不要担心容器开辟的内存不够而无法存入,内存不够会自动开辟。
resize()增加容器元素个数才可以增加容器元素,reserve()增加容器容量,不可以增加容器元素
仅通过 reserve() 成员函数增加 value 容器的容量,其大小并没有改变;但通过 resize() 成员函数改变 value 容器的大小,它的容量可能会发生改变。另外需要注意的是,通过 resize() 成员函数减少容器的大小(多余的元素会直接被删除),不会影响容器的容量。
圆括号 () 和大括号 {} 是有区别的,前者(vectorv(20) )表示元素的个数,而后者(vectorv{20} ) 则表示 vector 容器中只有一个元素 20。

我们可能需要将容器的容量和大小保存在变量中,要知道 vector 对象的容量和大小类型都是 vector::size_type 类型。因此,当定义一个变量去保存这些值时,可以如下所示:
  1. vector::size_type cap = value.capacity();
  2. vector::size_type size = value.size();
size_type 类型是定义在由 vector 类模板生成的 vecotr 类中的,它表示的真实类型和操作系统有关,在 32 位架构下普遍表示的是 unsigned int 类型,而在 64 位架构下普通表示 unsigned long 类型。

迭代器的使用:
什么是迭代器:
迭代器就是地址
迭代器和 C++ 的指针非常类似,它可以是需要的任意类型,通过迭代器可以指向容器中的某个元素,如果需要,还可以对该元素进行读/写操作。

注意迭代器不是引用,可以用迭代器作实参传递去改变容器内容,但是形参不要定义为引用,直接定义为:
template
void container_change(I i){};

vector 支持迭代器的成员函数
成员函数
功能
begin()
返回指向容器中第一个元素的正向迭代器;如果是 const 类型容器,在该函数返回的是常量正向迭代器。
end()
返回指向容器最后一个元素之后一个位置的正向迭代器;如果是 const 类型容器,在该函数返回的是常量正向迭代器。此函数通常和 begin() 搭配使用。
rbegin()
返回指向最后一个元素的反向迭代器;如果是 const 类型容器,在该函数返回的是常量反向迭代器。
rend()
返回指向第一个元素之前一个位置的反向迭代器。如果是 const 类型容器,在该函数返回的是常量反向迭代器。此函数通常和 rbegin() 搭配使用。
cbegin()
和 begin() 功能类似,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。
cend()
和 end() 功能相同,只不过其返回的迭代器类型为常量正向迭代器,不能用于修改元素。
crbegin()
和 rbegin() 功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。
crend()
和 rend() 功能相同,只不过其返回的迭代器类型为常量反向迭代器,不能用于修改元素。

vector<>容器和普通数组的区别:
普通数组的容量是固定的,vector<>容器的容量是可以变的,即动态的。
vectorv2(v1.begin(),v1.end());
将v1中所有的数据复制到v2中
同样功能可以用:
vectorv2;
v2.assign(v1.begin(),v1.end());

怎么访问vector容器中的元素:
  1. v.at(n)返回容器位置为n的元素的引用(注意第一个位置为0)
  2. vector容器也是数组,可以用v[n]访问

所谓泛型编程就是模板编程,泛型就是广泛可以使用的类型,即模板
五类主要的序列容器:
vector,array,list,deque,forward_list

vector实现二位存储 vector>
依照这个原理,可以产生多维存储..........
vector也可以通过多级下标访问元素---myv[i][j]

array 本质 模板结构体
template struct array { // 类型成员 using value_type= T; using pointer= T * ; using const_pointer= const T*; using reference= T & ; using const_reference = const T&; using iterator= T * ; // array 的迭代器即普通指针 using const_iterator= const T*; using size_type= std::size_t; using difference_type= std::ptrdiff_t; using reverse_iterator= std::reverse_iterator; using const_reverse_iterator = std::reverse_iterator; typedef__array_traits AT_Type; typename AT_Type::TypeM_elems; // 数组 T[N] 或空数组// ===================== 迭代器 =====================constexpr iterator begin() { return iterator(data()); } constexpr iterator end() { return iterator(data() + N); } constexpr const_iterator begin() const { return const_iterator(data()); } constexpr const_iterator end() const { return const_iterator(data() + N); } // 省略 cbegin(), cend(), rbegin(), rend(), crbegin(), crend()// ===================== 对外接口 =====================void fill(const value_type& val) { std::fill_n(begin(), end(), val); } void swap(array& other) { std::swap_ranges(begin(), end(), other.begin()); }constexpr size_type size() const { return N; } constexpr size_type max_size() const { return N; } constexpr bool empty() const { return size() == 0; }constexpr reference operator[](size_type n) { return AT_Type::S_ref(M_elems, n); } constexpr const_reference operator[](size_type n) const { return AT_Type::S_ref(M_elems, n); }constexpr reference at(size_type n) { return n < N ? AT_Type::S_ref(M_elems, n) : /* out_of_range */; }constexpr const_reference at(size_type n) const { return n < N ? AT_Type::S_ref(M_elems, n) : /* out_of_range */ ; }constexpr reference front() { return *begin(); } constexpr reference back() { return N ? *(end() - 1) : *end(); } constexpr const_reference front() const { return AT_Type::S_ref(M_elems, 0); } constexpr const_reference back() const { return N ? AT_Type::S_ref(M_elems, N - 1) : AT_Type::S_ref(M_elems, 0); }constexpr pointer data() { return AT_Type::S_ptr(M_elems); } constexpr const_pointer data() const { return AT_Type::_S_ptr(M_elems); } };

array容器不是array数组,它如同其他容器拥有自己的成员函数
和其它容器不同,array 容器的大小是固定的,无法动态的扩展或收缩,这也就意味着,在使用该容器的过程无法借由增加或移除元素而改变其大小,它只允许访问或者替换存储的元素。
每一个容器的使用都要包含自己的头文件,头文件在std命名空间中
array容器的头文件:#include
array容器的迭代器 array的迭代器也是一个普通指针,是模板参数类型的指针
array的迭代器指向元素地址,对迭代器解引用就是元素值。
array容器的建立: array容器的建立一定要给出存储的数据类型和容器的大小
1,array values;
由此,就创建好了一个名为 values 的 array 容器,其包含 10 个浮点型元素。但是,由于未显式指定这 10 个元素的值,因此使用这种方式创建的容器中,各个元素的值是不确定的,并不一定就是0(array 容器不会做默认初始化操作)
#include "iostream" #include using namespace std; void insert(array& arr) { for(int i=0; i<10; i++) { scanf("%d",&arr[i]); } } void display(array& arr) { for(int i=0; iarr; insert(arr); display(arr); return 0; } 输出: wujinyou@wujinyou:~/CCCPro/STL_dir$ ./stl_array.o 12 34 54 3 4 23 123 34 23 43 12 34 54 3 4 23 123 34 23 43 1980142733 21845 1868968680 32730 1980142656 21845 0 0 1980141856 21845

2,arrayvalues{};
将所有的元素初始化为 0(注意:不是为空,而是0) 或者和默认元素类型等效的值:
3,当然,在创建 array 容器的实例时,也可以像创建常规数组那样对元素进行初始化:array values {0.5,1.0,1.5,,2.0};
这里只初始化了前 4 个元素,剩余的元素都会被初始化为 0.0
array容器成员函数汇总
成员函数
功能
begin()
返回指向容器中第一个元素的随机访问迭代器。
end()
返回指向容器最后一个元素之后一个位置的随机访问迭代器,通常和 begin() 结合使用。
rbegin()
返回指向最后一个元素的随机访问迭代器。
rend()
返回指向第一个元素之前一个位置的随机访问迭代器。
cbegin()
和 begin() 功能相同,只不过在其基础上增加了 const 属性,不能用于修改元素。
cend()
和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin()
和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend()
和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size()
返回容器中当前元素的数量,其值始终等于初始化 array 类的第二个模板参数 N。注意:这里的butongyv其他容器的size(),不是获取有多少元素,就相当于vector的capacity.
max_size()
返回容器可容纳元素的最大数量,其值始终等于初始化 array 类的第二个模板参数 N。
empty()
判断容器是否为空,和通过 size()==0 的判断条件功能相同,但其效率可能更快。
at(n)
返回容器中 n 位置处元素的引用,该函数自动检查 n 是否在有效的范围内,如果不是则抛出 out_of_range 异常。
front()
返回容器中第一个元素的直接引用,该函数不适用于空的 array 容器。
back()
返回容器中最后一个元素的直接应用,该函数同样不适用于空的 array 容器。
data()
返回一个指向容器首个元素的指针。利用该指针,可实现复制容器中所有元素等类似功能。
fill(val)
将 val 这个值赋值给容器中的每个元素。
array1.swap(array2)
交换 array1 和 array2 容器中的所有元素,但前提是它们具有相同的长度和类型。


访问array容器中单个元素 首先,可以通过容器名[]的方式直接访问和使用容器中的元素,这和 C++ 标准数组访问元素的方式相同,例如:
  1. values[4] = values[3] + 2.O*values[1];
此行代码中,第 5 个元素的值被赋值为右边表达式的值。需要注意的是,使用如上这样方式,由于没有做任何边界检查,所以即便使用越界的索引值去访问或存储元素,也不会被检测到。(越界无检索)

为了能够有效地避免越界访问的情况,可以使用 array 容器提供的 at() 成员函数,例如 :
2,values.at (4) = values.at(3) + 2.O*values.at(1);
这行代码和前一行语句实现的功能相同,其次当传给 at() 的索引是一个越界值时,程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时,建议大家使用 at(),除非确定索引没有越界。(越界可检索)
3,array 容器提供了 data() 成员函数,通过调用该函数可以得到指向容器首个元素的指针
4,在头文件中还重载了 get() 全局函数,该重载函数的功能是访问容器中指定的元素,并返回该元素的引用。需要注意的是,该模板函数中,参数的实参必须是一个在编译时可以确定的常量表达式,所以它不能是一个循环变量。
重载函数get():
形式:get(name)
n为指定容器元素,name为容器名称

array和vector的比较
空间 模板参数
vector 动态空间:
本质上也是静态空间,只是vector内部机制会自动进行内存的重新配置,移动数据,释放旧空间。
随着元素的加入,内部空间会自动拓展空间来容纳新元素
空间拓展方式:自动拓展
2个,但是建立容器时只需要一个参数
array 静态空间:
内存空间的大小固定,如果所需内存超出固定内存,需要重新配置,移动数据,释放旧空间。
空间拓展方式:程序员手动拓展
2个,建立容器也要两个

LIST: 本质是环状双向链表
源码属性:
模板类
list节点: list节点实质是一个模板结构体
templatestruct _list_node{ typedef void* void_pointer; void_pointer prev; //previous void_pointer next; T data; };

可见,list的节点是一个以结构体形成的双向链表
其中第一个元素的前向指针总为 null,因为它前面没有元素;同样,尾部元素的后向指针也总为 null。
元素和节点的区别:
节点是容器(链表)中的一个节点,元素是存储于节点中的数据
list--iterator: list容器的迭代器不同vector和array的迭代器,不再是普通数据类型的指针,而是一个模板结构体
为什么list容器的迭代器不是list结点模板结构体指针:
因为list的迭代器需要进行进行一些复杂的工作,所以需要把它自己定义为一个具有复杂功能的模板结构体
比如:array和vector的容器内存是连续的,所以迭代器加1减1就是是在连续内存的前后移动
但是list容器是双向链表,内存不连续,迭代器加1,减1就需要进行编程处理,编写函数来向前一个或者后一个结点指定
迭代器不指向结点,而是含有结点变量
既然list的迭代器不指向结点中的数据,也不指向结点,那么迭代器如果对结点和结点中的元素进行操作:
迭代器中定义一个结点类型的变量,用来记录结点,以及对链表的结点进行操作

源码:
STL(标准模板库)
文章图片

STL(标准模板库)
文章图片

在list模板类中将以上类声明为:iterator(迭代器)
list的迭代器不是指向结点,也不是指向结点中的元素,但是同样的。所用的迭代器解引用都是容器的元素,而list是利用的对解引用符的重载函数输出


list--container: STL(标准模板库)
文章图片

list容器是一个模板类
list的所有的函数,迭代器都是这个模板类的成员
list容器的优点:
1,很方便的向容器中插入节点,添加数据值
2,方便删除节点,和数据值,而不会影响其他的节点和数据
3,链表的建立:只需要不断插入数据就可以快速建立链表
list容器的缺点:
1,不方便访问节点数据值
list容器的使用场景:
需要不断添加,删除,改动元素

list container的成员函数: 1,begin()
2,end()
3,void push_back(const T& x)
功能:插入一个节点作为尾节点
实现原理:
STL(标准模板库)
文章图片

4,void push_front(const T& x)
插入一个节点作为头节点
和push_back()相对应
5,iterator erase(iterator position)
移除迭代器position所指的节点
6,void pop_front()
移除头节点
7,void pop_back()
移除尾节点
8,void list::clear()
清除所有节点(删除整个链表)
9,void list::remove(const T& x)
清除数值为x的所有节点
10,voidlist:: unique()
清除数值相同的连续节点,保留一个
list成员函数列表:
表 2 list 容器可用的成员函数
成员函数 功能
begin() 返回指向容器中第一个元素的双向迭代器。
end() 返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin() 返回指向最后一个元素的反向双向迭代器。
rend() 返回指向第一个元素所在位置前一个位置的反向双向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
empty() 判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
size() 返回当前容器实际包含的元素个数。
max_size() 返回容器所能包含元素个数的最大值。这通常是一个很大的值,一般是 232-1,所以我们很少会用到这个函数。
front() 返回第一个元素的引用。(相当于返回了第一个元素)
back() 返回最后一个元素的引用。
assign() 用新元素替换容器中原有内容。
emplace_front() 在容器头部生成一个元素。该函数和 push_front() 的功能相同,但效率更高。
push_front() 在容器头部插入一个元素。注意:插入和删除函数没有返回值。
pop_front() 删除容器头部的一个元素。
pop_back() 删除容器尾部的一个元素。
emplace_back() 在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同,但效率更高。
push_back() 在容器尾部插入一个元素。
emplace() 在容器中的指定位置插入元素。该函数和 insert() 功能相同,但效率更高。
insert() 在容器中的指定位置插入元素。
erase() 删除容器中一个或某区域内的元素。返回删除元素的下一个元素的迭代器,如果是最后一个就返回头节点,因为list是循环链表。和vector反着来。
swap() 交换两个容器中的元素,必须保证这两个容器中存储的元素类型是相同的。
resize() 调整容器的大小。
clear() 删除容器存储的所有元素。
splice() 将一个 list 容器中的元素插入到另一个容器的指定位置。
remove(val) 删除容器中所有等于 val 的元素。
remove_if() 删除容器中满足条件的元素。
unique() 删除容器中相邻的重复元素,只保留一个。
merge() 合并两个事先已排好序的 list 容器,并且合并之后的 list 容器依然是有序的。
sort() 通过更改容器中元素的位置,将它们进行排序。
reverse() 反转容器中元素的顺序。



各容器之间的比较
源码本质 iterator本质 ierator的指向 构造容器需要的参数/个
vector 模板类 普通数据类型的指针 vector的迭代器指向元素地址,对迭代器解引用就是元素值。 1
array 摸版结构体 普通数据类型的指针 array的迭代器指向元素地址,对迭代器解引用就是元素值。 2
list 模板类 模板结构体指针 包含结点变量,而不是指向结点 1
list的下标访问方法 注意List不同于其他容器,list不能通过下标访问元素

以下内容来源-----链接
序列式容器 所谓STL序列式容器,其共同的特点是不会对存储的元素进行排序.
包括 array、vector、deque、list 和 forward_list 5种容器。

存储的方式:
无论是哪种序列式容器,其存储的都是 C++ 基本数据类型(诸如 int、double、float、string 等)或使用结构体自定义类型的元素。

关联式容器 关联式容器在存储元素时还会为每个元素在配备一个键,整体以键值对的方式存储到容器中。相比前者,关联式容器可以通过键值直接找到对应的元素,而无需遍历整个容器。另外,关联式容器在存储元素,默认会根据各元素键值的大小做升序排序
相比其它类型容器,关联式容器查找、访问、插入和删除指定元素的效率更高。
包括 map、multimap、set 以及 multiset 这 4 种容器

存储的方式:---键值对
关联式容器在存储元素值的同时,还会为各元素额外再配备一个值(又称为“键”,其本质也是一个 C++ 基础数据类型或自定义类型的元素),它的功能是在使用关联式容器的过程中,如果已知目标元素的键的值,则直接通过该键就可以找到目标元素,而无需再通过遍历整个容器的方式。

弃用序列式容器,转而选用关联式容器存储元素,往往就是看中了关联式容器可以快速查找、读取或者删除所存储的元素,同时该类型容器插入元素的效率也比序列式容器高。

序列式容器中存储的元素默认都是未经过排序的,而使用关联式容器存储的元素,默认会根据各元素的键值的大小做升序排序。
关联式容器所具备的这些特性,归咎于 STL 标准库在实现该类型容器时,底层选用了 「红黑树」这种数据结构来组织和存储各个键值对。

注意,基于各个关联式容器存储数据的特点,只有各个键值对中的键和值全部对应相等时,才能使用 set 和 multiset 关联式容器存储,否则就要选用 map 或者 multimap 关联式容器。

pair 类模板 pair 类模板定义在头文件中


map 模板类

注意一些函数的参数,比如find函数:利用key寻找值,返回迭代器,而不是利用值寻找值。
find(key) 在 map 容器中查找键为 key 的键值对,如果成功找到,则返回指向该键值对的双向迭代器;反之,则返回和 end() 方法一样的迭代器。另外,如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。

map容器的迭代器 一定要注意:map容器中存放的不是键值对,也不是值。而是pair
对map容器的迭代器进行指向操作,指向的是pair结构体中的函数或者变量。
那么对迭代器解引用也应该是pair中存储的值。
对于map的迭代器(iterator),对其解引用后,就是一个pair对象,所以iterator->first = 键、iterator->second = 值。
map容器和其他容器迭代器解引用的相同点和不同点 相同点:解引用的结果都是容器中存储的元素(对象)。
不同点:
其他容器解引用出来的元素就是存储的值;
map容器解引用出来的是也是其元素,但是这个元素是一个pair对象,而不直接就是存储的值。
总结一句话:
容器中存储的是什么,迭代器解引用就是的结果就是什么。

map容器建立和存储的过程 建立map容器
容器内建立pair对象存储键值对
容器内建立RB-tree对象存储pair。

map容器初始化和赋值方法 1,赋值:{{},{}}赋值法。
2,拷贝:利用赋值构造函数:mapffmap(fmap);
3,截取:
map 类模板还支持取已建 map 容器中指定区域内的键值对,创建并初始化新的 map 容器。例如:
  1. std::mapmyMap{ {"C语言教程",10},{"STL教程",20} };
  2. std::mapnewMap(++myMap.begin(), myMap.end());
这种方法注意end()的选择,如果要选择到最后,不要--mymap.end();
4,下标赋值。
mapmymap{{0,"fangfang"},{1,"xiaoli"}}; auto ite=mymap.find(1); cout<<(*ite).second<first<<" "<second< fmap; fmap[0]="aaaa"; fmap[1]="bbbb"; fmap[2]="cccc"; int i=0; for(i; iffmap(fmap); for(i=0; i

map容器不能像vector一样从数组中获取值。
5,insert插入法:
insert可以先建立pair键值对再插入,也可以插入临时值(右值引用插入):
int main() { mapmymap; pair ret=mymap.insert({"China","Beijing"}); cout<first<<"---"<second<first<<"---"<second<


注意:
(1,pair键值对的定义,
(2,insert返回类型以及如何定义返回类型变量。
(3,insert还可以同时插入多个键值对。
关于Insert更多看-------连接
6,两个效率更高的插入方法:
1》
template
pair emplace (Args&&... args);
  • 当该方法将键值对成功插入到 map 容器中时,其返回的迭代器指向该新插入的键值对,同时 bool 变量的值为 true;
  • 当插入失败时,则表明 map 容器中存在具有相同键的键值对,此时返回的迭代器指向此具有相同键的键值对,同时 bool 变量的值为 false。
  • 返回类型同insert
2》
template
iterator emplace_hint (const_iterator position, Args&&... args);
  1. 该方法不仅要传入创建键值对所需要的数据,还需要传入一个迭代器作为第一个参数,指明要插入的位置(新键值对键会插入到该迭代器指向的键值对的前面);
  2. 该方法的返回值是一个迭代器,而不再是 pair 对象。当成功插入新键值对时,返回的迭代器指向新插入的键值对;反之,如果插入失败,则表明 map 容器中存有相同键的键值对,返回的迭代器就指向这个键值对。
3. 成功,返回一个指向键值对的迭代器。
int main() { mapmymap; pair ret=mymap.emplace("China",1); cout<first<<""<second<first<<""<second<

map访问值的方法 1,迭代器指向second对象:ite-second;
2,迭代器解引用之后引用second:(*ite).second;
3,下标访问(键作为下标访问):
需要特别注意的是:这个下标是键值,而不一定是0,1,2这些数字,。
eg:
mymap["YunNan"]
因为map是可以修改值的值的,所以:
mymap["YunNan"]="sanqizhixiang"

注意,只有当 map 容器中确实存有包含该指定键的键值对,借助重载的 [ ] 运算符才能成功获取该键对应的值;反之,若当前 map 容器中没有包含该指定键的键值对,则此时使用 [ ] 运算符将不再是访问容器中的元素,而变成了向该 map 容器中增添一个键值对。其中,该键值对的键用 [ ] 运算符中指定的键,其对应的值取决于 map 容器规定键值对中值的数据类型,如果是基本数据类型,则值为 0;如果是 string 类型,其值为 "",即空字符串(即使用该类型的默认值作为键值对的值)。

4,除了借助 [ ] 运算符获取 map 容器中指定键对应的值,还可以使用 at() 成员方法。和前一种方法相比,at() 成员方法也需要根据指定的键,才能从容器中找到该键对应的值;不同之处在于,如果在当前容器中查找失败,该方法不会向容器中添加新的键值对,而是直接抛出 out_of_range 异常。
mymap.at("YunNan");

注意:键和值的类型任意,不是键只能为int。
map和multimap
map multimap unordered_map unorder_multimap
下标(键) 支持 不支持(原因:因为键值可以重复) 不支持

map和unorder_map的区别
链接

map的部分函数
at() 参数:键
find 参数:键
成功返回元素迭代器,失败返回end()的迭代器。

成员方法 功能
begin() 返回指向容器中第一个(注意,是已排好序的第一个)键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
end() 返回指向容器最后一个元素(注意,是已排好序的最后一个)所在位置后一个位置的双向迭代器,通常和 begin() 结合使用。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
rbegin() 返回指向最后一个(注意,是已排好序的最后一个)元素的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。
rend() 返回指向第一个(注意,是已排好序的第一个)元素所在位置前一个位置的反向双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的键值对。
find(key) 在 map 容器中查找键为 key 的键值对,如果成功找到,则返回指向该键值对的双向迭代器;反之,则返回和 end() 方法一样的迭代器。另外,如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
lower_bound(key) 返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
upper_bound(key) 返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器。如果 map 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
equal_range(key) 该方法返回一个 pair 对象(包含 2 个双向迭代器),其中 pair.first 和 lower_bound() 方法的返回值等价,pair.second 和 upper_bound() 方法的返回值等价。也就是说,该方法将返回一个范围,该范围中包含的键为 key 的键值对(map 容器键值对唯一,因此该范围最多包含一个键值对)。
empty() 若容器为空,则返回 true;否则 false。
size() 返回当前 map 容器中存有键值对的个数。
max_size() 返回 map 容器所能容纳键值对的最大个数,不同的操作系统,其返回值亦不相同。
operator[] map容器重载了 [] 运算符,只要知道 map 容器中某个键值对的键的值,就可以向获取数组中元素那样,通过键直接获取对应的值。
at(key) 找到 map 容器中 key 键对应的值,如果找不到,该函数会引发 out_of_range 异常。
insert() 向 map 容器中插入键值对。
erase() 删除 map 容器指定位置、指定键(key)值或者指定区域内的键值对。后续章节还会对该方法做重点讲解。
swap() 交换 2 个 map 容器中存储的键值对,这意味着,操作的 2 个键值对的类型必须相同。
clear() 清空 map 容器中所有的键值对,即使 map 容器的 size() 为 0。
emplace() 在当前 map 容器中的指定位置处构造新键值对。其效果和插入键值对一样,但效率更高。
emplace_hint() 在本质上和 emplace() 在 map 容器中构造新键值对的方式是一样的,不同之处在于,使用者必须为该方法提供一个指示键值对生成位置的迭代器,并作为该方法的第一个参数。
count(key) 在当前 map 容器中,查找键为 key 的键值对的个数并返回。注意,由于 map 容器中各键值对的键的值是唯一的,因此该函数的返回值最大为 1。

map的下标和解引用 其他可以进行下标和解引用的容器,解引用和下标操作结果都是取值。
但是map不同,解引用是pair对象的引用,下标才是取值。
对于下标的使用要非常注意:如果不想因为所对应的键值对不存在而创建多余键值对,就不要用下标,应该用find查找:



set
迭代器解引用 除了map。可以对迭代器解引用获取值,set也可以。

特点:
1,当使用 set 容器存储键值对时,只需要为其提供各键值对中的 value 值(也就是 key 的值)即可。
2,et 容器中各键值对的键 key 和值 value 是相等的,根据 key 排序,也就等价为根据 value 排序。
3,键和值可以是任何数据类型。
4,

set的初始化方式 1,赋值:
2,拷贝:
3,截取:


set和map的区别
map set
模板参数个数 2 1
解引用 pair对象地址
下标 支持(原因:通过下标(键)可以获取对应的值)
不支持(原因:键就是值)

set函数
表 1 C++ set 容器常用成员方法
成员方法 功能
begin() 返回指向容器中第一个(注意,是已排好序的第一个)元素的双向迭代器。如果 set 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
end() 返回指向容器最后一个元素(注意,是已排好序的最后一个)所在位置后一个位置的双向迭代器,通常和 begin() 结合使用。如果 set 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
rbegin() 返回指向最后一个(注意,是已排好序的最后一个)元素的反向双向迭代器。如果 set 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。
rend() 返回指向第一个(注意,是已排好序的第一个)元素所在位置前一个位置的反向双向迭代器。如果 set 容器用 const 限定,则该方法返回的是 const 类型的反向双向迭代器。
cbegin() 和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的元素值。
cend() 和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的元素值。
crbegin() 和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的元素值。
crend() 和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改容器内存储的元素值。
find(val) 在 set 容器中查找值为 val 的元素,如果成功找到,则返回指向该元素的双向迭代器;反之,则返回和 end() 方法一样的迭代器。另外,如果 set 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
lower_bound(val) 返回一个指向当前 set 容器中第一个大于或等于 val 的元素的双向迭代器。如果 set 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
upper_bound(val) 返回一个指向当前 set 容器中第一个大于 val 的元素的迭代器。如果 set 容器用 const 限定,则该方法返回的是 const 类型的双向迭代器。
equal_range(val) 该方法返回一个 pair 对象(包含 2 个双向迭代器),其中 pair.first 和 lower_bound() 方法的返回值等价,pair.second 和 upper_bound() 方法的返回值等价。也就是说,该方法将返回一个范围,该范围中包含的值为 val 的元素(set 容器中各个元素是唯一的,因此该范围最多包含一个元素)。
empty() 若容器为空,则返回 true;否则 false。
size() 返回当前 set 容器中存有元素的个数。
max_size() 返回 set 容器所能容纳元素的最大个数,不同的操作系统,其返回值亦不相同。
insert() 向 set 容器中插入元素。
erase() 删除 set 容器中存储的元素。
swap() 交换 2 个 set 容器中存储的所有元素。这意味着,操作的 2 个 set 容器的类型必须相同。
clear() 清空 set 容器中所有的元素,即令 set 容器的 size() 为 0。
emplace() 在当前 set 容器中的指定位置直接构造新元素。其效果和 insert() 一样,但效率更高。
emplace_hint() 在本质上和 emplace() 在 set 容器中构造新元素的方式是一样的,不同之处在于,使用者必须为该方法提供一个指示新元素生成位置的迭代器,并作为该方法的第一个参数。
count(val) 在当前 set 容器中,查找值为 val 的元素的个数,并返回。注意,由于 set 容器中各元素的值是唯一的,因此该函数的返回值最大为 1。

注意:序列式容器没有push_back(),pop_back()这样的插入函数。
序列式容器的插入都是insert(),emplace(),emplace_hint();

关联式容器的元素删除 序列式容器的删除使用----erase函数,序列式容器的这个函数有两个版本
1,只有一个参数,2,有两个参数的。参数都是迭代器。
关联式容器除了以上两种erase函数,还有一个erase函数:
3,就是可以传递一个键值参数,这会删除容器中所有和这个键值匹配的键值对,返回删除的键值对数量。
mymap.erase("YunNan");
mymap.erase(1);

注意:很多不允许重复的情况下都要想到这些容器,不要自己去统计。

multimap和multiset 允许键重复
含重复键的键值对相邻存储
这种容器可以用来存储的一种情况:
作者的所有书籍:
一个函数找到某个作者的所有书籍----equal_range(键);
返回一个pair对,但是两个都是迭代器,第一个指向与键值匹配的第一个元素的位置,
第二个指向最后一个与键匹配的元素的位置。



4 种无序关联式容器 unordered_map,unordered_set,unorder_multiset,unordered_multimap.
根据字面意思便可以知道容器的区别:
unordered------无序
multi-------------可重复

unordered_map 容器 所谓“无序”,指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说,unordered_map 容器和 map 容器仅有一点不同,即 map 容器中存储的数据是有序的,而 unordered_map 容器中是无序的。
底层:
unordered_map 容器底层采用的是哈希表存储结构,该结构本身不具有对数据的排序功能,所以此容器内部不会自行对存储的键值对进行排序。
头文件---
map和unordered_map的比较:

map
优点:map内部实现是红黑树,有序性是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作,其复杂度为logN。
缺点:空间占用率高,因为每一个节点都需要额外保存父节点,孩子节点以及红/黑性质,使得每一个节点都占用大量的空间。
适用处:对于那些有顺序要求的问题,用map会更高效一些。
unordered_map
优点: 内部实现是哈希表,因此其查找速度非常的快,复杂度为O(1)。
缺点: 更改哈希表的大小,重构哈希表比较耗费时间。
适用处:对于查找问题,unordered_map会更加高效一些。
使用时map的key需要定义operator<。unordered_map要求传入的数据能够进行大小比较,“==”关系比较;所以自定义数据需要定置hash_value仿函数同时重载operator==。

简单记忆:除了无序和底层,其他的和map一样。
unordered_map 容器迭代器
unordered_map 容器迭代器的类型为前向迭代器(又称正向迭代器)。这意味着,假设 p 是一个前向迭代器,则其只能进行 *p、p++、++p 操作,且 2 个前向迭代器之间只能用 == 和 != 运算符做比较。

容器的一些特性 序列式 list
没有下标访问方式

关联式 stack
queue
1,这两个容器都是以其他容器作为底层实现原理,都是对替他容器的修改。
它们被称为容器配接器(container adapter),因为配接器具有修改其他容器接口功能的作用。
2,两个都是默认以双端队列deque作为底层容器,当然也可以选择其他容器作为底层容器。
3,由于它们的特性,不允许对他们进行遍历,这两个容器也没有迭代器。
4,特殊函数
特性 函数
stack 先进后出 top():获取栈顶元素,但是不删除
push(T a):压入栈顶,无返回值
pop():删除栈顶元素,无返回值
queue 先进先出 front():获取对头元素
back():获取队尾原素
push(T a):压入队尾
pop():出队(删除对头元素)
内部实现:
stack:
STL(标准模板库)
文章图片

queue:
STL(标准模板库)
文章图片


#include #include #include #include #include using namespace std; int main() { //如果不以默认deque为底层容器,则要给出第二个模板参数 stack> inst; //测试主要函数 for (int i = 0; i < 10; ++i) { inst.push(i); } cout << "stack:" << "top->" << inst.top() << " "; inst.pop(); cout<< "top->" << inst.top() << endl; //使用默认底层容器 queue q_inst; for (int i = 0; i < 10; ++i) { q_inst.push(i); } //函数 cout<<"queue:" <<"front->" << q_inst.front() << " "<<"back->"<" << q_inst.front() << " " << "back->" << q_inst.back() << " "; }

hash系列容器

    推荐阅读