STL

参考

https://cplusplus.com/reference/stl/

概念

STL 构成

• 容器 ： 封装数据结构的模板类
• 算法 ：数据结构算法，都是模板函数 <algorithm.h> <numeric.h>
• 迭代器 : 容器中数据的读写；容器与算法之间的桥梁
• 函数对象 : 如何一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（仿函数）
• 适配器 : ???
• 内存分配器 : ???

头文件

<iterator>
<functional>
<vector>
<deque>
<list>
<queue>
<stack>
<set>
<map>
<algorithm>
<numeric>
<memory>
<utility>

模板

• 容器类模板

容器用于存储序列化的数据；向量、队列、栈、集合

• 算法(函数)模板

算法用于对容器中的数据元素进行一些常用操作，排序、统计等

• 迭代器类模板

迭代器实现了抽象的指针功能，指向容器中的数据元素，用于对容器中的数据元素进行遍历和访问
迭代器是容器和算法之间的桥梁：传给算法的不是容器，而是指向容器中元素的迭代器，算法通过迭代器实现对容器中数据元素的访问，这样使得算法与容器保持独立，从而提高算法的通用性

例子概览

例子1

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

void display(int x)
{
    
    cout<<" "<<x;
    return ;
}
int main()
{
    
    vector<int> v; // 创建容器对象 元素类型为int
    int x;
    cin>>x;
    while(x>0)
    {
    
        v.push_back(x);
        cin>>x;
    }

    // 利用算法max_element计算并输出容器v中的最大元素
    cout<<"max= "<<*max_element(v.begin(),v.end())<<endl;
    // 利用算法accumulate 计算并输出容器中v中所有元素的和
    cout<<"sum= "<<accumulate(v.begin(),v.end(),0)<<endl;
    // 利用算法sort对容器v中的元素进行排序
    sort(v.begin(),v.end());
    // 利用算法for_each 输出排序后的结果
    cout<<"sorted result"<<endl;
    for_each(v.begin(),v.end(),display);
    cout<<"\b"<<endl;

    return 0;
}

例子2

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    
    //创建一个
    类容器
    map<string,int> book;

    book["wang"]=1;
    book["zhang"]=2;
    book["li"]=3;

    cout<<"output"<<endl;

    for (pair<string,int> item:book)
    {
    
        cout<<item.first<<": "<<item.second<<endl;
    }

    string name;
    cout<<"输入名字"<<endl;
    cin>>name;

    // 创建一个不能修改所指向的元素的迭代器
    map<string,int>::const_iterator it;
    it=book.find(name); // 查找关键字为zhang的容器元素
    if (it==book.end())
    {
    
        cout<<"not find"<<endl;
    }
    else
    {
    
        cout<<it->first<<": "<<it->second<<endl;
    }

    return 0;
}

容器 - 序列式容器

由类模板实现
同类型元素构成、(部分容器)长度可变

基于STL，部分容器可以根据存储数据的数量自动变长

array<T,N>

不能增加删除元素，只能改变某个元素的值
相当于静态数组

遍历

#include <iostream>
#include <array>

using namespace std;

int main()
{
    
    array<double,10> arr1; // 默认不初始化 采用的是随机值

    array<double,10> arr2 {
    }; // 都被初始化为0.

    array<double,10> arr3 {
    1.,2.}; // 部分初始化，其他为0.

    array<double,10> arr4={
    1.,2.}; // 部分初始化，其他为0.
    
    for (int i=0;i<arr4.size();i++)
    {
    
        arr4.at(i)=i;
    }

    // 使用get()重载函数输出指定位置元素 返回元素的引用
    cout<<get<3>(arr4)<<endl;

    // 如果容器不为空
    if (!arr4.empty())
    {
    
        // for (auto v=arr4.begin();v<arr4.end();v++) // auto让编译器自动判断变量的类型
        for (double* v=arr4.begin();v<arr4.end();v++)
        {
    
            cout<<*v<<endl;
        }
    }

    cout<<"****************"<<endl;

    if (!arr4.empty())
    {
    
        auto first=arr4.rbegin(); // 指向最后一个元素，反向迭代器
        auto last=arr4.rend(); // 指向第一个元素的前一个位置
        int v=0;
        while (first!=last)
        {
    
            // 注意：反向迭代器的++ 是向左移动一位，--是向右移动一位
            *first=v;
            first++;
            v++;
        }

        first=arr4.rbegin();
        for (;first!=last;first++)
        {
    
            cout<<*first<<endl;
        }
    }
    return 0;
}

越界

使用[]索引方式，不能检查是否越界
使用.at()索引方式，能够检查越界性
使用get<n>索引方式，n为常量，能够检查越界性

.data()

.data()返回指向容器首个元素的指针

array<int,5> arr5={
    1,2,3,4,5};
cout<<*(arr5.data()+1); // 2

字符数组/字符串

array<char,20> arr6={
    0};
strcpy(arr6.data(),"hello world"); // strcpy 拷贝自动添加\0

cout<<arr6.data()<<endl;
cout<<&arr6[0]<<endl;

赋值

当两个arr容器满足大小相同，且保存元素的类型相同时，两个array容器可以直接做赋值操作，即将一个容器中的元素赋值给另一个容器

array<char,50> arr7={
    "hello cmd"};
array<char,50> arr8={
    "hello qt"};
arr8=arr7;
cout<<arr7.data()<<endl; // hello cmd
cout<<arr8.data()<<endl; // hello cmd

比较

如果两个array容器满足大小相同，且保存元素的类型相同，且保存的元素支持比较运算符，就可以用任何比较运算符直接比较两个array容器

array<char,50> arr7={
    "hello cmd"};
array<char,50> arr8={
    "hello qt"};
cout<<arr7.data()<<endl; // hello cmd
cout<<arr8.data()<<endl; // hello qt

if (arr7==arr8)
{
    
    cout<<"=="<<endl;
}
if (arr7<arr8)
{
    
    cout<<"<"<<endl; // <
}
if (arr7>arr8)
{
    
    cout<<">"<<endl;
}

vector<>

常用于快速访问、尾部添加/删除元素
动态数组实现
随机访问迭代器

与array不同，vector相当于动态数组
vector会动态调整所占用的内存空间，整个过程无需人工干预
对于容器头部或者中部插入或删除元素，时间复杂度为线性O(n)

对于反向迭代器, ++ 表示左移一位，–表示右移一位

创建

vector<int> values; // 这里创建一个空的vector，此时没有元素，则不为其分配空间，当添加一个元素是，vector会自动分配内存

// 预先分配内存，reserve不会影响已存储的元素，也不会生成任何元素
// 需要注意的是：调用reserve增加容量后，之前创建好的任何迭代器都可能失效，这是因为，为了增加容量，容器的元素可能被复制或移动到了新的内存地址，因此迭代器需要重新生成一下
values.reserve(20) 

values<int> values={
    1,2,3};

values<int> values(20); // 初始20个元素，默认为0
values<int> values(20,2); // 初始20个元素，默认为2

// 拷贝构造函数
vector<char> value1(5,'c');
vector<char> value2(value1);

// 使用指针或迭代器初始部分范围
int arr[]={
    1,2,3};
vector<int> v1(arr,arr+2); // {1,2}
vector<int> v2={
    1,2,3,4,5};
vector<int> v3(begin(v1),begin(v2))

空vector - 注意

由于vector容器可以随着存储元素的增加，自行申请更多的存储空间，因此可以创建一个空的vector容器对象
对于空vector容器，begin(),end()成员函数返回的迭代器是相等的，即指向同一个位置
空vector可以通过push_back或者resize成员函数实现初始化容器的目的
另外，vector容器在申请更多内存时，容器中的所有元素可能会被赋值或移动到新的内存地址，这会导致之前创建的迭代器失效

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    
    vector<int> v={
    1,2,3};

    cout<<v.data()<<endl; // 0x6614d0

    auto first=v.begin();
    auto end=v.end();


    // 扩容
    v.reserve(20);
    cout<<v.data()<<endl; // 0x661510

    first=v.begin();
    end=v.end();

    while(first!=end)
    {
    
        cout<<*first<<endl;
        ++first;
    }

    // 1
    // 2
    // 3

    return 0;
}

访问

[] 访问，越界不会报错，但是会发生不可避免的错误，不能检查是否越界(T *p=&v[index])
.at()，越界会报错
.data() 返回

常用函数

push_back() // 添加元素
reserve() // 增加容器容量 values.reserve(20)

font() // 返回第一个元素的引用 可以进行元素修改 v.font()=10
back() // 返回最后一个元素的引用

emplace_back() // 等价于push_back() 优先选择emplace_back()

insert() // 插入一个元素 返回新的迭代器
emplace() // 等价于insert，但是每次只能插入一个元素

pop_back() // 删除最后一个元素, size减小，capacity不变
erase() // 删除指定位置元素，返回一个迭代器，size减小，capacity不变
remove() // 删除所有元素，size不变，capacity不变
clear() // 删除所有元素，size=0，capacity不变

strink_to_fit() // 将容量缩减至实际存储单元size的个数

例子

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    
    vector<char> v;

    v.push_back('s');
    v.push_back('t');
    v.push_back('l');
    v.push_back('\0');

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

    for (auto i=v.begin();i<v.end();i++)
    {
    
        cout<<*i<<endl;
    }

    v.insert(v.begin(),'c');
    cout<<v.data()<<endl;

    return 0;
}
/*
    size: 4
    s
    t
    l

    cstl
*/

capacity/size/resize

capacity：指的是在不分配更多内存的情况下，容器可以保存的最多元素格式
size: 实际所包含的元素个数
注意： array 没有capacity 只有size函数

capacity和size返回的类型是vector::size_type，size_type类型是定义在vetcor类木本生成的vector类中的，其表示的真是类型和操作系统有关，usigned int或unsigned long

vector<T>::size_type cap=v.capacity();
vector<T>::size_type size=v.size();

注意：容器只要增加一个元素，就必须分配更多（不止1个）的元素，这里具体会多申请多少个内存空间，取决于底层算法实现（这样做的好处是：可以很大程度上减少vector申请空间的次数，当后序再添加元素时，就可以节省申请空间耗费的时间）

对于resize 增大可能改变容量，减小不改变容量

vector<int> v={
    1,2,3};

cout<<v.capacity()<<endl; // 3
cout<<v.size()<<endl; // 3

v.push_back(4);
cout<<v.capacity()<<endl; //6
cout<<v.size()<<endl; // 4

cout<<"**********"<<endl;
// end 不是指向capacity的最后一个+1
// end 指向的是实际元素的最后一个+1
for (auto first=v.begin();first<v.end();first++)
{
    
    cout<<*first<<endl; // 1 2 3 4
}

cout<<"**********"<<endl;
v.resize(2);
cout<<v.capacity()<<endl; //6
cout<<v.size()<<endl; // 2

v.resize(10);
cout<<v.capacity()<<endl; // 10
cout<<v.size()<<endl; // 10

vector底层机制 – 没细看

见文档

vector是一个类模板，创建的对象是类对象，因此与普通自定义的类对象相似，

在C++中，vector是一个类模板，用于动态数组的实现，它的内部实现是使用指针来管理动态分配的内存，因此vector对象本身在栈上分配，而真正存储数据的内存在堆上分配
当创建一个vector对象时，他会在栈上分配一点内存来存储该对象（注意，只是对象，并不是包含的内存），当使用push_back等方法向vetcor中添加元素时，vector会在堆上分配一块新的内存来存储新元素，如果当内存不足时，vector会自动分配更大的内存空间，并将旧内存中的数据复制到新的内存中，因此vector的内存管理是由它自己完成的，无需手动管理内存

虽然vector对象在创建时是在栈区创建二代，但是所管理的元素是在堆区创建的，因此在函数之间传递vector是，实际上是利用类的拷贝构造函数或移动构造函数，创建的一个在栈区的副本，而非vector对象管理的元素，不同函数之间的vector对象副本共享相同的堆内存块 ，因此二者可以访问相同的元素（具体来说，就是当返回返回一个对象时，编译器会创建这个对象的一个副本，并将副本传递个函数调用者，对于类类型对象，这样的副本使用过拷贝构造函数或移动构造函数创建的，且拷贝构造函数或移动构造函数会赋值或移动vetcor中管理的元素）
注意：在返回一个局部vector对象之后，该局部对象将会被销毁，因此函数调用者只能使用副本对象，不能保留或修改原始对象（相当于值赋值）

vector 与指针

vector<int> nums={
    1,2,3,4,5};
int *ptr=&nums[0]; // 指向第一个元素的指针
cout<<*ptr<<endl; // 访问第一个元素
*ptr=10; // 修改vector中的元素

vector 与堆内存

// 在堆上创建vector对象
std::vector<int> *func()
{
    
	std::vector<int>* vec=new std::vector<int>();
	vec->push_back(1);
	vec->push_back(2);
	vec->push_back(3);

	return vec;
}

std::vector<int> *vecPtr=func();

delete vecPtr;
vecPtr=nullptr;

vector/自定义类型

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct prut{
    
    string MC;
    double DJ;
    int SL;
};
int main() {
    
    int N;
    cin >> N;
    double sum = 0.0;
    vector<prut> a(N);//<---看-这-里--- a为prut类型的vector，包含N个元素
    for(int i = 0; i < N; i++) {
    
        cin >> a[i].MC >> a[i].DJ >> a[i].SL;
        sum += a[i].DJ * a[i].SL;
    }
    printf("%lf", sum);
    return 0;
}

vector < bool >

vector 存储的不是bool类型，其并不是一个容器
值得注意的是，vector在存储bool类型值时，每个bool值都只使用一个bit位来存储，也就是说vector底层，一个字节可以存储8个bool尅性值，如果使用operator[]就会返回一个单bit的引用，显然这样是不存在的

尽量避免使用vector
应该用deque(deque可以正常存储bool类型)或bitset（不是容器，不支持迭代器）来代替vector

list<>

常用于任意位置插入/删除元素
双向链表实现（第一个元素的前向指针总为NULL,最后一个元素的后向指针总为NULL）
双向迭代器

list容器的元素可以分散存储在内部才能空间中，不是必须存储在一块连续的内存空间中

创建

list<int> l;

list<int> l(10); // 默认10个0元素

list<int> l(10,5); // 10个5

list<int> l2(l); // 拷贝构造，必须前后存储的元素类型一致

int a[]={
    1,2,3};
list<int> l(a,a+2); // 普通构造

array<int> a2={
    1,2,3};
list<int> l(a2.begin(),a2.begin()+2);

访问

不支持位置索引访问,也就是不支持[]方法
不支持at()方式
不支持data()方式

常用函数

虽然插入不会影响之前的迭代器，但是可能会遗漏新插入的元素
不支持data()方式

insert // 不会造成原有List迭代器失效
splice // 接合操作，不会造成原有List迭代器失效

front() // 返回第一个元素的引用
back() // 返回最后一个元素的引用

push_front
push_back
pop_front
pop_back
emplace_front
emplace_back
emplace
insert
splice
erase
clear
remove
unique() // 删除容器中相邻的重复元素，只保留一份
remove_if() // 删除容器中满足条件的元素

例子

#include <iostream>
#include <list>

using namespace std;

int main()
{
    
    list<int> l;

    l.push_back(1);
    l.push_back(2);
    l.push_back(3);

    l.push_front(10); // 头部添加元素

    cout<<l.size()<<endl; // 4 

    l.sort(); // 排序

    // 注意这里是双向迭代器，不能使用first<enl这样操作
    for (list<int>::iterator first=l.begin();first!=l.end();first++)
    {
    
        cout<<*first<<endl; // 1 2 3 10
    }

    int &v_first=l.front();
    int &v_last=l.back();
    cout<<v_first<<" "<<v_last<<endl; // 1 10

    v_first=11;
    v_last=12;

    for (list<int>::iterator first=l.begin();first!=l.end();first++)
    {
    
        cout<<*first<<endl; // 11 2 3 12
    }

    return 0;
}

empty/size

.size()==0 等价于 .empty()
empty()效率更高

lsit底层机制 – 没细看

见文档

forward_list<> – 没细看

正向链表
单链表实现

见文档

deque<>

双端队列
常用于快速访问、首尾添加/删除元素
分段连续空间结构实现，(注意：存储并非是连续空间)
随机访问迭代器

创建

#include <deque>

deque<int> d; // 空双端队列

deque<int> d(10); // 10个相同元素，默认为0
deque<int> d(10,1); // 10个1

deque<int> d1={
    1,2,3};
deuqe<int> d2(d1); // 拷贝构造（调用拷贝构造时，存储的数据类型一致）

// 用其他元素进行拷贝
int a[]={
    1,2,3,4,5};
deque<int> d(a,a+5);

空deque - 注意

迭代器不能用来初始化空的deque容器
空deque可以使用push_back/push_front/resize添加元素
另外，需要注意的是：当向deque添加元素时，deque容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址(原占用的内存会释放)，这回导致之前创建的迭代器失效(因此，在添加元素之后，要重新生成迭代器)

访问

[]访问，且可以修改，但是不会进行越界检查
.at()访问，能够进行越界检查

常用函数

没有capacity和data()函数

font() // 返回第一个元素的引用
back() // 返回最后一个元素的引用

push_back
pop_back
push_front
pop_front
emplace_back
emplace_front
insert
emplace
erase
clear

例子

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    
    deque<int> d;

    d.push_back(1);
    d.push_back(2);
    d.push_back(3);

    d.push_front(0); // 头部添加元素

    cout<<d.size()<<endl; // 4 

    for (deque<int>::iterator first=d.begin();first<d.end();first++)
    {
    
        cout<<*first<<endl; // 0 1 2 3 4
    }
    return 0;
}

deque底层机制 – 没细看

见文档

vector采用连续的线性空间
deque存储数据的空间是由一段一段等长的连续空间构成，各段空间之前并不一定是连续的，可以位于内存的不同区域
通过建立map数组，deque容器申请的这些分段的连续空间就能实现"整体连续"的效果…

stack<>

常用于仅在尾部增加/删除元素
基于deque、list、vector实现
不支持迭代器
(可称为 容器适配器)

queue<>

常用于尾部添加、头部删除元素
基于deque、list、vector实现
不支持迭代器
(可称为 容器适配器)

map<关键字类型，值类型>

容器中每个元素都是一个pair结构类型，该结构有两个成员 first、second 关键字对应first,值对应second
二叉树实现（红黑树实现）
双向迭代器：支持 ++p,p++,*p,p–,–p；(双向迭代器不支持+= -= + - > < <= =>)

键必须是唯一的
map容器中存储的都是pari对象，也就是利用pair类模板创建的键值对（各个键值对的键和值可以是任意数据类型，包括结构体或自定义类型）
对于map的排序规则，默认是std::less<T>排序规则，还有其他排序规则，还可以自定义排序规则
键（的值）不能重复也不能被修改（pair对象可以修改）（也就是当键值对存储在map容器中，键是const类型，不能被修改）

序列容器/关联式容器

序列式容器，存储的元素默认是未经过排序的
关联式容器，存储的元素默认会根据元素的键值的大小进行升序排列

创建

#include <iostream>
#include <map>
#include <string>
#include <utility>

using namespace std;

int main()
{
    
    map<string,string> m; // 空对象

    m["1"]="hello world";
    m["2"]="hello qt";
    m["3"]="hello cmd";

    map<string,int> m2={
    {
    "1",2},{
    "2",3}}; // 直接赋值

    pair<string,int> p1("3",4);
    pair<string,int> p2("4",5);
    map<string,int> m3={
    p1,p2}; // 根据pair对象创建

    map<string,int> m4(m3); // 拷贝构造

    // 注意map会自动根据键大小进行排序，所以创建和访问的顺序可能不一样
    for (map<string,string>::iterator it=m.begin();it!=m.end();++it)
    {
    
        /*
            1: hello world
            2: hello qt
            3: hello cmd
        */
        cout<<it->first<<": "<<it->second<<endl;
    }

    cout<<"**********"<<endl;
    for (map<string,int>::iterator it=m2.begin();it!=m2.end();++it)
    {
    
        /*
            1: 2
            2: 3
        */
        cout<<it->first<<": "<<it->second<<endl;
    }

    cout<<"**********"<<endl;
    for (map<string,int>::iterator it=m3.begin();it!=m3.end();++it)
    {
    
        /*
            3: 4
            4: 5
        */
        cout<<it->first<<": "<<it->second<<endl;
    }

    cout<<"**********"<<endl;
    for (map<string,int>::iterator it=m4.begin();it!=m4.end();++it)
    {
    
        /*
            3: 4
            4: 5
        */
        cout<<it->first<<": "<<it->second<<endl;
    }
	
	// 还可以利用其他map的迭代器进行初始化

    return 0;
}

排序规则

// 下面两个等价
map<string,int> m1={
    {
    "1",2},{
    "2",3}}; 
map<string,int,std::less<std::string>> m1={
    {
    "1",2},{
    "2",3}};

访问

[key]，返回键 对应的值（注意：该访问方法，必须保证键存在，如果键不存在，则自动创建一个空值默认键值对）
.at(key) 访问，返回键 对应的值，查找失败则报错
find(key) 返回的是迭代器，不是值，（查找失败则返回map容器最后一个键值对之后的位置，和end() 功能类似）

insert / operator[]

insert() 方法可以将新的键值对插入到map容器中的指定位置，但这与map容器会自动对存储的键值对进行排序并不冲突，当使用insert()方法向map容器的指定位置插入新键值对时，其底层会现将新键值对插入到容器的指定位置，如果其破坏了map容器的有序性，该容器会对新键值对的位置进行调整
其他多种insert的方法，见文档

向map容器中添加新键值对元素时，insert成员方法的执行效率高
对map容器中指定的键值对的值进行更新时，operator[]的效率高
效率的细节说明，没细看，见文档

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    
    // 创建空容器
    map<string,string> m;

    // 创建键值堆变量
    pair<string,string> p={
    "hello world","w"};

    // 创建insert返回值对象
    pair<map<string,string>::iterator,bool> ret;

    // 返回pair对象
    ret=m.insert(p);
    if (ret.second)
    {
    
        cout<<ret.first->first<<": "<<ret.first->second<<endl; // hello world: w
    }
    else
    {
    
        cout<<"ERROR"<<endl;
    }

    ret=m.insert(pair<string,string>({
    "hello qt","q"})); // 右值引用的方式传递临时的键值对变量
    if (ret.second)
    {
    
        cout<<ret.first->first<<": "<<ret.first->second<<endl; // hello qt: q
    }
    else
    {
    
        cout<<"ERROR"<<endl;
    }

    for (auto it=m.begin();it!=m.end();it++)
    {
    
        /*
            hello cmd: c
            hello qt: q
            hello world: w
        */
        cout<<it->first<<": "<<it->second<<endl;
    }

    return 0;
}

其他插入效率比较 - 见文档

例子

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    
    // 创建空容器，根据键的值，对键值做降序排序
    map<string,int,greater<string>> m;

    m.emplace("1",2);
    m.emplace("2",3);
    m.emplace("3",4);

    // 大小
    cout<<"size: "<<m.size()<<endl; // size: 3


    // 判断是否为空
    if (!m.empty())
    {
    
        for (auto i=m.begin();i!=m.end();i++)
        {
    
            /*
                3: 4
                2: 3
                1: 2
            */
            cout<<i->first<<": "<<i->second<<endl;
        }
    }
    return 0;
}

常用函数

find() // 找到指定key值的键值对，返回一个指向该键值对的双向迭代器

lower_bound(key) // 返回一个迭代器
upper_bound(key) // 返回一个迭代器

emplace() // 插入一个新的键值对，执行效率 分析见文档！！！
emplace_hint() // 插入一个新的键值对 

pair 键值对

pair类模板
<first,second> 可以是基本数据类型、结构体、类自定义类型

pair() // 默认构造，创建空pair对象
pair(const first_type &a,const second_type &b) // 直接使用两个元素初始化
template<class U,class V>pair(const pair<U,V> &pr) // 拷贝构造函数，借助另一个pair对象，创建新的对象

#include <iostream>
#include <utility> // pair类模板
#include <string>

using namespace std;

int main()
{
    
    pair<string,int> pair1; // 空对象 默认构造

    pair<string,int> pair2("hello world",1);  // 直接构造
 
    pair<string,int> pair3(pair2); // 拷贝构造

    /*
        : 0
        hello world: 1
        hello world: 1
    */
    cout<<pair1.first<<": "<<pair1.second<<endl;
    cout<<pair2.first<<": "<<pair2.second<<endl;
    cout<<pair3.first<<": "<<pair3.second<<endl;

    pair3.first="hello qt";
    pair3.second=2;
    cout<<pair3.first<<": "<<pair3.second<<endl; // hello qt: 2

    return 0;
}

pair对象可以进行比较，先比较.frist元素的大小，如果相等则继续比较.second元素的大小
注意：对于进行比较2个pair对象，其对应的键和值类型必须相同
对于swap：可以互换两个pair对象的键值对，前提是2个pair对象的键和值类型要相同（pair1.swap(pair2)）

set<>

map的特例，每个元素只有关键字而没有值
双向迭代器

各个元素和值完全相同，且各个元素的值不能重复

basic_string<字符类型>

与vector类型
string是basic_string的实例
随机访问迭代器

其他容器

multimap

存储的各元素的键可以重复
没细看

multiset

存储的各元素的键可以重复

unordered_map

哈希容器
哈希表实现

unordered_multimap

哈希容器
哈希表实现

unordered_set

哈希容器
哈希表实现

容器与类

如果容器的元素类型是一个类，则针对该类：
自定义拷贝构造函数和赋值操作符重载函数
…

常见函数成员

.begin() 
.end() //返回指向容器最后一个元素所在位置的 后一个位置的迭代器
.rbegin() // 返回执行最后一个元素的迭代器
.rend() // 返回指向第一个元素所在位置前一个位置的迭代器
operator=()
size()
capacity() // 返回当前容量
resize() // 改变实际元素个数
font() // 返回第一个元素的引用
back() // 返回最后一个元素的引用
swap()
fill()
....

迭代器

由类模板实现
不同容器对应不同的迭代器
值得注意的是，当迭代器指向容器中的一个特定元素时，迭代器不会保留任何关于容器本身的信息，因此无法从迭代器中判断它是指向哪类具体的容器

容器类名::iterator 迭代器名; // 正向迭代器
容器类名::const_iterator 迭代器名; // 常量正向迭代器
容器类名::reverse_iterator 迭代器名; // 反向迭代器
容器类名::const_reverse_iterator 迭代器名; // 常量反向迭代器

*迭代器名 ：表示迭代器指向的元素

常量/非常量迭代器

非常量迭代器可修改元素，常量迭代器不可修改元素

访问权限

输入输出迭代器，并不是把容器当做操作对象，而是把输入流/输出流当做操作对象

• 输出迭代器

可修改所指向的容器元素
间接访问操作 *
++操作

• 输入迭代器

只读所指向的容器元素
间接访问操作 *；元素成员间接访问->
++ == != 操作

迭代方式

• 前向迭代器

可读写修改所指向的容器元素
++p,p++,*p
元素可赋值，两个正向迭代器可互相赋值

• 双向迭代器

兼容前向迭代器
++p,p++,*p,p–,–p
(双向迭代器不支持+= -= + - > < <= =>)

• 随机访问迭代器

兼容双向迭代器
还支持 迭代器<,> 运算符±,p[i],p-i,p+=i等

• 反向迭代器

注意：反向迭代器的++ 是向左移动一位，–是向右移动一位

• 插入迭代器

在容器中指定位置插入元素

容器/迭代器

随机访问迭代器：vector、deque、basic_string
双向迭代器：list、map、set
不支持迭代器：queue、stack

迭代器相容性

输入/输出 - 前向 - 双向 - 随机
后面迭代器兼容前面的迭代器

迭代器/指针

容器的迭代器和指针不能混用

c11 begin/end

c11具有begin/end两个函数，可以操作容器对象或普通数组
对于容器：功能和普通容器的begin、end成员函数的功能完全想用
对于普通数组，begin()函数返回指向数组第一个元素的指针，end()返回指向数组中最后一个元素之后一个位置的指针