容器

头文件

set<Key, Compare, Alloc>

<set>

begin() end()

clear()empty()size()

insert(t/p,t/I,j)erase(k/p/p,q)

find(k)~O(logN) count(k)

lower_bound(k)~O(logN)upper_bound(k) ~O(logN)

multiset<Key, Compare, Alloc>

map<Key, Data, Compare, Alloc>

<map>

operator[](k)

不要用 insert()

multimap<Key, Data, Compare, Alloc>

insert(pair)

类型

名称

示例

备注

容器成员函数

begin() end()

p=c.begin(); p!=c.end();

[ c.being(),c.end() )

clear()

c.clear();

empty()

if( c.empty() );

size()

int len=c.size();

insert(t/p,t/I,j)

c.inset(n) (p,n) (pbgn, pend)

erase(k /p /p,q)

c.erase(k) (p) (pbgn, pend)

find(k)

p=c.find(k);

Y:*p=k N:p=c.end();

count(k)

int count= c.count(k)

lower_bound(k)

p=c.lower_bound(k)

*p>=k 且 p 最前

upper_bound(k)

p=c.upper_bound(k)

*p>k 且 p 最前

operator[](k)

day[“Feb”]=28

可用于增加，修改

类型

名称

示例

备注

游离函数

作用于

数组

search()

p=search (s1, s1+ len1, s2, s2 + len2);

查子串 A(n)O(n*m)

search_n()

p=search_n(first, last, count, val)

查重复元素子串 O(l-f)

unique()

newend=(first,last,myEqual);

除去重复元素 ( 留首 )=(l-f-1)

unique_copy()

newend=(first,last,opFirst,myEqual);

lower_bound()

pb=c.lower_bound(first,last,k,myEqual)

*p>=k 且 p 最前

要求升序

log(l-f)+1

upper_bound()

pe=c.upper_bound(first,last,k,myEqual)

*p>k 且 p 最前

inplace_merge ()

inplace_merge(first,middle,last,myLess);

[f,m) 和 [m,l) 都升序→ [f,l] 升序

关于set的：

后三者返回 newEnd

includes,set_union~max(m,n), set_intersection~min(m,n)

set_difference~max(m-n,0),set_symmetric_difference~|m-n|

可模拟集和多重集， ~ 号后为出现 m 、 n 次的元素出现次数

关于 heap 的：

全部返回 void

push_heap~logN p op_heap ~logN

m ake_heap~O(3N) sort_heap~O(NlogN)

参数都是 (f,l,less),

push 和 pop 的元素是 *(l-1)

power()

result=power(T t, int n)

O(log n) 次乘法