CSTL標(biāo)準(zhǔn)容器插入刪除算法的復(fù)雜度(來源flyhorse)

C++STL標(biāo)準(zhǔn)容器插入刪除算法的復(fù)雜度(來源flyhorse)/jenus1/archive/2008/03/29/2227691.aspx1vector內(nèi)部實現(xiàn)：數(shù)組//就是沒有固定大小的數(shù)組，vector直接翻譯是向量的意思支持操作：begin(),〃取首個元素，返回一個iteratorend(),//取末尾(最后一個元素的下一個存儲空間的地址)size(),//就是數(shù)組大小的意思clear(),//清空empty(),〃判斷vector是否為空口〃很神奇的東東，可以和數(shù)組一樣操作〃舉例：vectora;〃定義了一個vector〃然后我們就可以用a[i]來直接訪問a中的第i+1個元素！和數(shù)組的下標(biāo)一模一樣！push_back(),pop_back()〃從末尾插入或彈由insert()O(N)//插入元素，O(n)的復(fù)雜度erase()O(N)〃刪除莫個元素，O(n)的復(fù)雜度可以用于數(shù)組大小不定且空間緊張的情況2deque類似〃雙端隊列，兩頭都支持進由支持push_front()和pop_front()是的精簡版:)〃棧，只支持從末尾進由支持push(),pop(),top()是的精簡版〃單端隊列，就是我們平時所說的隊列，一頭進，另一頭由支持push(),pop(),front(),back()3list內(nèi)部實現(xiàn)：雙向鏈表〃作用和vector差不多，但內(nèi)部是用鏈表實現(xiàn)支持操作：begin(),end(),size(),clear(),empty()push_back(),pop_back()〃從末尾插入或刪除元素push_front(),pop_front()insert()O(1)〃鏈表實現(xiàn)，所以插入和刪除的復(fù)雜度的O(1)erase()O(1)sort()O(nlogn)(logn)找不到返〃不支持［］操作！4set內(nèi)部實現(xiàn)：紅黑樹//Red-BlackTree,一種平衡的二叉排序樹〃又是一個Compare函數(shù)，類似于qsort函數(shù)里的那個Compare函數(shù)，作為紅黑樹在內(nèi)部實現(xiàn)的比較方式insert()O(logn)erase()O(logn)find()O回a.end()lower_bound()O(logn)查找第一個不小于k的元素upper_bound()O(logn)查找第一個大于k的元素equal_range()O(logn)返回pair5multiset允許重復(fù)元素的6map內(nèi)部實現(xiàn):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)***//這個..太猛了，怎么說呢，數(shù)組有一個下標(biāo)，如a[i],這里i是int型的。數(shù)組可以認(rèn)為是從int印射到另一個類型的印射，而map是一個任意的印射，所以i可以是任何類型的！7multimap允許重復(fù)元素，沒有口運算符8priority_queue內(nèi)部實現(xiàn)：堆〃優(yōu)先隊列支持操作：push()O(n)pop()O(n)top()O(1)Seealso:push_heap(),pop_heap()9hashinmap內(nèi)部實現(xiàn)：Hash表〃內(nèi)部用哈希表實現(xiàn)的map重載HashFcn和EqualKey支持操作：insert();0(1)earse();O(1)口；O(1)1.sort()voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast);voidsort(RandomAccessIteratorfirst,RandomAccessIteratorlast,StrictWeakOrderingcomp);區(qū)間[first,last)Quicksort,復(fù)雜度O(nlogn)(n=last-first,平均情況和最壞情況)用法舉例：.從小到大排序(int,double,char,string,etc)constintN=5;intmain(){inta[N]={4,3,2,6,1};stringstr[N]={“TJU"，"ACM,"ICPC"，"abc"，"kkkkk"};sort(a,a+N);sort(str,str+N);return0;).從大到小排序(需要自己寫comp函數(shù))constintN=5;intcmp(inta,intb){returna>b;}intmain(){inta[N]={4,3,2,6,1};sort(a,a+N,cmp);return0;}.對結(jié)構(gòu)體排序structSS{intfirst,second;};intcmp(SSa,SSb){if(a.first!=b.first)returna.first<b.first;returna.second<b.second;}v.s.qsort()inC(平均情況O(nlogn),最壞情況O(nA2))//qsort中的cmp函數(shù)寫起來就麻煩多了！intcmp(constvoid*a,constvoid*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()系歹U:stable_sort(first,last,cmp);//穩(wěn)定排序partial_sort(first,middle,last,cmp);//部分排序?qū)⑶?middle-first)個元素放在[first,middle)中，其余元素位置不定A[12]={7,2,6,11,9,3,12,10,8,4,1,5};partial_sort(A,A+5,A+12);〃結(jié)果是“123451112109876".Detail:Heapsort,O((last-first)*10g(middle-first))sort()系歹U:partial_sort_copy(first,last,result_first,result_last,cmp);〃輸入到另一個容器，不破壞原有序列boolis_sorted(first,last,cmp);〃判斷是否已經(jīng)有序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,5nth_element(A,A+6,A+12);Output:5261437891011122.binary_search()boolbinary_search(ForwardIteratorfirst,Forwarditeratorlast,constLessThanComparable&value);boolbinary_search(ForwardIteratorfirst,Forwarditeratorlast,constT&value,StrictWeakOrderingcomp);在[first,last)中查找value,如果找到返回Ture,否則返回False二分檢索，復(fù)雜度O(log(lastfirst))v.s.bsearch()inCBinary_search()系歹Uitrupper_bound(first,last,value,cmp);//itr指向大于value的第一個值(或容器末尾)itrlower_bound(first,last,value,cmp);//itr指向不小于valude的第一個值(或容器末尾)pairequal_range(first,last,value,cmp);〃找生等于value的值的范圍O(2*log(last-first))intA[N]={1,2,3,3,3,5,8}*upper_bound(A,A+N,3)==5*lower_bound(A,A+N,3)==3make_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:vectorvi;while(scanf("％d',&n)!=EOF){vi.push_back(n);push_heap(vi.begin(),vi.end());}Othersinteresting:next_permutation(first,last,cmp)prev_permutation(first,last,cmp)//bothO(N)min(a,b);max(a,b);min_element(first,last,cmp);max_element(first,last,cmp);Othersinteresting:fill(first,last