前言

STL全称Standard Template Library，就是标准模板库，意思就是一群非常牛批的人实现的各种算法，数据结构的库被当成标准模板给你直接使用，他位于std这个namespace中 ，我们这里还要介绍一个东西叫做迭代器(iterator),迭代器是一个数据类型，其可以表示容器内所有元素的值，也支持做自增等操作，相当于容器和操作容器算法之间的中介¹,这个容器也是非常抽象的std数据结构对象，假如我们要迭代每一个数据结构就需要实现不同的数据类型进行迭代，但是有了迭代器就不用了

List

这里的list其实就是双向循环链表和vector不一样，vector是一串连续的地址空间，而List不是连续的地址空间，具体不再细说，注意向List push元素，这些元素存在stack中，假如我们的push操作在函数中，退出函数啥也没了…看代码

#include <iostream>
#include <list>
#include <iterator>

using namespace std;
void show_list(list<int> list1){
    list<int>::iterator it; //创建一个迭代器，，迭代器是一个抽象变量，用其表示容器内任意已一个元素
    cout << "show list is" << endl;
    for( it = list1.begin(); it != list1.end(); it++){
        cout << *it  << endl;
    }
}

int main()
{
    list<int> list1; //构建一个list
   
    for ( int i = 0 ; i < num; i++){
        list1.push_front(i *2); //向容器内传入元素
    }
    
    show_list(list1);

    
 

    return 0;
}

关于容器的函数有非常多，比如
XXX.push_back()
XXX.push_front()
XXX.pop_back()
XXX.pop_front()
XXX.back()返回尾元素
XXX.front()返回头元素
XXX.begin()以迭代器遍历的形式返回头节点
XXX.end()以迭代器遍历的形式返回尾节点
XXX.size()
XXX.erase()接受一个迭代器，然后再对应的list中删除
我们看一下erase的使用，发现固然erase可以接收一个迭代器然后删除对应元素，但是不能正真的抹去他

#include <iostream>
#include <unordered_map>
#include <list>
#include <iterator>
using namespace std;

void print_container(const std::list<int>& c){
    for(int i : c){
        cout<<i<<" ";
    }
    cout<<"\n";
}

int main()
{
    std::list<int> list;
    std::unordered_map<int, std::list<int>::iterator> umap;
    for(int i = 0; i < 10;i++){
        list.push_front(i * 3);
        umap[i] = list.begin();
    }
    
    //遍历list
    print_container(list);
    
    //erase
    list.erase(umap[3]);
    
    //遍历list
    print_container(list);
    
    if(umap.count(3)){
        cout<<"key is 3 exit "<<*(umap[3])<<"\n";
    }else{
        cout<<"key is 3 not exit"<<"\n";
    }
    

    return 0;
}

交换list的元素

众所周知list是双向循环链表，如果我们只交换list元素指针和引用是不能达到效果的,我们只能用迭代器的函数iter_swap();进行交换

#include <iostream>
#include <list>
#include <map>
#include <iterator>

using namespace std;

int main()
{
    std::list<int> list1; //创建一个list,每一个list的成员都是int
    std::list<int>::iterator it,it1;
    //初始化list
    for (int i = 0; i < 10; i++){
        list1.push_back(i * 3);
    }
    
    //打印list1
    cout << "list1 is: " ;
    for (it = list1.begin(); it != list1.end(); it++){
        cout << *it << " ";
    }
    cout << "\n";
    
    //交换2个成员
   it = list1.begin();
   it1 = list1.end();
   it1--;
   
   iter_swap(it,it1);
   
    cout << "after swap list1 is: " ;
    for (it = list1.begin(); it != list1.end(); it++){
        cout << *it << " ";
    }
    cout << "\n";

    return 0;
}

push_back vs emplace_back

我们在插入的时候一般用push_back但是在c++11有一个新的容器插入方法emplace，简单区分一下区别，push，或者insert在移动或者copy元素进容器的时候是call copy constructor和move constructor，而emplace是constructed in-place的，而不是调用移动或者copy操作，避免了不必要的copy
换句话说emplace_back的对象是一个class或者struct类型且在构造struct和class的时候可以传参，那么我们在使用emplace_back的时候可以直接传入参数(mov construct)，而非class或者struct对象，如下代码

#include <vector>
#include <iostream>
#include <memory>

class A{
    int data;
public:
    A(){std::cout << "common construct" << std::endl;}
    A(int i ):data(i){}
    A(const A&& rhs){ std::cout << "move construct" << std::endl;}
    A(const A& rhs) { std::cout << "copy construct " << std::endl; }
};


int main(){
    std::vector< A > v;
    v.emplace_back(1);
}

上述代码只会调用第二个构造函数，并且是直接在vector中构建不会触发move construct
下面的代码会触发move construct,下面代码先触发第二个构造函数再通过move construct移动进vector中

#include <vector>
#include <iostream>
#include <memory>

class A{
    int data;
public:
    A(){std::cout << "common construct" << std::endl;}
    A(int i ):data(i){}
    A(const A&& rhs){ std::cout << "move construct" << std::endl;}
    A(const A& rhs) { std::cout << "copy construct " << std::endl; }
};


int main(){
    std::vector< A > v;
    
    v.emplace_back(A(1));
}

既然说了push_back是copy，那么不可避免地是copy的时候触发拷贝构造，而element是会用到移动构造

什么是constructed in-place，我没有找到关于``c++ in-place```相关的名词，但是我在搜索的时候大家在提及in-place和另一个名词经常化为等同，那就是placement new，这个比较好理解，就是我们构建一个结构或者class，不是直接new在堆上构建他，而是先搞一片内存，再把这个内存强制转换成对应的结构，这个在一些的场景下比先开辟内存再把东西copy进去效率要高，比如

char *buf  = new char[sizeof(string)]; // pre-allocated buffer
string *p = new (buf) string("hi");    // placement new
string *q = new string("hi");          // ordinary heap allocation

关于移动构造看下面简介和这里个链接
Move constructor moves the resources in the heap, i.e., unlike copy constructors which copy the data of the existing object and assigning it to the new object move constructor just makes the pointer of the declared object to point to the data of temporary object and nulls out the pointer of the temporary objects. Thus, move constructor prevents unnecessarily copying data in the memory.

这里细说他们的内部实现
push
1.在push一个vector的时候会先创建一个新的vector(在vector已经存在的情况下)，然后将老的vector和新push的元素copy进去

在list中查找元素

查找元素我们要用find函数即可，但是想用std::find我们必须#include <algorithm>
std::find输入一个list的首部迭代器，再输入一个list尾部迭代器，最后输入一个待查找的数值，假如找到了这个数值就返回这个数，没有找到就返回尾部迭代器，如下

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>

using namespace std;

int main()
{
    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    l1.push_back(5);
    l1.push_back(6);
    
    if( std::find(l1.begin(), l1.end(), 3) != l1.end() ){  //假如find返回不等于尾部迭代器说明已经找到了数
        std::cout << "find!" << "\n";
    }

    return 0;
}

hashtable

hash表都知道是啥，我们不介绍其细节，但是std中有一个hash对象，这个hash对象只是提供hash函数，做存储的hash表还是用map类型
我们先创建一个hash表对象
但是map类型底层上来讲是红黑树，其搜索插入都是Olog(n)的复杂度,并且顺序存储，真要hashtable还得看unordered_map

std::map<int, std::list<int>::iterator> LRUInstance_map;

看我们结合list和map实现map直接定位到list中的某个节点(要知道list是双向循环链表)，其时间复杂度为O(1)

#include <iostream>
#include <map>
#include <list>
//#include <iterator>

using namespace std;

int main()
{
    std::list<int> LRUinstance;
    std::map<int, int *> LRUmap;
    
 
    for(int i = 0; i < 10; i++){
        LRUinstance.push_back(i * 3);
        LRUmap[i] = &(LRUinstance.back());
         //cout << "map" << i << " is " << *(LRUmap[i]) << endl;
    }
    
    cout << "link list of n5 node is "<< *(LRUmap[5]) << endl;
    *(LRUmap[5]) = *(LRUmap[5])-1;
    cout << "now before -- link list of 5 node is "<< *(LRUmap[5]) << endl;
    
    //cout<<"Hello World";

    return 0;
}

unordered_map

我们上面提到了unordered_map，这里细说一下，unordered_map底层存储才是真正使用的hash表存储，map用的是红黑树,所以unordered_map的查找和插入最快能达到O(1)，unordered_map解决冲突的方法应该是开放链表法?
unordered_map有2种插入方法，分别是用[]直接插入，第二个是用unordered_map的insert函数

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;
    //insert by []
    umap["zzz"] = 1;
    //insert by UMAP.insert()
    umap.insert(make_pair("ccc",2));
    
    cout<<"umap zzz is "<< umap["zzz"] << "\n";
    cout<<"umap ccc is "<<umap["ccc"]<<"\n" ;
    
    return 0;
}

查找某个key的值用find(key)或者直接用[],但是注意我们使用find查找返回的是unordered_map类型的迭代器，unordered_map类型的迭代器可以用->first访问key元素，->second访问value元素

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;
    //insert by []
    umap["zzz"] = 1;
    //insert by UMAP.insert()
    umap.insert(make_pair("ccc",2));
    
    cout<<"umap zzz is "<< umap["zzz"] << "\n";
    cout<<"umap ccc 's value is "<<umap.find("ccc")->second<<"\n" ;
    cout<<"umap ccc 's key is "<<umap.find("ccc")->first<<"\n" ;
    
    return 0;
}

我们知道一个hash表可以存储多个多余的key，但是我们的unordered_map不支持多余的key存在，count函数本来是用于查看一个key对应多少个元素的，但是因为unordered_map的特性所以在这个数据结构中主要用于检查这个key存不存在…

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;

    umap["zzz"] = 1; 
    if (umap.count("zzz")){
        cout << "key zzz exist!!!"<<"\n";
    }
    
    return 0;
}

我们知道hash表中有bucket的概念，bucket简单的说是hash表中一共有多少slot，不管这个slot有没有key/value对

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;
    //insert by []
    umap["aaa"] = 6;
    umap["bbb"] = 6;
    umap["ccc"] = 6;
    umap["ddd"] = 6;
    umap["eee"] = 6;
    umap["fff"] = 6;
    umap["ggg"] = 6;
    umap["hhh"] = 6;
    umap["iii"] = 6;
    umap["jjj"] = 6;
    umap["kkk"] = 6;
    umap["lll"] = 6;
    umap["mmm"] = 6;
   
    
    cout<<"bucket_count  is "<<umap.bucket_count()<<"\n"; 
    
   
    
    return 0;
}

上面一共有33个bucket，但是我们只有13个bucket有数据
map还有一个函数叫做bucket()这个函数传入key，返回这个key在hash表中的真实位子,个人感觉这个函数是对key进行hash，然后直接返回其应该对饮的位子

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;
    //insert by []
    umap["aaa"] = 6;
    umap["bbb"] = 6;
    umap["ccc"] = 6;
    umap["ddd"] = 6;
    umap["eee"] = 6;
    umap["fff"] = 6;
    umap["ggg"] = 6;
    umap["hhh"] = 6;
    umap["iii"] = 6;
    umap["jjj"] = 6;
    umap["kkk"] = 6;
    umap["lll"] = 6;
    umap["mmm"] = 6;
   
    
    cout<<"key aaa locate is  "<<umap.bucket("ccc")<<"\n"; 
    
   
    
    return 0;
}

UMAP.erase()函数根据输入的key擦除对应的key/value

#include <iostream>
#include <unordered_map>

using namespace std;

int main()
{
    std::unordered_map<string,int> umap;
    //insert by []
    umap["aaa"] = 6;
    umap["bbb"] = 6;
    umap["ccc"] = 6;
    umap["ddd"] = 6;
    umap["eee"] = 6;
    umap["fff"] = 6;
    umap["ggg"] = 6;
    umap["hhh"] = 6;
    umap["iii"] = 6;
    umap["jjj"] = 6;
    umap["kkk"] = 6;
    umap["lll"] = 6;
    umap["mmm"] = 6;
   
    if(umap.count("aaa")){
        cout << "aaa is exsit!"<<"\n";
    }else{
        cout << "aaa is's exsit!" << "\n";
    }
    //erase element ,the key of element is "aaa"
    umap.erase("aaa");
    
    if(umap.count("aaa")){
        cout << "aaa is exsit!"<<"\n";
    }else{
        cout << "aaa is's exsit!" << "\n";
    }
 
    return 0;
}

deque

首先我们知道queue是insert from end，delete from front，而deque全称叫做double-end queue，他是queue的一个特殊形式，其插入和删除都是在end操作

---

1. 引用1 ↩︎