vector

关于vector

vector可以理解为一个变长数组，可以用数组下标访问vector并且大小可以改变。

使用vector

vector在vector头文件中

1
#include <vector>

创建一个空vector

1
vector<int> v;//v[n]

创建500个vector，可以理解为二维数组v[500] [n];

1
vector<int> v(500);//v[500][n]

创建一个包含500个int类型数据的vector：

1
vector<int> v(500,int(0));//v[500]

插入元素

使用push_back()往vector后面插入元素

1
v.push_back(10);

访问vector中的数据

可以使用下标与迭代器访问，但是下标访问如果访问到无效区域会出错，vector下标也是从0开始.

1
2
3
4
5
int now = v[0];//访问第一个数据

vector<int>::iterator it;//定义了一个vector的迭代器
for(it = v.begin();it != v.end();it++)//便利遍历vector 
    cout<<*it<<endl;

一些函数

c.back( ) 传回最后一个数据，不检查这个数据是否存在。
c.begin( ) 传回迭代器的第一个数据。
c.capacity( ) 返回容器中数据个数。
c.clear( ) 移除容器中所有数据。
c.empty( ) 判断容器是否为空。
c.end( ) 指向迭代器中的最后一个数据地址。
c.erase(pos) 删除pos位置的数据，传回下一个数据的位置。
c.erase(beg,end) 删除[beg,end)区间的数据，传回下一个数据的位置。
c.front( ) 传回第一个数据。
c.max_size() 返回容器中最大数据的数量。
c.pop_back() 删除最后一个数据。
c.push_back(elem) 在尾部加入一个数据。
c.rbegin( ) 传回一个逆向队列的第一个数据。
c.rend( ) 传回一个逆向队列的最后一个数据的下一个位置。
c.size( ) 返回容器中实际数据的个数。
c1.swap(c2);swap(c1,c2) 将c1和c2元素互换。

pair

关于pair

pair是一个一对一的配对，左值对应唯一右值，但右值不对应唯一左值。

使用pair

pair不需要头文件

1
2
3
pair<string, string> anon;//创建了一个string对string的pair
pair<string, int> word_count;//创建了一个string对int的pair
pair<string, vector<int> > line;//创建了一个string对vector的pair

也可以在定义时进行成员初始化：

1
2
3
pair<string, string> author("James","Joy");    // 创建一个author，两个元素类型分别为string类型，并默认初始值为James和Joy。
pair<string, int> name_age("Tom", 18);
pair<string, int> name_age2(name_age);    // 拷贝构造初始化

变量间赋值：

1
2
3
4
pair<int, double> p1(1, 1.2);
pair<int, double> p2 = p1;     // 把p1复制给p2，此处为拷贝构造
pair<int, double> p3；
p3 = p1;    // 一样的将p1复制给p3，此处为拷贝赋值

pair访问

访问两个元素操作可以通过first访问左值和sencond访问右值：

1
2
3
4
pair<int ,double> p1;
p1.first = 1;
p1.second = 2.5;
cout<<p1.first<<' '<<p1.second<<endl;//输出结果：1 2.5

插入元素

利用make_pair()插入新的pair对：

1
p1.mark_pair(1, 1,5);

map

关于map

map是一颗红黑树，他提供了一个键对值的映射，键与值都可以为任意类型。在没有理解map之前可以将其简单理解为一个超大数组。

使用map

这里建立了一个int对string的映射，一个int对应一个string

1
2
#include <map>
map<int, string> mp;

插入元素

可以将map的操作简单看作数组的操作，但是他并没有没有数组这么简单

1
2
mp[123] = "student_first";//123键对应"student_first"这个值，即在123这里对应"student_first"这个字符串
mp[456] = "student_second";

查找元素

当所查找的关键key 出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同 。

1
2
// find 返回迭代器指向当前查找元素的位置否则返回map.end()位置
map<int, string>::iterator iter = mp.find("123");

刪除与清空元素

1
2
3
4
5
6
7
8
9
//迭代器刪除
iter = mp.find("123");
mp.erase(iter);
 
//用关键字刪除
int n = mp.erase("123"); //如果刪除了會返回1，否則返回0
 
//清空map
mp.clear();

map的大小

在往map里面插入了数据，我们怎么知道当前已经插入了多少数据呢，可以用size函数 ，用法如下：

1
int size = mp.size();

map的常用函数

begin( ) 返回指向map头部的迭代器
clear( ) 删除所有元素
count( ) 返回指定元素出现的次数
empty( ) 如果map为空则返回true
end( ) 返回指向map末尾的迭代器
erase( ) 删除一个元素
find( ) 查找一个元素
insert( ) 插入元素
key_comp( ) 返回比较元素key的函数
rbegin( ) 返回一个指向map尾部的逆向迭代器
rend( ) 返回一个指向map头部的逆向迭代器
size( ) 返回map中元素的个数

set

关于set

关于set，必须说明的是set 关联式容器 。set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一 ，而且系统能根据元素的值自动进行排序 。应该注意的是set中数元素的值不能直接被改变 。

set的插入和查找都是log级别

使用set

1
2
#include<set>
set<int> s;

插入元素

1
s.insert(3);//在set中插入3

查找元素

当所查找的关键key出现时，它返回数据所在对象的位置，如果沒有，返回iter与end函数的值相同 。

1
set<int>::interator iter = s.find(3);//返回3的位置

清空元素

1
s.clear();//清空set

set的大小

1
int size = s.size();//返回元素个数

set中常用的方法

begin() 返回一个迭代器，返回的值为set容器的第一个元素
end() 返回一个迭代器，返回的值为set容器的最后一个元素
clear() 删除set容器中的所有的元素
empty() 判断set容器是否为空
max_size() 返回set容器可能包含的元素最大个数
size() 返回当前set容器中的元素个数
rbegin() 返回一个逆迭代器，返回的值和end()相同
rend() 返回一个逆迭代器，它指向容器c的第一个元素前面的位置

queue

关于queue

queue是一个队列容器，先进先出

使用queue

1
2
#include<queue>
queue<int> q;

插入元素

1
q.push(1);//在队列尾部添加1

查找元素

queue不能指定查找某个元素的位置，但是可以查找第一个元素和最后一个元素。

1
2
int num1 = q.front();//返回队首元素
int num2 = q.back();//返回队尾元素

删除元素

queue只能删除队首元素

1
q.pop();//删除队首元素

队列大小

1
2
int size = q.size();//返回队列中元素的个数
int flag = q.empty();//查看队列是否为空，如果为空返回1，非空返回0

priority_queue

关于

这个是优先队列，与queue相似，但是他并不是单纯的按照入队顺序出队，而是按照优先权出队（默认大者优先出队，也可自定义优先级）。与普通队列不同的是优先队列是队尾先出列！

使用优先队列

优先队列有三个参数，元素类型，容器类型，比较算子。默认容器为vector，默认算子为less，即小的往前，大的往后，队尾先出列。

1
2
3
priority_queue<int> q;
priority_queue<pair<int, int> > q;
priority_queue<int, vector<int>, greater<int> >q;//小的先出队

插入元素

与queue一样，使用push插入，但是需要与优先队列中的一致

1
q.push(1);

查找元素

优先队列只能访问最高优先级的值，即队尾

1
int num = q.top();

删除元素

与queue相似，利用pop删除最高优先级的值

1
q.pop();

队列大小

与queue相似

1
2
int size = q.size();//返回队列元素个数
int flag = q.empty();//如果队列为空则返回1，否则返回0

自定义比较算子

这是优先队列最困难也是最重要的部分。一般使用重载运算符。这里自定义了一个从小到大排的算子，即大的先出

1
2
3
4
5
6
struct node{
	int w;
}edge;
inline bool operator > (const edge a, const edge b){
	return a.w > b.w;
}

优先队列排序与出队的关系

优先队列中元素是从队尾出，所以当从小到大排序时(less)，大的先出队；当从大到小排序时(greater)小的先出队!

deque

关于

deque的名字叫双向队列，与名字一样，可以双向添加双向删除

使用deque

deque有单独的头文件

1
2
#include<deque>
deque<int> q;

插入元素

push_front()在队头插入，push_back()在队尾插入

1
2
q.push_front(1);//在队头插入1
q.push_back(2);//在队尾插入2

删除元素

pop_front()删除队头元素,pop_back()删除队尾元素

1
2
q.pop_front();//删除队头元素
q.pop_back();//删除队尾元素

队列大小

和queue相同

1
2
int size = q.size();//返回队列中元素个数
int flag = q.empty();//队列空返回1，否则返回0

删除队列

clear()清空队列

1
q.clear();