顺序容器

概述

vector

deque    双端队列

list     双向链表

forward  单向链表

array    固定大小数组

string

容器的类型别名

iterator            迭代器类型

const_iterator      迭代器，可读不可写

size_type

difference_type     两个迭代器之间的距离

value_type          元素类型

reference           value_type&

const_reference     const value_type&

begin与end的版本

rbegin,rend        反向遍历

cbegin,cend        const_iterator

初始化

直接拷贝整个容器：要求容器类型和元素类型都相同

由一个迭代器指定元素范围：元素类型能转换即可

list<char*> list_char(vector_string.begin(), vector_string.end())

列表初始化、与大小相关的构造函数

array的初始化必须指定大小：array<int, 10> ay;

赋值和交换

c1=c2要求左右两边具有相同的类型

c1.assign(c2.begin(),c2.end());

其中c1,c2类型可以不同

赋值过后所有迭代器、指针和引用都会失效

swap(c1,c2)

c1.swap(c2)

不涉及拷贝动作，迭代器，指针和引用依然有效

相当于旧c1的迭代器变成了新c2的迭代器

两个array交换会有拷贝过程

大小比较

只有容器其中的元素类型定义了比较运算符时才可以比较

比较类似于char*的strcmp过程

添加元素

c.push_back(x);       //尾部添加c.emplace_back(x);    //同上c.push_front(x);c.emplace_frone(x);c.insert(p,t);        //在迭代器p前插入一个t，返回指向添加的t的迭代器c.emplace(p,t);c.insert(p,n,t);      //在迭代器p前插入n个t，返回指向新添加的第一个c.insert(p,b,e);      //在迭代器p前插入迭代器b和e之间的元素，返回其中的首个c.insert(p,il);       //il为{}包围的元素值列表

可以用insert在vector,deque,string插入，但效率低

emplace操作是直接在c的空间中使用构造函数构造了一个x，省去局部临时对象，当x为一个自定义类元素时比较好理解。

forward_list型只能在首部进行操作

访问元素

c.back();        //返回尾部引用c.front();       //返回首部引用c[n];c.at(n);

注意访问过程中一直为元素的引用

array
     
       ay = {1,2,3,4,5};int &x = ay.at(0);int y = ay.at(1);x = 10;                            //改变了ay[0]y = 10;                            //未改变ay[1]
     

back不适用于forward_list

删除元素

c.pop_back();c.pop_front();c.erase(p);        //返回p后迭代器c.erase(b,e);      //返回e后迭代器c.clear();

vector和string在进行删除操作后，其迭代器会失效

forward_list的特殊操作

flst.before_begin();        //指向链表首元素之前并不存在的元素的迭代器flst.cbefore_begin();lst.insert_after(p,t);      //返回一个指向插入的最后一个元素的迭代器lst.insert_after(p,n,t);lst.insert_after(p,b,e);lst.insert_after(p,li);lst.erase_after(p);         //返回最后一个被删除的元素之后元素的迭代器lst.erase_after(b,e);

改变容器大小

vt.resize(n);        //若n比原来大，添加新元素，初始化；否则删除多余的vt.resize(n,t);      //调整vt，有新加元素的话均为t

同样不支持array

迭代器失效

迭代器指向的元素由于插入，删除而导致其位置发生了改变，此时迭代器会失效

不要保存end返回的迭代器，用.end()

管理vector的大小

vt.shrink_to_fit();vt.capacity();vt.reserve(n);        //将capacity置为n

使用resize()只是针对的都是以后元素

vector
     
       vt(10, 1);vt.resize(15,2);vt.resize(5,2);
     

第一次resize后，在vt后又补了5个2

第二次resize后，vt中只剩下了5个2，capacity会与resize前一样

capacity的预分配大小取决于编译器

容器适配器

一种机制，使某种事物的行为看起来像另一种事物

默认情况下，

stack:deque

queue:deque

priority_queue:vector

可以重载默认容器类型

stack<string, vector<string>> str_stk;

type	operation supported	basic type
stack	push_back, pop_back, back	deque, vector, list
queue	back, push_back, front, pop_front	deque, list
priority_queue	front,push_back,pop_front,random visit	vector, deque

其它操作

stk.top();                //返回栈顶元素que.front();              //返回队首元素prique.top();             //返回优先级最高元素

泛型算法

一些经典算法的通用接口；可用于不同类型的元素和多种容器类型。

auto result = find(vec.begin(), vec.end(), value);

查找成功，返回首个的迭代器；查找失败，返回第二个参数，即查找范围的尾后。

元素本身必须保证支持比较运算符<=>

头文件:algorithm, numeric

只读算法

count(vt.cbegin(), vt.cend(), val);               //统计目标范围中val的数量accumulate(vt.cbegin(), vt.cend(), sum);          //sum+目标范围求和，可以是任何定义了+的类型，const char*就不行equal(vt1.cbegin(), vt1.cend(), vt2.cbegin());    //逐个比较对应元素是否相等，假定vt2比vt1长

写算法

算法不检查写操作，所以要保证目标范围确实存在

fill(vt.begin(), vt.end(), val);        //目标范围中元素重置为零fill_n(vt.begin(), n, val);     //起始位置后连续n个置为val

back_inserter

头文件iterator

接受一个容器的引用，返回与其绑定的插入迭代器，使用它赋值时会自动调用push_back()

vector
     
       vt;fill_n(back_inserter(vt),10,1);
     

拷贝算法

auto ret = copy(vt1.begin(), vt1.end(), vt2.begin());    //保证vt2不比源范围小replace(vt.begin(), vt.end(), s_val, d_val);             //在vt中将s_val替换为d_valreplace_copy(vt1.begin(), vt1.end(), back_inserter(vt2), s_val, d_val);//将替换后的结果保存在vt2中

排序算法

sort(words.begin(), words.end());                        //升序排列wordsauto end_unique = unique(words.begin(), words.end());//将不重复的元素按照原顺序放在最前面，后面的按原顺序被覆盖words.erase(end_unique, word.end());

stable_sort(words.begin(), words.end())为排序的稳定版本

定制操作

向算法中传递函数

sort(words.begin(), words.end(), isShorter());

bool isShorter(const string &s1, const string &s2)为比较words中的元素大小，排序结果按照为真的情况排列

lambda表达式

一个可调用对象，类似于一个未命名的内联函数。

相当于可以传参的函数指针，必须使用尾置返回

结构

[capture list](parameter list) -> return type {function body}

int num = 1;auto fun = [num](const int &a, const int &b){ return a + b + num;};cout << fun(2, 3) << endl;

替换函数指针时效果更明显

捕获和返回

值捕获

引用捕获

使用&符号，保证在lambda执行时变量是存在的

隐式捕获

=表示全部为值捕获，&表示全部为引用捕获

例子可以直接改写为

auto fun = [=](const int &a, const int &b){ return a + b + num;};

混合捕获

[&, identifier_list]:除identifier_list中的各项，其余的都是是引用捕获

[=, identifier_list]:除identifier_list中的各项，其余的都是是值捕获

identifier_list由逗号隔开

可变lambda

对于值捕获，lamda内部的使用相当于拷贝，但要在参数列表后加上mutable关键字才可以修改

int num = 1;auto fun = [num]() mutable { return ++num;};num = 0;cout << fun() << endl;        //输出为2cout << num << endl;          //输出为0cout << fun() << endl;        //输出为3

对于引用捕获，取决于引用指向的是否为const类型

int num = 1;auto fun = [&num]{ return ++num;};num = 0;cout << fun() << endl;        //num为1cout << num;                  //num为1

lambda的返回类型

如果一个lambda体包含return之外的任何语句，编译器会默认假定其返回类型为void

只有一条return时

auto lb = [](int i) {    return i < 0 ? -i : i;};transform(vt.begin(), vt.end(), vt.begin(), lb);

报错

auto lb = [](int i) {    if(i < 0)        return -i;    else        return i;};transform(vt.begin(), vt.end(), vt.begin(), lb);

后置返回类型

auto lb = [](int i) -> int{    if(i < 0)        return -i;    else        return i;};transform(vt.begin(), vt.end(), vt.begin(), lb);

参数绑定

bind函数，头文件functional中

auto newCallable = bind(callable, arg_list);

arg_list由逗号隔开

其中类似于"_n"形式的参数，表示callable中的第n个参数，在命名空间std::placeholders中

using namespace std;using namespace std::placeholders;bool loc(int num, int boundary){    return num >= boundary;}int main(){    int ay[] = {-3,-2,-1,0,1,2,3};    vector
     
       vt(begin(ay), end(ay));    auto loc0 = bind(loc, _1, 0);    auto it = find_if(vt.begin(), vt.end(), loc0);    for( ; it != vt.end(); it++)    {        cout << *it << endl;    }}
     

还可以用bind重新对参数进行排序，实现一些有趣的功能

sort(words.bedin(), words.end(), isShorter);//调整isShorter参数位置，变成由长到短进行排序sort(words.bedin(), words.end(), bind(isShorter, _2, _1));

绑定引用参数

bind的过程默认是由“拷贝”实现的，对于需要以引用方式传递的参数，比如ostream类型，使用ref函数

void print(ostream &os, const int num, const char splitChar){    os << num << splitChar;}int main(){    int ay[] = {-3,-2,-1,0,1,2,3};    vector
     
       vt(begin(ay), end(ay));    auto loc0 = bind(loc, _1, 0);    auto it = find_if(vt.begin(), vt.end(), loc0);    for_each(vt.begin(), vt.end(), bind(print, ref(cout), _1, ' '));}
     

迭代器详解

插入迭代器

back_inserter

front_inserter

inserter

int ay[] = {-3,-2,-1,0,1,2,3};vector
     
       vt(begin(ay), end(ay));list
      
        lt;copy(vt.cbegin(), vt.cend(), inserter(lt, lt.begin()));    //与vt相同copy(vt.cbegin(), vt.cend(), front_inserter(lt));    //前面多了32..-3
      
     

iostream迭代器

直接读取输入流、像输出流写

vector
     
       vt;istream_iterator
      
        int_it(cin);istream_iterator
       
         end;while(int_it != end){    vt.push_back(*int_it++);}
       
      
     

或者直接写成

istream_iterator
     
       int_it(cin);istream_iterator
      
        end;vector
       
         vt(int_it, end);
       
      
     

也可以直接用于算法

绑定时不读取，直到使用迭代器时才真正读取

ostream_iterator
     
       out(os);ostream_iterator
      
        out(os, str);    //str为一个C风格的字符串，会跟在每次打印的后面out = val;                           //将val写入到out对应的输出流*out, ++out, out++;                  //实际没有任何动作
      
     

例子，把vt中的元素都打出来

ostream_iterator
     
       int_it(cout, "\t");for(auto it = vt.begin(); it != vt.end(); it++){    *int_it++ = *it;}
     

*int_it++只是为了与其它迭代器保持一致

使用copy更为简洁

copy(vt.begin(), vt.end(), int_it);

只要类元素支持输入(>>)和输出(<<)运算符，都可以会用流迭代器

反向迭代器

rbegin, rend

crbegin, crend

按实际位置来看，rbegin++相当于end--

所以可以使用反向迭代器来做递减排序

sort(vec.rbegin(), vec.rend())

base成员函数可以将反向迭代器转变为正向迭代器，即其真实位置向右移一位，且++运算变向。

泛型算法结构

迭代器类别

输入迭代器，输出迭代器，前向迭代器，双向迭代器，随机访问迭代器

算法形参模式

alg(beg, end, other args)

alg(beg, end, dest, other args)

alg(beg, end, beg2, other args)

alg(beg, end, beg2, end2 other args)

单个目标迭代器

如带有dest的算法，假定目标空间足够容纳写入的数据，更常见的是dest为ostream_iterator

接受第二个序列范围

没有end2时，假定第二个范围不比第一个范围小

命名规范

使用重载形式传递一个谓词

比如用来代替<=>

unique(beg, end);

unique(beg, end, cmp);

cmp提供判断两个元素是否相等的谓词

_if版本的算法

find(beg, end, val);

find_if(beg, end, pred);

pred查找提供判断范围中的元素是否为真的谓词

拷贝与否的版本

reverse(beg, end):

reverse_copy(beg, end, dest):

将处理后的元素保存到dest中

特定容器算法

list, forward_list定义了独有的sort, merge, remove, reverse和unique

splice成员

参数列表有三种

(p, lst2)  (p, lst2, p2)  (p, lst2, b, e)

	lst.splice(args)	flst.splice_after(args)
插入位置	p之前	p之后
插入元素	p2指向的元素	p2之后的那一个元素

链表特有操作的核心是：改变底层容器

关联容器

两个主要的关联容器:map和set。map是“关键字-值”，set只有“关键字”。

8种容器主要在三个维度上有所区分：

map or set

关键字可否重复

是否有序保存:头文件对应为unordered_map和unordered_set

使用

map<string, size_t> word_count;

可以直接使用下标访问

++word_count[word];

word如果不在map中，下标运算符会自动创建一个新元素，初始值为0

每个key-value对是一个"pair"类型，可以通过迭代器来遍历，内部元素分别对应为first和second

int main(){    map
     
       word_count;    string word;    while(cin >> word)    {        ++word_count[word];    }    for(auto it = word_count.begin(); it != word_count.end(); it++)    {        cout << (*it).first << ' ' << it -> second << endl;    }}
     

在vs中不支持列表初始化，可以用相应类型的数组

map
     
      ::value_type init[] = {    map
      
       ::value_type("b", 1),    map
       
        ::value_type("b", 1)};map
        
          word_count(begin(init), end(init));
        
       
      
     

set<string>

高效的关键字查询操作，检查一个给定关键字是否在set中

string str[] = {"a", "an", "the"};set
     
       exclude;exclude.insert(begin(str), end(str));while(cin >> word){    if(exclude.find(word) == exclude.end())    {        ++word_count[word];    }}
     

关键字类型的要求

对于有序容器而言，关键字必须定义元素比较的方法，默认会采用<

关键字类型上必须有“严格弱序”的定义

自定义比较函数

struct personInfo{    string name;    int age;};bool comparePerson(const personInfo &p1, const personInfo &p2){    return p1.name < p2.name;}int main(){    map
     
       word_count(comparePerson);    //等价于map
      
        word_count(comparePerson);}
      
     

pair类型

头文件utility，用来生成特定类型的模板

定义及初始化

pair<string, int> pi("tom", 12);

pair<string, int> pie("tom", 12);    //空的pair

数据成员是public的，通过.first和.second访问

比较

两个元素都相等时才相等，判断大小按照先比较first，再比较second的原则

基本操作

额外类型

key_type:关键字类型

mapped_type：每个关键字关联的类型

value_type：对于set，与key_type相同；对于map，相应的pair类型

关键字部分是const的，不能改变

迭代器

set的迭代器类型是const的，不能修改关键字

使用迭代器遍历关联容器时，会按关键字升序遍历元素

泛型算法

关键字是const，不能将关联容器传递给修改或重排容器元素的算法

对于只读取元素的算法，关联容器中的元素不能通过它们的关键字进行快速查找，使用其专用的算法会快得多。

可以将关联容器当做源序列或目的位置来做。

添加元素

set.insert(vt.begin(), vt.end());set.insert({2,4,6});                //vs2010不支持person.insert({"han", 34});           //vs2010不支持person.insert(make_pair("tom", 23));person.insert(pair
     
      ("jack", 33));person.insert(map
      
       ::value_type("jack", 33));
      
     

对应的同样有emplace函数

返回值

对于不包括重复关键字的容器，返回一个pair，first是一个指向对应关键字的迭代器，second是一个bool值，表示插入是否成功。

若关键字已在容器中，second为false。

对于包括重复关键字的容器，每次insert都会成功，返回指向新元素迭代器。

删除元素

函数	参数类型	返回值	操作
c.erase(k)	关键字	删除元素的个数	删除关键字值为k的元素
c.erase(p)	迭代器	void	删除p指定的元素
c.erase(b, e)	迭代器对	void	删除指定范围内的元素

map的下标操作(include unordered)

word_count["a"] = 1;

若word_count中不含有关键字值为"a"的元素会默认创建一个，首先初始化值为0，再将1赋予它

c.at(k)

访问关键字为k的元素，带参数检查，若不在c中，会抛出一个“out_of_range”异常

返回值

注意，map迭代器解引用操作和下标操作所得到的结果是不同的，前者返回value_type类型，后者返回mapped_type类型

访问元素

c.find(k);        //返回第一个指向关键字为k的元素迭代器，若不在c中，返回c.end()

c.count(k);       //返回关键字为k的元素数量，对于不允许关键字重复的容器，只有0或1

c.lower_bound(k); //返回第一个关键字不小于k的元素的迭代器

c.upper_bound(k); //返回第一个关键字大于k的元素的迭代器

c.equal_range(k); //返回一个迭代器pair，表示关键字等于k的元素的范围，若不存在，则两个都为c.end()

在multi中查找元素

(1)在multimap及multiset之中，具有相同关键字的元素会相邻存储，所以利用find查找到第一个的迭代器，再根据count锁定范围。

(2)使用lower_bound和upper_bound确定范围

(3)直接使用equal_bound

无序容器

不是用比较来组织元素，而是使用哈希函数

在关键字类型的元素没有明显的序关系情况下很有效

使用无序容器遍历并输出，关键字未必会有序

桶

根据关键字计算出哈希值，一个哈希值对应一个桶，相当于“拉链法”

桶接口

c.bucket_count();        //正在使用的桶数目c.max_bucket_count();    //能容纳的最多的桶数量c.bucket_size();         //第n个桶中有多少元素c.bucket(k);             //关键字为k的元素在哪个桶中

桶迭代器

local_iterator

const_local_iterator

c.begin(n), c.end(n)    桶n的首和尾后

c.cbegin(n), c.cend(n)    

哈希策略

c.load_factor();        //每个桶的平均元素数量，返回floatc.max_load_factor();    //c试图维护的平均桶大小c.rehash(n);            //重新存储，保证bucket_count>=n且bucket_count>size/max_load_factorc.reserve(n);           //重新存储，使得c可以保存n个元素且不必rhash

reserve相当于预先分配了n个元素的空位，保证不引起rehash++

对关键字类型的要求

默认情况会用==来比较关键字值，使用hash<key_type>来生成hash值。标准库为内置类型，string，指针以及智能指针提供了hash模板

对于自定义类型需要提供hash模板

bool equalPerson(const PersonInfo &p1, const PersonInfo &p2){    return p1.name == p2.name;}size_t hasher(const PersonInfo &person){    return hash
     
      ()(person.name);}int main(){    unordered_multimap
      
        person(40, hasher, equalPerson);//40是桶大小}
      
     

如果类中重载了==运算符，可以省去equal函数。

关联容器特点总结

(1)map和set内部实现是采用非线性的二叉树结构，具体的说是红黑树的结构原理；

(2)关联容器对元素的插入和删除操作比vector 要快，比list 要慢，因为list 是线性的，而关联容器是二叉树结构

(3)map和set的查找的复杂度基本是Log(N)