概念：
STL：标准模板库，是C++标准库的重要组成部分，STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，注意，这里提到的容器，本质上就是封装有数据结构的模板类，例如 list、vector、set、map 等，
由概念便可以知道，STL中的所有数据结构都是以模板的方式创建的
容器(数据结构)，算法（算法），迭代器(算法访问容器元素的工具)，
C++ STL 一共提供了六大组件，包括 容器，算法，迭代器，仿函数，配接器和配置器 ，彼此可以组合套用。
容器通过配置器取得数据存储空间；
算法通过迭代器存取容器内容；
仿函数可以协助算法完成不同的策略变化；
配接器可以应用于容器、仿函数和迭代器。
- 容器：包括各种数据结构，如vector，queue， deque,，set， map，用来存放数据，分为序列式容器和关联式容器，实现的角度来讲是一种类模板。
容器可分为：序列式容器，关联式容器
序列式：容器中的元素有顺序关系
关联式：容器中的元素不要求有顺序关系
2、算法：各种常用的算法，问题的解法，如sort (插入，快排，堆排序)， search (二分查找），从实现的角度来讲是一种方法模板。
3、迭代器：从实现的角度来看，迭代器是一种将 operator，operator->，operator++，operator-等指针相关操作赋予重载的类模板，所有的 STL 容器都有自己的迭代器。是容器和算法的粘合剂，算法要通过迭代器才可以访问容器中的元素，迭代器会通过自己的方法找到容器中的元素，
4、仿函数：从实现的角度看，仿函数是一种重载了 operator() 的类或者类模板。可以帮助算法实现不同的策略。
5、配接器：一种用来修饰容器或者仿函数或迭代器接口(参数)的东西。
6、配置器：负责空间配置与管理，从实现的角度讲，配置器是一个实现了动态空间配置、空间管理,空间释放的类模板。
vector(向量)
怎么使用：
- 包含头文件vector和命名空间std
vector 容器以类模板 vector<T>（ T 表示存储元素的类型）的形式定义在 <vector> 头文件中，并位于 std 命名空间中。
- 五种创建容器方法：
(1)先创建空容器，再添加容器容量和元素
(2)创建的同时初始化容器元素
vector<T> v5{a,b,c…}
vector<T> v5={a,b,c…}
- 创建的同时指定容器容量，不给出容器元素
vector<T> v4[n] []永远代表个数
说明：包含n个重复执行了值初始化的对象（即值为0）
- 创建的同时指定容器容量和重复元素
vector<int> myv(n)和vector<int>myv[n];
vector<int>myv[n]是vector<int>类型的数组。
vector<int>myv(n)是建立一个vector<int>类型的类对象(容器)，在这个类对象中初始化10个int类型的数据空间。
注意，注意，注意：
所有容器的类型，比如vector<int> 仅仅表示变量的中存储的元素的类型。
vector<int> myv; //myv中存放vector<int>容器
vector<vector<int>> myv; //容器中存放vector<vector<int>>类型容器。
vector<int> myv和vector<int> myv[n]的区别
一个是变量，一个是数组。
vector类型的变量才具有vector的函数。
数组中的元素才是vector类型的变量，才具有vector的函数。
理解这些一定要记住：
容器的本质——类
要注意：建立的是一个类对象还是一个保存类对象的数组。
变量或者数组中保存的是一个个的类
vector的下标访问
vector中重载了[ ],所以也可以用下标访问vector容器的元素。
vector<T> v3(n,val)
说明：包含n个重复的val元素
(5)通过存储元素类型相同的其它 vector 容器，也可以创建
的 vector 容器，例如：
vector<T> v1
vector<T> v2(v1) （）永远代表复制
vector<T> v2 = v1
如果不想复制其它容器中所有的元素，可以用一对指针或者迭代器来指定初始值的范围，例如：
纯文本复制
- int array[]={
1,2,3}; - std::vector<int>values(array, array+2);//values 将保存{1,2}
- std::vector<int>value1{
1,2,3,4,5}; - std::vector<int>value2(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() 结合使用。 |
|
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()分两种
一种是头文件<algorithm>中定义的三个函数的find(),一种是容器内部定义的以指定数值为参数的find().
三个参数的find也可以用来查找容器中的数据，但是效率不高，所以最好使用容器内部定义的find.
如果元素存在，返回元素迭代器，不存在返回end()的迭代器。
find(ite.begin(),ite.end(),要寻找的参数)
指定一段寻找的区间，去寻找某一个元素。
find(值)
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> inst={1,23,4,4};
if(find(inst.begin(),inst.end(),23)!=inst.end())
cout<<"23"<<endl;
return 0;
}
注意头文件：algorithm
注意：序列式容器都没有定义内部的find函数，所以要用algorithm头文件中的find
push和emplace两类函数的区别
push_front(T)
注意：vector没有这个函数
push_back(T)
insert(p,x),insert(p,n,x)
链接
emplace(P,T)
#include <iostream>
#include <vector>
using namespace std;
class testDemo {
public:
testDemo(int n) :num(n) {
cout << "构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
cout << "拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
cout << "移动拷贝构造函数" << endl;
}
testDemo& operator=(const testDemo& other);
private:
int num;
};
/*
为什么一定要重载这个函数：
1，自定义类型，这个函数不是默认生成的；
2，emplace和insert内部实现需要这个函数
*/
testDemo& testDemo::operator=(const testDemo& other) {
this->num = other.num;
cout << "重载"<<endl;
return *this;
}
int main() {
vector<testDemo> vec{};
cout << "emplace:" << endl;
vec.emplace(vec.begin(), 2);
cout << "insert:" << endl;
vec.insert(vec.begin(), 2);
return 0;
}emlace_front(T)
emplace_back(T)
区别：
push类函数需要先调用构造函数构造一个临时的对象，然后再在容器的尾部通过调用移动拷贝构造函数(如果没有就调用拷贝构造函数)拷贝这个临时对象加入容器。
而emplace类函数是直接在容器尾部调用对象的构造函数直接构造对象，不需要生成临时对象，不需要拷贝。
链接
vector的容量
vector对象刚建立，没赋值时，size=capacity=0;.
vector容器扩张原则：len = size()!=0?2*size():1;
如果原来的容器的大小不为0，扩展两倍的容量，扩展之后赋值元素到新地址，释放就地址。
vector什么时候会进行扩容
看源码可知：当push_back()时，判断要插入的位置已经是最后一个可用位置的的时候就会进行扩容。
vector以及其他容器扩容的集中情况
push_back,insert,emplace都会自动扩容，即使刚开始没有容量。
但是注意一种情况：不能利用[ ]插入值的形式给容器扩容，对于一个还没有建立任何空间的容器对象，不能企图用[ ]为期插入数据，否则就是段错误，因为这个对象虽然有了地址，但是其存储数据的地址没有分配，系统不知道要存放在哪。
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vec;
cout<<"push_back:"<<endl;
cout<<"capacity="<<vec.capacity()<<endl;
vec.push_back(10);
cout<<vec[0]<<endl;
cout<<"capacity="<<vec.capacity()<<endl;
cout<<endl;
vector<int> vec1;
cout<<"insert:"<<endl;
cout<<"capacity="<<vec1.capacity()<<endl;
//vec1.insert(vec1.begin(),1);
vec1.insert(vec1.begin(),3,1);
cout<<vec1[0]<<endl;
cout<<"capacity="<<vec1.capacity()<<endl;
cout<<endl;
vector<int> vec2;
cout<<"capacity="<<vec2.capacity()<<endl;
vec2.emplace(vec2.begin(),2);
//vec2.emplace(vec2.begin(),3,2);
cout<<vec2[0]<<endl;
cout<<"capacity="<<vec2.capacity()<<endl;
cout<<endl;
//以下代码会出现段错误，一位不能开辟内存，企图访问一个不存在的内存。
vector<int> vec3;
cout<<"[]"<<endl;
cout<<"capacity="<<vec3.capacity()<<endl;
vec3[0]=3;
cout<<vec3[0]<<endl;
cout<<"capacity="<<vec3.capacity()<<endl;
cout<<endl;
return 0;
}
但是只要给其分配了内存，那么用[ ]来给其分配超出其容量范围的位置的插入元素，容量不变，但是可以插入，虽然可以实现，但是很危险，因为超出容器容量的范围的元素是不包含在这个容器中的。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> vec(5);
int i=0;
cout<<"capactiy="<<vec.capacity()<<endl;
for(;i<5;++i)
vec[i]=i;
cout<<"capactiy="<<vec.capacity()<<endl;
for(;i<5;++i)
vec[i]=i;
cout<<"capactiy="<<vec.capacity()<<endl;
return 0;
}
结果：
容器容量不变，但是可以向超出容量范围的地址插入数据
[ ]的访问原则
访问容器或者数组本身分配所得的内存内的数据，这样才是安全的
不要担心容器开辟的内存不够而无法存入，内存不够会自动开辟。
resize()增加容器元素个数才可以增加容器元素，reserve()增加容器容量，不可以增加容器元素
仅通过 reserve() 成员函数增加 value 容器的容量，其大小并没有改变；但通过 resize() 成员函数改变 value 容器的大小，它的容量可能会发生改变。另外需要注意的是，通过 resize() 成员函数减少容器的大小（多余的元素会直接被删除），不会影响容器的容量。
圆括号 () 和大括号 {} 是有区别的，前者（vector<int>v(20) ）表示元素的个数，而后者（vector<int>v{20} ） 则表示 vector 容器中只有一个元素 20。
我们可能需要将容器的容量和大小保存在变量中，要知道 vector<T> 对象的容量和大小类型都是 vector<T>::size_type 类型。因此，当定义一个变量去保存这些值时，可以如下所示：
- vector<int>::size_type cap = value.capacity();
- vector<int>::size_type size = value.size();
size_type 类型是定义在由 vector 类模板生成的 vecotr 类中的，它表示的真实类型和操作系统有关，在 32 位架构下普遍表示的是 unsigned int 类型，而在 64 位架构下普通表示 unsigned long 类型。
迭代器的使用：
什么是迭代器：
迭代器就是地址
迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。
注意迭代器不是引用，可以用迭代器作实参传递去改变容器内容，但是形参不要定义为引用，直接定义为：
template<typename I>
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<>容器的容量是可以变的，即动态的。
vector<int>v2(v1.begin(),v1.end());
将v1中所有的数据复制到v2中
同样功能可以用：
vector<int>v2;
v2.assign(v1.begin(),v1.end());
怎么访问vector容器中的元素：
- v.at(n)返回容器位置为n的元素的引用（注意第一个位置为0）
- vector容器也是数组，可以用v[n]访问
所谓泛型编程就是模板编程，泛型就是广泛可以使用的类型，即模板
五类主要的序列容器：
vector,array,list,deque,forward_list
vector实现二位存储
vector<vector<int>>
依照这个原理，可以产生多维存储……….
vector也可以通过多级下标访问元素—myv[i][j]
vector的拼接
1，insert—无需排序
insert既可以用来插入元素，也可以用来拼接
#include <iostream>
#include <vector>
using namespace std;
void printVec(vector<int>& vec){
for(int i=0;i<vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
}
int main(){
vector<int> vec1={1,1,1,1,1},vec2={2,2,2,2,2,2};
vec2.insert(vec2.end(),vec1.begin(),vec1.end());
printVec(vec2);
return 0;
}
2，merge–需要排序
虽然不排序也可以运行成功，但是顺序乱了
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVec(vector<int>& vec){
for(int i=0;i<vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
}
int main(){
vector<int> vec1={1,3,5,7},vec2={2,8,6,4};
vector<int> vec3;
vec3.resize(vec1.size()+vec2.size());
sort(vec2.begin(),vec2.end());
merge(vec1.begin(),vec1.end(),vec2.begin(),vec2.end(),vec3.begin());
printVec(vec3);
return 0;
}
merge默认升序排列
2，如果合并使用的多，直接重载+
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printVec(vector<int>& vec){
for(int i=0;i<vec.size();++i)
cout<<vec[i]<<" ";
cout<<endl;
}
template<typename T>
vector<T> operator+(vector<T>& v1,vector<T>& v2){
v1.insert(v1.end(),v2.begin(),v2.end());
return v1;
}
int main(){
vector<int> vec1={1,3,5,7},vec2={8,6,4,2};
vec1=vec1+vec2;
printVec(vec1);
return 0;
}
array
本质
模板结构体
template <typename T, size_t N>
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<iterator>;
using const_reverse_iterator = std::reverse_iterator<const_iterator>;
typedef __array_traits<T, N> AT_Type;
typename AT_Type::Type M_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容器的建立：
array容器的建立一定要给出存储的数据类型和容器的大小
1，array<double, 10> values;
由此，就创建好了一个名为 values 的 array 容器，其包含 10 个浮点型元素。但是，由于未显式指定这 10 个元素的值，因此使用这种方式创建的容器中，各个元素的值是不确定的，并不一定就是0（array 容器不会做默认初始化操作）
#include "iostream"
#include <array>
using namespace std;
void insert(array<int,20>& arr)
{
for(int i=0;i<10;i++)
{
scanf("%d",&arr[i]);
}
}
void display(array<int,20>& arr)
{
for(int i=0;i<arr.size();i++)
{
printf("%d ",arr.at(i));
}
cout<<endl;
}
int main()
{
array<int,20>arr;
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，array<double,10>values{};
将所有的元素初始化为 0(注意：不是为空，而是0) 或者和默认元素类型等效的值：
3,当然，在创建 array 容器的实例时，也可以像创建常规数组那样对元素进行初始化：array<double, 10> 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++ 标准数组访问元素的方式相同，例如：
- values[4] = values[3] + 2.O*values[1];
此行代码中，第 5 个元素的值被赋值为右边表达式的值。需要注意的是，使用如上这样方式，由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到。(越界无检索)
越界的是一个随机值
#include <iostream>
#include <array>
int main(){
std::array<int,2> arr{1,2};
std::cout<<arr[3]<<std::endl;
return 0;
}
为了能够有效地避免越界访问的情况，可以使用 array 容器提供的 at() 成员函数，例如 :
2，values.at (4) = values.at(3) + 2.O*values.at(1);
这行代码和前一行语句实现的功能相同，其次当传给 at() 的索引是一个越界值时，程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时，建议大家使用 at()，除非确定索引没有越界。（越界可检索）
3，array 容器提供了 data() 成员函数，通过调用该函数可以得到指向容器首个元素的指针
4，在 <array> 头文件中还重载了 get() 全局函数，该重载函数的功能是访问容器中指定的元素，并返回该元素的引用。需要注意的是，该模板函数中，参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。
重载函数get()：
形式：get<n>(name)
n为指定容器元素，name为容器名称
array和vector的比较
| 空间 | 模板参数 | ||
| vector | 动态空间： 本质上也是静态空间，只是vector内部机制会自动进行内存的重新配置，移动数据，释放旧空间。 随着元素的加入，内部空间会自动拓展空间来容纳新元素 空间拓展方式：自动拓展 |
2个，但是建立容器时只需要一个参数 | |
| array |
静态空间： 内存空间的大小固定，如果所需内存超出固定内存，需要重新配置，移动数据，释放旧空间。 空间拓展方式：程序员手动拓展 |
2个，建立容器也要两个 |
LIST：
本质是环状双向链表
源码属性：
模板类
list节点：
list节点实质是一个模板结构体
template<class T>
struct _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的迭代器不指向结点中的数据，也不指向结点，那么迭代器如果对结点和结点中的元素进行操作：
迭代器中定义一个结点类型的变量，用来记录结点，以及对链表的结点进行操作
源码：
在list模板类中将以上类声明为：iterator（迭代器）
list的迭代器不是指向结点，也不是指向结点中的元素，但是同样的。所用的迭代器解引用都是容器的元素，而list是利用的对解引用符的重载函数输出
list–container:
list容器是一个模板类
list的所有的函数，迭代器都是这个模板类的成员
list容器的优点：
1，很方便的向容器中插入节点，添加数据值
2，方便删除节点，和数据值，而不会影响其他的节点和数据
3，链表的建立：只需要不断插入数据就可以快速建立链表
list容器的缺点：
1，不方便访问节点数据值
list容器的使用场景：
需要不断添加，删除，改动元素
list container的成员函数：
1，begin()
2，end()
3，void push_back(const T& x)
功能：插入一个节点作为尾节点
实现原理：
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<T,Alloc>::clear()
清除所有节点（删除整个链表）
9，void list<T,Alloc>::remove(const T& x)
清除数值为x的所有节点
10，void list<T,Alloc>:: unique()
清除数值相同的连续节点，保留一个
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() | 反转容器中元素的顺序。 |
list容器的排序
list不能使用标准库函数sort，需要使用自己的sort函数。
list的函数默认升序排序，而且不可以设置降序。
设置降序可以先sort升序排序，再利用list的reverse函数反转链表即可。
list怎么插入元素
list<int> lt1={1,2,10,3};
list<int> lt2={11,22,33};
//在lt1的10之后插入lt2的元素
auto ite=find(lt1.begin(),lt1.end(),10);
lt1.splice(ite,lt2);各容器之间的比较
| 源码本质 | 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 类模板定义在<utility>头文件中
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，拷贝：利用赋值构造函数：map<int,string>ffmap(fmap);
3，截取：
map 类模板还支持取已建 map 容器中指定区域内的键值对，创建并初始化新的 map 容器。例如：
- std::map<std::string, int>myMap{ {“C语言教程”,10},{“STL教程”,20} };
- std::map<std::string, int>newMap(++myMap.begin(), myMap.end());
这种方法注意end()的选择，如果要选择到最后，不要–mymap.end();
4，下标赋值。
map<int,string>mymap{
{0,"fangfang"},{1,"xiaoli"}};
auto ite=mymap.find(1);
cout<<(*ite).second<<endl;
cout<<ite->first<<" "<<ite->second<<endl;
map<int,string> fmap;
fmap[0]="aaaa";
fmap[1]="bbbb";
fmap[2]="cccc";
int i=0;
for(i;i<fmap.size();i++)
{
cout<<fmap[i]<<" ";
}
cout<<endl;
map<int,string>ffmap(fmap);
for(i=0;i<ffmap.size();i++)
{
cout<<ffmap[i]<<" ";
}
cout<<endl;
map容器不能像vector一样从数组中获取值。
5,insert插入法：
insert可以先建立pair键值对再插入，也可以插入临时值(右值引用插入)：
int main()
{
map<string,string>mymap;
pair<map<string,string>::iterator,bool> ret=mymap.insert({"China","Beijing"});
cout<<ret.first->first<<"---"<<ret.first->second<<endl;
pair<string,string> add={"Americ","Niuyake"};
ret=mymap.insert(add);
cout<<ret.first->first<<"---"<<ret.first->second<<endl;
return 0;
}
~ 注意：
（1，pair键值对的定义，
（2，insert返回类型以及如何定义返回类型变量。
（3，insert还可以同时插入多个键值对。
关于Insert更多看——-连接
6，两个效率更高的插入方法：
1》
template <class… Args>
pair<iterator,bool> emplace (Args&&… args);
- 当该方法将键值对成功插入到 map 容器中时，其返回的迭代器指向该新插入的键值对，同时 bool 变量的值为 true；
- 当插入失败时，则表明 map 容器中存在具有相同键的键值对，此时返回的迭代器指向此具有相同键的键值对，同时 bool 变量的值为 false。
- 返回类型同insert
2》
template <class… Args>
iterator emplace_hint (const_iterator position, Args&&… args);
- 该方法不仅要传入创建键值对所需要的数据，还需要传入一个迭代器作为第一个参数，指明要插入的位置（新键值对键会插入到该迭代器指向的键值对的前面）；
- 该方法的返回值是一个迭代器，而不再是 pair 对象。当成功插入新键值对时，返回的迭代器指向新插入的键值对；反之，如果插入失败，则表明 map 容器中存有相同键的键值对，返回的迭代器就指向这个键值对。
3. 成功，返回一个指向键值对的迭代器。
int main()
{
map<string,int>mymap;
pair<map<string,int>::iterator,bool> ret=mymap.emplace("China",1);
cout<<ret.first->first<<" "<<ret.first->second<<endl;
map<string,int>::iterator ite=mymap.emplace_hint(mymap.end(),"Americ",2);
cout<<ite->first<<" "<<ite->second<<endl;
return 0;
}
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查找：
map的一些操作
1，删除值
2，对map进行排序
首先一定要注意map模板类的第三个模板参数，这个参数决定元素按键值升序或者降序在map中的存储方式：
默认：less<key>升序
可设置：greater<key>降序
也可以自己定义键值比较函数，用函数名作为第三个参数
这个参数默认map 中的元素是以键值key递增存储的。
如果需要递减存储就设置第三个参数未greater<key>。
注意，key是你设置的数据的类型。
以上是初始建立map对象时设置的，如果运用过程中想要修改map容器的元素的存储顺序，怎么办：
自定义键值比较函数
详细链接
map中当key是结构体或者类时，需要重载哪些函数
看链接可知：函数对象中实现对函数调用符–小括号的重载。而map传递过去用于比较的是map的键，但是如果键是结构体或者类，那么结果或者类是比较不了的，所以这个时候需要我们自己重定义这个函数对象，重载（）的时候，不是比较结构体或者类，而是比较结构体或者类中的某一个元素。
map实现按值排列存储—实现pair对存储数据
map实现不了按值存储，即使你实现了pair对按序插入，也不会按序在map中存储。我们只能将map中的pair对存储在vector中，让后自定义排序函数对pair对进行排序。
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<string, int> PAIR;
bool cmp_by_value(const PAIR& lhs, const PAIR& rhs) {
return lhs.second < rhs.second;
}
struct CmpByValue {
bool operator()(const PAIR& lhs, const PAIR& rhs) {
return lhs.second < rhs.second;
}
};
int main() {
map<string, int> name_score_map;
name_score_map["LiMin"] = 90;
name_score_map["ZiLinMi"] = 79;
name_score_map["BoB"] = 92;
name_score_map.insert(make_pair("Bing",99));
name_score_map.insert(make_pair("Albert",86));
//把map中元素转存到vector中
vector<PAIR> name_score_vec(name_score_map.begin(), name_score_map.end());
sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
// sort(name_score_vec.begin(), name_score_vec.end(), cmp_by_value);
for (int i = 0; i != name_score_vec.size(); ++i){
cout<<name_score_vec[i].first<<name_score_vec[i].second<<endl;
}
return 0;
}
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函数
| 成员方法 | 功能 |
|---|---|
| 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 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。
头文件—<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:
queue:
queue对头和队尾元素获取
注意queue的back()和front()函数，它底部是使用vector或者deque这些容器的，也是直接调用这些容器的back和front，queue中back字面意思应该是从对头出来的，也就是最先放入的元素，但是底部容器中back是容器最后一个元素，也就刚刚放入的元素，front也是同理
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
using namespace std;
int main()
{
//如果不以默认deque<T>为底层容器，则要给出第二个模板参数
stack<int, list<int>> inst;
//测试主要函数
for (int i = 0; i < 10; ++i)
{
inst.push(i);
}
cout << "stack:" << "top->" << inst.top() << " ";
inst.pop();
cout<< "top->" << inst.top() << endl;
//使用默认底层容器
queue<int> q_inst;
for (int i = 0; i < 10; ++i)
{
q_inst.push(i);
}
//函数
cout<<"queue:" <<"front->" << q_inst.front() << " "<<"back->"<<q_inst.back()<<" ";
q_inst.pop();
cout << "queue:" << "front->" << q_inst.front() << " " << "back->" << q_inst.back() << " ";
}hash系列容器
hash值函数
链接
hash<K> 实例的成员函数 operator()() 接受 K 类型的单个参数，然后返回 size_t 类型的哈希值。
使用方法：建立hash<K>对象之后，hash对象调用(),在()中传参就可以计算出哈希值。
头文件：
一般类型：
1，#include <functional>
2,string类型数据：#include <string>
3,自定义类型—一般还是计算自定义类型中的基本数据类型的hash值再稍微变换一下就是自定义类型的哈希值
详情链接
例子：
1,int:
1,建立hash对象
#include <iostream>
//#include <string>
#include <functional>
#include <vector>
using namespace std;
int main() {
hash<int> hash_int;
vector<int> vec = {1,2,4,5,6,7};
for (auto& i : vec) {
cout << hash_int(i) << endl;
}
return 0;
}
2，不建立hash对象--{}，一下类型不再列出
#include <iostream>
//#include <string>
#include <functional>
#include <vector>
using namespace std;
int main() {
//hash<string> hash_str;
vector<int> vec = {1,3,4,7,8,9};
for (auto& i : vec) {
cout << hash<int>{}(i) << endl;
}
return 0;
}
3，不建立hash对象--()，一下类型不再列出
#include <iostream>
//#include <string>
#include <functional>
#include <vector>
using namespace std;
int main() {
//hash<string> hash_str;
vector<int> vec = {1,3,4,7,8,9};
for (auto& i : vec) {
cout << hash<int>()(i) << endl;
}
return 0;
}2,char
#include <iostream>
//#include <string>
#include <functional>
#include <vector>
using namespace std;
int main() {
hash<char> hash_char;
vector<char> vec = {'a','b','c','d','e','f'};
for (auto& i : vec) {
cout << hash_char(i) << endl;
}
return 0;
}3,double
#include <iostream>
//#include <string>
#include <functional>
#include <vector>
using namespace std;
int main() {
hash<double> hash_dou;
vector<double> vec = {1.2,3.2,4.55,6.24};
for (auto& i : vec) {
cout << hash_dou(i) << endl;
}
return 0;
}4,string
#include <iostream>
#include <string>
//#include <functional>
#include <vector>
using namespace std;
int main() {
hash<string> hash_str;
vector<string> vec = {"I","am","a","cute","baby"};
for (auto& i : vec) {
cout << hash_str(i) << endl;
}
return 0;
}#include <iostream>
#include <string>
//#include <functional>
#include <vector>
using namespace std;
int main() {
//hash<string> hash_str;
vector<string> vec = {"I","am","a","cute","baby"};
for (auto& i : vec) {
cout << hash<string>{}(i) << endl;
}
return 0;
}堆和优先队列
C++默认的优先队列是大顶堆，如果需要指定为小顶堆，可以指定第三个模板参数。
如果存储的数据类是特殊数据类型，如结构体，类等，需要自定义函数对象。
但是注意比较参数是第三个，第二个参数也要写，而且第二个参数是vector<第一个参数类型>。
详细链接
默认大顶堆
//大顶堆
vector<int> vec = {1,2,3,4,5,6,7,8,9};
priority_queue<int> pq(vec.begin(),vec.end());
cout<<pq.top()<<endl;
//小顶堆
vector<int> vec = {1,2,3,4,5,6,7,8,9};
priority_queue<int, vector<int>, greater<int>> pq(vec.begin(),vec.end());
cout<<pq.top()<<endl;
//存储结构体结点，自定义函数对象
struct node {
int val;
node* next;
node(int v) :val(v) {
next = nullptr;
}
};
struct cmp {
bool operator()(node* n1,node* n2) {
return n1->val > n2->val;//>--小顶堆，<--大顶堆《>小顶堆，<大顶堆》
}
};
int main() {
vector<int> vec = {1,2,3,4,5,6,7,8,9};
priority_queue<node*, vector<node*>, cmp> pq;
for (int i = 0; i < 9; ++i) {
pq.push(new node(vec[i]));
}
cout<<pq.top()->val<<endl;
return 0;
}一些特别的函数
find
find()分两种
一种是头文件<algorithm>中定义的三个函数的find(),一种是容器内部定义的以指定数值为参数的find().
三个参数的find也可以用来查找容器中的数据，但是效率不高，所以最好使用容器内部定义的find.
如果元素存在，返回元素迭代器，不存在返回end()的迭代器。
find(ite.begin(),ite.end(),要寻找的参数)
指定一段寻找的区间，去寻找某一个元素。
find(值)
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> inst={1,23,4,4};
if(find(inst.begin(),inst.end(),23)!=inst.end())
cout<<"23"<<endl;
return 0;
}
注意头文件：algorithm
注意：序列式容器都没有定义内部的find函数，所以要用algorithm头文件中的find
emplace类的函数
1，如果插入的是对象，就调用对象的构造函数以及传入的参数构建对象再插入容器
//线程的创建
vector<thread> vecThread;
int a = 10, b = 23;
for (int i = 0; i < 5; ++i) {
vecThread.emplace_back(add, a, b);
vecThread[i].join();
}2，不是对象，只需要插入数据，不同于insert—先生成数据再放入指定内存位置，emplace—在指定内存位置直接生这个数据。
STL迭代器失效问题
迭代器失效的原因
因为插入或者删除元素，导致原来内存的数据产生移动，就会导致原有的迭代器失效。
会产生迭代器失效的是使用连续内存存储数据的容器，比如vector，deque，unordered_map，unordered_set；而list，map，set这一类容器使用的不是连续内存，除了被删除的节点的迭代器失效外，其他迭代器不会失效。
vector
map
关于容器存储动态分配内存问题—clear是否释放内存
需要注意的是，如果容器存储的是动态分配的内存，容器中的元素被清空时(clear)，它只会释放容器本身用于管理这些元素的内存(也就是容器自己的内存)，而不会自动释放动态分配的内存(被保存元素的内存)。
因此，如果容器中的元素包含动态分配的内存，需要手动释放这些内存。可以遍历容器中的元素，逐一释放相应的内存。
#include <iostream>
#include <map>
int main(){
std::map<int,int*> t_map;
for(int i=0;i<10;++i){
int *tmp=new int(i);
t_map[i]=tmp;
}
for(auto& pair:t_map){
std::cout<<*(pair.second)<<std::endl;
delete pair.second;
pair.second=nullptr;
}
std::cout<<t_map.size()<<std::endl;
if(t_map[1]==nullptr){
std::cout<<"pointer has delete."<<std::endl;
}
else{
std::cout<<*(t_map[1])<<std::endl;
}
return 0;
}
std::distance–寻找两个迭代器直接的距离，或者某一个元素的下标
链接
distance可以用于关联式容器吗
可以，但是没有实际用处。
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
int main(){
std::vector<int> v{1,2,3,4,5,6,7,8,9};
std::map<int,int> m;
m[0]=0;
m[1]=1;
m[2]=2;
int index=std::distance(v.begin(),find(v.begin(),v.end(),5));
std::cout<<index<<std::endl;
index=std::distance(m.begin(),m.find(2));
std::cout<<index<<std::endl;
return 0;
}
关于erase和clear是否调用元素析构函数的问题
先判断型别再绝对是否执行析构，可见是可以执行析构函数的。
今天的文章stl标准模板库_标准模板规格尺寸分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/74590.html
