排序

重载运算符

1
2
3
4
5

bool operator < (const struct &a, const struct &b){
	return your own rule;
}

sort(struct a, struct a + n);

map

1
2

map<typeA,typeB> m;
映射typeA到typeB
方法 例子
[A] m[A]; //A映射的值
find m.find(x)//查询x元素的迭代器，若不存在返回m.end()
front a = q.front();
end m.end();末尾+1的迭代器
size m.size();
empty m.empty();
clear m.clear();

队列

queue

方法 例子
push q.push(element); //队尾
pop q.pop();//队头
front a = q.front();
back b = q.back();
size q.size();
empty q.empty();

均为O(1)

1
2
3
4
5
6
7
8

void clear(queue<int>& q) {
	queue<int> empty;
	swap(empty, q);
}
//清空1
queue<int> q;
q = queue<int>();
//清空2

priority_queue

大根二叉堆

方法 例子
push q.push(element); //队尾 O(logn)
pop q.pop();//队头 O(logn)
top a = q.top()//最大值O(1)

重载运算符

1
2
3
4
5
6
7

struct example{
    int x,y;
};

bool operator < (const example &a, const example &b){
    return your own rule;
}

1
2
3
4

 //升序队列  小顶堆 great 小到大
 priority_queue <int, vector<int>, greater<int> > pq;
 //降序队列  大顶堆 less  大到小 默认
 priority_queue <int, vector<int>, less<int> > pq;

二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//数组为单调增时候
lower_bound(start,end,num (,compare) )
//第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end
upper_bound(start,end,num (,compare) )
//第一个大于num的数字，找到返回该数字的地址，不存在则返回end

两个函数返回的结果都是迭代器
    

//若单调减
compare 填入 greater<type>()重载
//自定义
bool compare(const int &a,const int&b)
{
    return your own rule;
}

vector

方法 例子
push_back v.push_back(element);在最后添加一个数据
pop_back v.pop_back();//去掉最后一个数据
begin v.begin()//begin 得到头指针
end v.end()//最后一个单元+1的指针
front v.front()//头元素引用
end v.end()//尾元素引用
size v.size()//大小
clear v.clear()//清空
empty v.empty()//是否为空 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

初始化:
vector<type> name;
访问:
name[idx];
or
vector<type>::iterator it;
for(it = name.begin();it!=name.end();it++){
    cout << *it;
}
or (c++11)
使用auto代替vector<type>::iterator
or (c++11)
for(auto i : name){
    cout << i;
}
若想改变内容，则需要引用变量
for(auto &i : name){
    i = i + 1;
}