c++stl各封装容器的操作复杂度，转载

http://blog.csdn.net/jenus1/archive/2008/03/29/2227691.aspx

1 vector

内部实现: 数组 // 就是没有固定大小的数组，vector直接翻译是向量的意思

支持操作:

begin(), //取首个元素，返回一个iterator

end(), //取末尾（最后一个元素的下一个存储空间的地址）

size(), //就是数组大小的意思

clear(), //清空

empty(), //判断vector是否为空

[] //很神奇的东东，可以和数组一样操作

//举例： vector a; //定义了一个vector

//然后我们就可以用a[i]来直接访问a中的第i + 1个元素！和数组的下标一模一样！

push_back(), pop_back() //从末尾插入或弹出

insert() O(N) //插入元素，O(n)的复杂度

erase() O(N) //删除某个元素，O(n)的复杂度

可以用于数组大小不定且空间紧张的情况

2 deque

类似 //双端队列，两头都支持进出

支持push_front()和pop_front()

是的精简版:) //栈，只支持从末尾进出

支持push(), pop(), top()

是的精简版 //单端队列，就是我们平时所说的队列，一头进，另一头出

支持push(), pop(), front(), back()

3 list

内部实现: 双向链表 //作用和vector差不多，但内部是用链表实现

支持操作:

begin(), end(), size(), clear(), empty()

push_back(), pop_back() //从末尾插入或删除元素

push_front(), pop_front()

insert() O(1) //链表实现，所以插入和删除的复杂度的O(1)

erase() O(1)

sort() O(nlogn)(logn) 找不到返

//不支持[ ]操作！

4 set

内部实现: 红黑树 //Red-Black Tree，一种平衡的二叉排序树

//又是一个Compare函数，类似于qsort函数里的那个Compare函数，作为红黑树在内部实现的比较方式

insert() O(logn)

erase() O(logn)

find() O回a.end()

lower_bound() O(logn) 查找第一个不小于k的元素

upper_bound() O(logn) 查找第一个大于k的元素

equal_range() O(logn) 返回pair

5 multiset 允许重复元素的

6 map 内部实现: pair组成的红黑树 //map中文意思：印射！！

//就是很多pair 组成一个红黑树

insert() O(logn)

erase() O(logn)

find() O(logn) 找不到返回a.end()

lower_bound() O(logn) 查找第一个不小于k的元素

upper_bound() O(logn) 查找第一个大于k的元素

equal_range() O(logn) 返回pair

[key]运算符 O(logn) *** //这个..太猛了，怎么说呢，数组有一个下标，如a[i],这里i是int型的。数组可以认为是从int印射到另一个类型的印射，而map是一个任意的印射，所以i可以是任何类型的！

7 multimap 允许重复元素, 没有[]运算符

8 priority_queue

内部实现: 堆 //优先队列

支持操作:

push() O(n)

pop() O(n)

top() O(1)

See also: push_heap(), pop_heap() … in

9 hash_map

内部实现: Hash表//内部用哈希表实现的map

重载HashFcn和EqualKey

支持操作:

insert(); O(1)

earse(); O(1)

[ ]; O(1)

1.sort()

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

区间[first,last)

Quicksort,复杂度O(nlogn)

(n=last-first,平均情况和最坏情况)

用法举例:

1.从小到大排序(int, double, char, string, etc)

const int N = 5;

int main()

{

int a[N] = {4,3,2,6,1};

string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};

sort(a,a+N);

sort(str,str+N);

return 0;

}

2.从大到小排序（需要自己写comp函数)

const int N = 5;

int cmp(int a,int b) {return a > b;}

int main()

{

int a[N] = {4,3,2,6,1};

sort(a,a+N,cmp);

return 0;

}

3. 对结构体排序

struct SS {int first,second;};

int cmp(SS a,SS b) {

if (a.first != b.first) return a.first < b.first;

return a.second < b.second;

}

v.s. qsort() in C (平均情况O(nlogn)，最坏情况O(n^2)) //qsort中的cmp函数写起来就麻烦多了！

int cmp(const void *a,const void *b) {

if (((SS*)a)->first != ((SS*)b)->first)

return ((SS*)a)->first – ((SS*)b)->first;

return ((SS*)a)->second – ((SS*)b)->second;

}

qsort(array,n,sizeof(array[0]),cmp);

sort()系列:

stable_sort(first,last,cmp); //稳定排序

partial_sort(first,middle,last,cmp);//部分排序

将前(middle-first)个元素放在[first,middle)中，其余元素位置不定

e.g.

int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};

partial_sort(A, A + 5, A + 12);

// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".

Detail: Heapsort ,

O((last-first)*log(middle-first))

sort()系列:

partial_sort_copy(first, last, result_first, result_last, cmp);

//输入到另一个容器，不破坏原有序列

bool is_sorted(first, last, cmp);

//判断是否已经有序

nth_element(first, nth, last, cmp);

//使[first,nth)的元素不大于[nth,last), O(N)

e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5

nth_element(A,A+6,A+12);

Output: 5 2 6 1 4 3 7 8 9 10 11 12

2. binary_search()

bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);

在[first,last)中查找value，如果找到返回Ture,否则返回False

二分检索，复杂度O(log(last-first))

v.s. bsearch() in C

Binary_search()系列

itr upper_bound(first, last, value, cmp);

//itr指向大于value的第一个值(或容器末尾)

itr lower_bound(first, last, value, cmp);

//itr指向不小于valude的第一个值(或容器末尾)

pair equal_range(first, last, value, cmp);

//找出等于value的值的范围 O(2*log(last – first))

int A[N] = {1,2,3,3,3,5,8}

*upper_bound(A,A+N,3) == 5

*lower_bound(A,A+N,3) == 3

make_heap(first,last,cmp) O(n)

push_heap(first,last,cmp) O(logn)

pop_heap(first,last,cmp) O(logn)

is_heap(first,last,cmp) O(n)

e.g:

vector vi;

while (scanf(“%d”,&n) != EOF) {

vi.push_back(n);

push_heap(vi.begin(),vi.end());

}

Others interesting:

next_permutation(first, last, cmp)

prev_permutation(first, last, cmp)

//both O(N)

min(a,b);

max(a,b);

min_element(first, last, cmp);

max_element(first, last, cmp);

Others interesting:

fill(first, last, value)

reverse(first, last)

rotate(first,middle,last);

itr unique(first, last);

//返回指针指向合并后的末尾处

random_shuffle(first, last, rand)

Some Others:

More container: Rope, Slist, Bitset …

More about iterator

Memory allocation

Function object

1 vector

内部实现: 数组 // 就是没有固定大小的数组，vector直接翻译是向量的意思

支持操作:

begin(), //取首个元素，返回一个iterator

end(), //取末尾（最后一个元素的下一个存储空间的地址）

size(), //就是数组大小的意思

clear(), //清空

empty(), //判断vector是否为空

[] //很神奇的东东，可以和数组一样操作

//举例： vector a; //定义了一个vector

//然后我们就可以用a[i]来直接访问a中的第i + 1个元素！和数组的下标一模一样！

push_back(), pop_back() //从末尾插入或弹出

insert() O(N) //插入元素，O(n)的复杂度

erase() O(N) //删除某个元素，O(n)的复杂度

可以用于数组大小不定且空间紧张的情况

2 deque

类似 //双端队列，两头都支持进出

支持push_front()和pop_front()

是的精简版:) //栈，只支持从末尾进出

支持push(), pop(), top()

是的精简版 //单端队列，就是我们平时所说的队列，一头进，另一头出

支持push(), pop(), front(), back()

3 list

内部实现: 双向链表 //作用和vector差不多，但内部是用链表实现

支持操作:

begin(), end(), size(), clear(), empty()

push_back(), pop_back() //从末尾插入或删除元素

push_front(), pop_front()

insert() O(1) //链表实现，所以插入和删除的复杂度的O(1)

erase() O(1)

sort() O(nlogn)(logn) 找不到返

//不支持[ ]操作！

4 set

内部实现: 红黑树 //Red-Black Tree，一种平衡的二叉排序树

//又是一个Compare函数，类似于qsort函数里的那个Compare函数，作为红黑树在内部实现的比较方式

insert() O(logn)

erase() O(logn)

find() O回a.end()

lower_bound() O(logn) 查找第一个不小于k的元素

upper_bound() O(logn) 查找第一个大于k的元素

equal_range() O(logn) 返回pair

5 multiset 允许重复元素的

6 map 内部实现: pair组成的红黑树 //map中文意思：印射！！

//就是很多pair 组成一个红黑树

insert() O(logn)

erase() O(logn)

find() O(logn) 找不到返回a.end()

lower_bound() O(logn) 查找第一个不小于k的元素

upper_bound() O(logn) 查找第一个大于k的元素

equal_range() O(logn) 返回pair

[key]运算符 O(logn) *** //这个..太猛了，怎么说呢，数组有一个下标，如a[i],这里i是int型的。数组可以认为是从int印射到另一个类型的印射，而map是一个任意的印射，所以i可以是任何类型的！

7 multimap 允许重复元素, 没有[]运算符

8 priority_queue

内部实现: 堆 //优先队列

支持操作:

push() O(n)

pop() O(n)

top() O(1)

See also: push_heap(), pop_heap() … in

9 hash_map

内部实现: Hash表//内部用哈希表实现的map

重载HashFcn和EqualKey

支持操作:

insert(); O(1)

earse(); O(1)

[ ]; O(1)

1.sort()

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

区间[first,last)

Quicksort,复杂度O(nlogn)

(n=last-first,平均情况和最坏情况)

用法举例:

1.从小到大排序(int, double, char, string, etc)

const int N = 5;

int main()

{

int a[N] = {4,3,2,6,1};

string str[N] = {“TJU”,”ACM”,”ICPC”,”abc”,”kkkkk”};

sort(a,a+N);

sort(str,str+N);

return 0;

}

2.从大到小排序（需要自己写comp函数)

const int N = 5;

int cmp(int a,int b) {return a > b;}

int main()

{

int a[N] = {4,3,2,6,1};

sort(a,a+N,cmp);

return 0;

}

3. 对结构体排序

struct SS {int first,second;};

int cmp(SS a,SS b) {

if (a.first != b.first) return a.first < b.first;

return a.second < b.second;

}

v.s. qsort() in C (平均情况O(nlogn)，最坏情况O(n^2)) //qsort中的cmp函数写起来就麻烦多了！

int cmp(const void *a,const void *b) {

if (((SS*)a)->first != ((SS*)b)->first)

return ((SS*)a)->first – ((SS*)b)->first;

return ((SS*)a)->second – ((SS*)b)->second;

}

qsort(array,n,sizeof(array[0]),cmp);

sort()系列:

stable_sort(first,last,cmp); //稳定排序

partial_sort(first,middle,last,cmp);//部分排序

将前(middle-first)个元素放在[first,middle)中，其余元素位置不定

e.g.

int A[12] = {7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5};

partial_sort(A, A + 5, A + 12);

// 结果是 "1 2 3 4 5 11 12 10 9 8 7 6".

Detail: Heapsort ,

O((last-first)*log(middle-first))

sort()系列:

partial_sort_copy(first, last, result_first, result_last, cmp);

//输入到另一个容器，不破坏原有序列

bool is_sorted(first, last, cmp);

//判断是否已经有序

nth_element(first, nth, last, cmp);

//使[first,nth)的元素不大于[nth,last), O(N)

e.g. input: 7, 2, 6, 11, 9, 3, 12, 10, 8, 4, 1, 5

nth_element(A,A+6,A+12);

Output: 5 2 6 1 4 3 7 8 9 10 11 12

2. binary_search()

bool binary_search(ForwardIterator first, ForwardIterator last, const LessThanComparable& value);

bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp);

在[first,last)中查找value，如果找到返回Ture,否则返回False

二分检索，复杂度O(log(last-first))

v.s. bsearch() in C

Binary_search()系列

itr upper_bound(first, last, value, cmp);

//itr指向大于value的第一个值(或容器末尾)

itr lower_bound(first, last, value, cmp);

//itr指向不小于valude的第一个值(或容器末尾)

pair equal_range(first, last, value, cmp);

//找出等于value的值的范围 O(2*log(last – first))

int A[N] = {1,2,3,3,3,5,8}

*upper_bound(A,A+N,3) == 5

*lower_bound(A,A+N,3) == 3

make_heap(first,last,cmp) O(n)

push_heap(first,last,cmp) O(logn)

pop_heap(first,last,cmp) O(logn)

is_heap(first,last,cmp) O(n)

e.g:

vector vi;

while (scanf(“%d”,&n) != EOF) {

vi.push_back(n);

push_heap(vi.begin(),vi.end());

}

Others interesting:

next_permutation(first, last, cmp)

prev_permutation(first, last, cmp)

//both O(N)

min(a,b);

max(a,b);

min_element(first, last, cmp);

max_element(first, last, cmp);

Others interesting:

fill(first, last, value)

reverse(first, last)

rotate(first,middle,last);

itr unique(first, last);

//返回指针指向合并后的末尾处

random_shuffle(first, last, rand)

Some Others:

More container: Rope, Slist, Bitset …

More about iterator

Memory allocation

Function object