基本数据结构(容器)

序列容器

元素按照特定的顺序存储，如：vector deque list

vector（线性表）

支持动态扩容，也叫柔性数组，内部数据结构是连续存储的，可以随机访问。
尾部插入或删除效率高，中间插入或删除效率低。

list（双向循环链表）

元素通过指针链接，在任何位置插入或删除元素效率较高，随机访问效率低。

deque（指针数组）

数组的每个元素，是一个指向一块连续内存的指针。结合了vector与list的特点。
支持在两端高效的插入或删除元素，支持随机访问。

关联容器

按照键的特定的顺序存储和访问，如：set map 均是基于红黑树实现，本质为平衡二叉树。
增删改查 O（log(n)）

容器适配器

对基本容器进行封装与适配，如：stack queue

stack（后进先出线性表）

默认用deque实现，可以用vector实现

queue（先进先出的线性表）

默认用deque实现，也可以用list实现

迭代器

用于遍历与访问容器中的元素，类似于 指针 。是容器和算法的桥梁
有五种迭代器：
输入迭代器：只能用于读取元素，只能向前移动一次
输出迭代器：只能用于写入元素，只能向前移动一次
前向迭代器：可以向前读取和写入元素
双向迭代器：可以向前或向后移动，进行读取和写入操作
随机访问迭代器：随机访问，像指针一样进行算术运算

A.vector

基本操作

#include <vector>
vector<val> vec;
vector<val>:: iterator ite;

front( )//返回首元素
back( )//返回尾元素
begin( )//返回首元素位置的迭代器
end( )//返回尾元素所在位置的下一位置的迭代器

a.创建以及初始化

1. 默认构造 vector<val> v1;
2. 初始化列表
   vector<val> v2_1={a,b,c,d};
vector<val> v2_2({a,b,c,d});
3. 迭代器构造(左闭右开)
   vector<val> v3(v2.begin(),v2.end());

4. 同数初始化(int时默认为0)
   vector<val> v4_1(a);a个默认值
   vector<val> v4_2(a,b); a个b

5. 复制构造 vector<val> v5(v4) ;

b.赋值 assign( )

1. 直接赋值 v1=v0;
2. 迭代器赋值（左闭右开） v2.assign(v1.begin(),v1.end());
3. 赋值列表 v3.assign({a,b,c,d});
4. 同数初始化 v4.assign(a,b);a个b

c.插入 push_back( ) ，insert( )

1. v.push_back(a);尾插a ，高效
2. v.insert(ite,a);在迭代器ite前插入a ， 低效

d.删除 pop_back( ) ，erase( )，clear( )

1. v.pop_back( );尾删，高效
2. v.erase(ite1);删除ite1所在位置的数据，并返回下一个数据所在位置的迭代器
3. v.clear( ); 清空v中全部数据（而非内存）`

e.扩容机制 size( ) ， capacity( ) ，resize( )

1. v.size( );返回v中元素数目
2. v.capacity( );返回v中在不扩容条件下最大元素数目
3. v.resize(n);将v中元素数目设置为n个，若大于之前size，后续以0填充；若小于之前
   size，保留前n个数目；且当n大于capacity时，vector自动扩容
   扩容机制：
   a. 当前所需size<=capacity+capacity / 2，new capacity=capacity+capacity/2
   b. 当前所需size>capacity+capacity / 2，new capacity=size

f.随机访问 [ ] ，at()

1. v[n]; 返回偏移量为n的数据值， 在debug版本下越界会抛出异常，在release版本下会
   产生未定义行为，访问速度快于v.at(n)
2. v.at(n);返回偏移量为n的数据值， 越界会抛出异常，访问速度慢于v[n]

g.内存置换 swap( ) 智能指针

1. 内存交换
   v1.swap(v2);v1与v2交换内存空间
2. 内存缩容
   vector<val\>(v).swap(v);将v的capacity设置为size
3. 内存清理
   vector<val\>({}).swap(v);将v的capacity设置为0
   注：实际上2,3均为初始化匿名对象后与v内存置换，但借助于智能指针，会自动清理掉v原
   先的内存占用

h.空间预留 reserve

v.reserve(n);直接扩展capacity为n，避免vector在capacity较小时不断的内存申请与数据
复制

i.高效删除

若对vector不关心其顺序，可采用置换后删除的方式来替代erase( );

{
    swap(v[i],v.back( ));
    v.pop_back( );
}

j.排序 sort( )

#include <algorithm>
sort(v.begin(),v.end(),cmp)

排序输入迭代器 左闭右开 默认按“<”排序，可自定义比较函数cmp
注:sort()内部实现主要为快排，当排序数据较大时使用快排将其分割，分割到较小时(32个)
改为插入排序

B.string

头文件

#include <string>//(实际已经包含在<iostream\>中)

a.对象创建

//1.无参构造
string s1;
//2.初始化列表
string s2({'h','e','l','l','o'});
//3.字符串初始化
string s3("hello");
//4.字符串的前n个字符
string s4("hello world",6);
//5.复制构造
string s5(s4);
//6.n个c
string s6(6,'c');

b.对象赋值assign()

//1.字符串常量赋值
s1="hello";
//2.字符串变量赋值
s2=s1;
//3.字符常量赋值
s3='h';
//4.assign()
s4.assign("hello,world");
s5.assign("helloworld",6);
s6.assign(s5);
s7.assign(6,'c');

c.拼接操作 +/+=/append()/push_back()

//1.运算符重载 +/+=
//2.函数重载 append()
s1.append("helloword");
s2.append(s1);
s3.append("hello",3);//拼接前3个字符
s4.append("you are my heart",8,8);//从第8个字符开始的8个字符
//3.push_back()
s5.push_back('x');

d.比较操作 compare/com ope

比较操作 先逐个比较字符直到字典序不同或.size()不同，字典序大的大，size大的大

//compare 返回值为int 
s1.compare(s2) //等于0则相等，大于0则s1>s2，小于0则s1<s2
//运算符重载 ==||!=||>||<||>=||<=