在模板参数,传递类名,在 ( 离散 ) 函数参数中,使用函数名 ( myStruct(); 或 myFunc )
内置 <functional> : greater <T>, less<T>, greater_equal<T>, less_equal<T>, equal_to<T>, not_equal_to<T>
自定义: struct strlt{ // 字典排序
bool operator ()(const char* a, const char*b) const{
return strcmp(a,b)<0;
}
};
关联型容器
容器
|
头文件
|
|
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) 次乘法
|