C++ 常用STL容器

vector

首先这个数组的一个替代品，但是与数组不一样的是，它更方便，主要表现在可以动态增长、可以自己管理内存，对于数组类型也是你给他指定什么类型就是什么类型。最关键的是提供了对应的方法，来操作vector，所以整体上使用容器会十分方便。

常见用法

// 创建一个vector存储 int
 vector<int> vec; 
//显示 vec 的原始大小,使用size()方法
cout << "vector size = " << vec.size() << endl;
//在向量末尾添加值i,使用push_back()方法
vec.push_back(i);
//访问vector的元素,与数组一样
vec[i];
//使用迭代器iterator访问
vector<int>::iterator v = vec.begin(); 
while( v != vec.end()) 
     cout << "value of v = " << *v << endl;
     v++;

关于使用迭代器访问(修改等)vector的操作，首先我们需要声明一个迭代器

vector<double>::iterator pd;  //定义了一个用于访问vector<double>的迭代器
pd = scores.begin();  //scores这个vector的起始元素
//而end()方法则是指向容器最后一个元素后面的那个元素 超尾
//而有时我们也许并不清楚我们需要定义的迭代器是属于哪种类型的，所以C++ 11提供了一个新的类型 auto
auto pd = scores.end();  //编译器会自动推断出pd属于哪种类型

另外我们再来看看其他常用与vector的方法：

erase()方法

首先erase方法用于删除vector中给定区间的元素

scores.erase(scores.begin(),scores.begin()+2);

该方法有两个参数，第一个参数用于指定该区间的起始位置，第二参数用于指定该区间的末尾位置的后一个。

vec.erase(p1,p2);  //那么指定的区间为[p1,p2)

insert()方法

insert方法用于将一个容器对象的一部分插入到另一个容器的某个位置。

vector<int> old_v;
vector<int> new_v;
old_v.insert(old_v.begin(),new_v.begin()+1,new_v.end());

该方法有三个参数，第一个参数用于指定被插入容器对象的插入位置，第二参数指定待插入的区间的起始位置，第三个参数指定待插入区间的末尾位置的后一个位置。

C++ STL的vector是有capacity和size的区别的：
size 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个容器。
capacity 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。
在 STL 中，拥有 capacity 属性的容器只有 vector 和 string。

resize()方法 和 reserve()方法

resize()方法是调整实际存在的内存空间大小，而reserve()只是修改capacity的值， 容器内的对象并没有真实的内存空间(空间是"野"的)。 此时切记使用 [] 操作符访问容器内的对象，很可能出现数组越界的问题。

#include <iostream>
#include <vector>
using std::vector;
int main(void)
    vector<int> v;
    std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
    v.reserve(10);
    std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
    v.resize(10);
    v.push_back(0);
    std::cout<<"v.size() == " << v.size() << " v.capacity() = " << v.capacity() << std::endl;
    return 0;

还有一些其他操作，矢量模板类并没有包含这些常见方法，而是以一种非成员函数来执行这些操作，这些非成员函数适用于所有容器类，这样做是为了省去大量的重复工作。

for_each() 函数

该函数用于对指定区域的元素进行指定函数的操作

vector<int>book;
for_each(book.begin(),book.end(),Show);

for_each函数有三个参数，前两主要用于确定要迭代的区间，如上述代码所展示是从book的开头元素到末尾元素。而第三个参数则是对每个元素所要进行的操作，是一个函数对象。

注意：for_each()函数将被指向的函数应用于容器区间的各个元素。被指向的函数不能修改容器元素的值！

Random_shuffle()函数

该函数用于随机排列指定区间的元素

vector<int>book;
Random_shuffle(books.begin(),books.end());

Random_shuffle函数接受两个参数，分别用于确定区间的首和尾。

当然对于使用该函数的容器是一定要运行进行随机访问的。

sort()函数

该函数有两个版本，区别在于参数上，功能则都是对容器指定区域进行排序。

版本一：两个参数，分别指向待排序区间的首和尾，默认排序为升序排列。

vector<int>book;
sort(book.begin(),book.end());

版本二：三个参数，前两个参数分别指向待排序区间的首和尾，最后一个参数则用于确定比较器

vector<int>book;
bool Worsehan(const book&r1,const book&r2)
    if(r1.rating<r2)
        return true;
        return false;
sort(book.begin(),book.end(),Worsehan);

这里需要说明一下，对于比较器而言，默认a < b 为true 就以升序排序，那么我们比较器如果当a > b时返回true则就是以降序进行排序。

然后还有几个在内存复制上经常用到的的函数

std::copy()函数

用于有迭代器的数据类型中，将一个指定区域的数据拷贝到另一个区域中去

std::copy(start,end,begin);

这个函数有三个参数，前两个参数分别为需要拷贝的源起始位置 和 源结尾位置，第三个参数表示的是将被拷贝到的目的位置的首位置。

copy(b,e,b1)：将迭代器范围[b,e)的元素复制到 以b1为起点(* begin* )的位置 ；
copy_backward(b,e,b1)：将迭代器范围[b,e)的元素复制到以 b1为终点(* end* ) 的位置；
copy_if(b,e,b1,pre)：将迭代器范围[b,e)中 使得pre为真 的元素复制到以b1为起点的位置，即只将满足条件的元素复制到以b1为起点的位置。

list

STL list容器又称双向链表容器，即该容器的底层是以双向链表的形式实现的。 这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。

可以看到，list 容器中各个元素的前后顺序是靠[ 指针 ]来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null。

常见用法

#inlcude<list>
using namespace std;
//创建一个没有任何元素的空 list 容器
list<int> values;
//创建一个包含n个元素的list容器
list<int>values(10);
//通过此方式创建 values 容器，其中包含 10 个元素，每个元素的值都为相应类型的默认值（int类型的默认值为 0）。
//创建一个包含n个元素的list容器，并为每个元素指定初始值
list<int> values(10,5);  //创建一个包含10个元素且值都为5的value容器
//已有list 容器的情况下，通过拷贝该容器可以创建新的 list 容器。
list<int> value1(10);
list<int> value2(value1);
//拷贝普通数组，创建list容器
int a[]={1,2,3,4,5};
list<int> values(a,a+5);
//拷贝其它类型的容器，创建 list 容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}
//注意以上操作就可以实现类似于python的切片操作

push_front()方法

在容器头部插入一个元素。

pop_front()方法

删除容器头部的一个元素。

其余方法与vector类似

deque

双端队列

首先定义方法与vector和list相似，因为是双端队列，所以有一些特别的成员函数。

map

map的构造

#include<map>
using namespace std;
//创建一个key为int类型，value为string的map
map<int ,string>person;

map中添加数据

• insert函数插入pair数据

map<int ,string>person;
pair<int,string>p1(1,2);
person.insert(p1);

• insert函数插入value_type数据

person.insert(map<int,string>::value_type(2,"Tom"));

• 用数组方式插入数据

person[3]="Jerry";

map数据的遍历

• 前向迭代器

map<int,string>::iterator it=person.begin();
while(it!=person.end())
    cout<<it->first<<' '<<it->second<<endl;
    it++;

• 反向迭代器

std::map < int, string > ::reverse_iterator iter;  
for(iter = mapPerson.rbegin(); iter != mapPerson.rend(); iter++) 
    cout<<iter->first<<"  "<<iter->second<<endl;  

删除元素

//删除键为1的元素
person.erase(1);
//删除迭代器 key指向的元素
map<string,int>::iterator key=person.find(1);
if(key!=person.end())
    person.erase(key);
//删除所有元素
person.erase(person.begin(),person.end());

map 查找问题

• count()

m.count(p); //返回m中键k出现的次数

对于map对象，count成员的返回值只能是0或者1，因为键如果存在那么必定是唯一的。

int occurs=0;
if(person.count(1))
   occurs=person[1];

所以使用count来判断键是否存在于map中，当然上述程序中，先调用count函数来判断键是否存在，之后又对其进行访问，相当于是对元素查找了两次，如果希望当元素存在时就使用它的话应该用find方法。

• find()

m.find(k); //返回指向键为k的元素的迭代器

map<int,string>::iterator it=person.find(1);
if(it!=person.end())
    cout<<it.second<<endl;  

所以，通过对于查找一次之后，还想继续访问，最好使用find方法。

map sort问题

map中是自动按key升序排序

set

集合的使用，相对于map而言要简单，基本上map的用法就包括了set的用法

• 在set中添加元素

set<string> set1;
set1.insert("the");
set1.insert("and");

• 从set中获取元素

//count
iset.count(1);   //return 0 or 1
//find
iset.find(1);   //return point to 1  iterator

• 从set中删除元素

set1.erase(1);  //删除集合中的元素1

priority_queue

优先级队列，就是堆，需要#include< queue >

定义优先级队列

priority_queue<Type, Container, Functional> heap;
* Type 就是数据类型
* Container 就是容器类型
* Functional 是比较方法
//对于默认的两种方法，比如按Type的大小分为大根堆和小根堆
priority_queue<int,vector<int>,greater<int>>heap;  //升序队列 小根堆
priority_queue<int,vector<int>,less<int>>heap;    //降序队列 大根堆
priority_queue<int,vector<int>>heap; //默认大根堆

关于heap的常用方法

• top方法访问队头元素
• empty队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

自定义关于heap的比较方法

//自定义比较方法
template <typename T>
struct cmp{
   bool operator()(T a,T b)