C++ STL容器

vector 变长数组, 倍增的思想

string 字符串, substr() , c_str()

queue 队列, push() , front() , pop()

priority_queue 优先队列, push() , top() , pop()

stack 栈, push() , top() , pop()

deque 双端队列

set , map , multiset , multimap 基于平衡二叉树(红黑树), 动态维护有序序列

unordered_set , unordered_map , unordered_multiset , unordered_multimap 哈希表

bitset 压位

vector

初始化:

vector <int> a (10) 长度为10的数组

vector <int> a (10,3) 长度为10的数组, 每一个数为3

vector <int> a [10] 定义了10个vector

vector 支持的函数:

a.size() 返回元素个数

a.empty() 空返回 true , 非空返回 false

a.clear() 清空

a.front() / a.back() 返回第一个数/ 最后一个数

a.push_back() 在最后插入一个数

a.pop_back() 删除最后一个数

a.begin() 返回 a 的第一个元素的迭代器

a.end() 返回 a 的最后一个元素的下一个元素的迭代器

a[] vector 支持随机寻址

vector 的遍历:

for(int i = 0 ; i < a.size() ; i++) cout << a[i] << ' '; 用数组下标遍历

for(vector<int>::iterator i = a.begin() ; i != a.end() ; i++) cout << *i << ' '; 用迭代器遍历

for(auto x : a) cout << x << ' '; C++的范围遍历

倍增思想: 系统为某一程序分配空间时所需时间, 与空间大小无关, 与申请次数有关.

vector 每一次数组长度不够时, 将数组长度扩大一倍.

pair

初始化:

pair <int,int> p

pair <int,pair <int,int>> p

pair 支持的操作:

p.first 返回第一个元素

p.second 返回第二个元素

string

初始化: string a

string 支持的函数:

a.length() 返回字符串长度

a.size() 返回元素个数

a.empty() 空返回 true , 非空返回 false

a.clear() 清空

a.find('x') 返回字符 x 在字符串中下标

a.substr(,) 返回某个子串

第一个参数表示子串起点下标, 第二个参数表示子串长度.

若第二个参数过大(或无第二个参数), 返回从第一个参数开始的整个子串.

若用 printf 输出 string 要用 a.c_str()

queue

初始化: queue <int> a

queue 支持的函数:

a.size() 返回元素个数

a.empty() 空返回 true , 非空返回 false

a.push(x) 向队尾插入一个元素 x

a.front() 返回队头元素

a.back() 返回队尾元素

a.pop() 弹出队头元素

注意: queue 没有 clear 函数

a = queue <int> (); 相当于 clear 功能

priority_queue

初始化:

priority_queue <int> heap 优先队列, 默认是大根堆

priority_queue <int,vector<int>,greater<int>> heap 定义小根堆

priority_queue 支持的函数:

heap.push(x) 插入一个元素 x

heap.top() 返回堆顶元素

heap.pop() 弹出堆顶元素

注意: priority_queue 没有 clear 元素

stack

初始化: stack <int> a

stack 支持的函数:

a.size() 返回元素个数

a.empty() 空返回 true , 非空返回 false

a.push(x) 向栈顶插入一个元素 x

a.top() 返回栈顶元素

a.pop() 弹出栈顶元素

注意: stack 没有 clear 函数

deque

初始化: deque <int> q

deque 支持的函数:

q.size() 返回元素个数

q.empty() 空返回 true , 非空返回 false

q.clear() 清空

q.front() 返回队头元素

q.back() 返回队尾元素

q.push_back() 向队尾插入一个元素 x

q.pop_back() 弹出队尾元素

q.push_front() 向队头插入一个元素 x

q.pop_front() 弹出队头元素

q[] deque 支持随机访址

q.begin() 返回第一个元素的迭代器

q.end() 返回最后一个元素下一个元素的迭代器

set / multiset

set 元素不能重复, multiset 元素可以重复

初始化:

set <int> s

multiset <int> ms

set / multiset 支持的函数:

s.size() 返回元素个数

s.empty() 空返回 true , 非空返回 false

s.clear() 清空

s.insert(x) 插入一个数 x

s.find(x) 查找一个数 x , 存在返回 x 的迭代器, 不存在返回 end() 的迭代器

s.count(x) 返回某一个数 x 的个数

s.erase() 输入的是一个数 x , 则删除所有 x ; 输入的是一个迭代器, 则删除这个迭代器

s.lower_bound(x) 返回大于等于 x 的最小的数的迭代器, 不存在则返回 end()

s.upper_bound(x) 返回大于 x 的最小的数的迭代器, 不存在则返回 end()

++ / -- 返回前驱/ 后继的迭代器

map / multimap

初始化:

map <string,int> a

a ["xt"] = 666

cout << a ["xt"] <<endl; 输出"1"

可将第一个参数作为数组下标

map / multimap 支持的函数:

a.size() 返回元素个数

a.empty() 空返回 true , 非空返回 false

a.clear() 清空

a.begin() 返回第一个元素的迭代器

a.end() 返回最后一个元素下一个元素的迭代器

++ / -- 返回前驱/ 后继的迭代器

a.insert() 插入的数需要是一个 pair

a.erase() 输入的参数需要是一个 pair 或迭代器

a.find()

a[]

unordered_set / unordered_map / unordered_multiset / unordered_multimap

允许存在重复元素的 set 和map

增删查改的时间复杂度是 O(1)

除不支持 lower_bound() 和 upper_bound() 外, 其余支持函数与 set 和map 相同

bitset

初始化: bitset <10000> S

bitset 只能存储 0 和 1 , < > 内参数表示长度

bitset 支持的操作:

~S 取反

& , | , ^ 与、或、异或

>> , << 位运算

== , != 等于、不等于

S.count() 返回有多少个 1

S.any() 判断是否至少有一个 1

S.none() 判断是否全为 0

S.set() 把所有位置成 1

S.set(k,v) 把第 k 位变成 v

S.reset() 把所有位置成 0

S.flip() 把所有位取反

S.flip(k) 把第 k 位取反