posts - 134,comments - 22,trackbacks - 0
          <2010年8月>
          25262728293031
          1234567
          891011121314
          15161718192021
          22232425262728
          2930311234

          常用鏈接

          留言簿(4)

          我參與的團(tuán)隊(duì)

          隨筆分類

          隨筆檔案

          收藏夾

          C++ 社區(qū)

          常用網(wǎng)站

          搜索

          •  

          最新評(píng)論

          閱讀排行榜

          評(píng)論排行榜

          STL算法學(xué)習(xí),小結(jié)如下:

          前提:

          下載stl源碼:  http://www.sgi.com/tech/stl/download.html
          打開網(wǎng)頁(yè):     http://www.sgi.com/tech/stl/stl_index.html

          一   函數(shù)對(duì)象: 因?yàn)楹芏嗟乃惴ㄖ卸嗍褂昧撕瘮?shù)對(duì)象


          二元函數(shù)對(duì)象,V1和V2為輸入,V3為結(jié)果

          plus<T>:
            transform(V1.begin(), V1.end(), V2.begin(), V3.begin(),plus<double>());

          其他的二元函數(shù)對(duì)象:minus,multiples,divieds,modulus.

          二元斷言函數(shù)對(duì)象,使用時(shí)需要bind2nd()或bind1st()來綁定比較對(duì)象。

          less<T>:
            find_if(L.begin(), L.end(), bind2nd(less<int>(), 0));

          其他的二元斷言函數(shù):equal_to,notequal_to,greater,greater_equal,less_equal,logical_and,logical_or

          二元邏輯函數(shù)

          binary_negate:
          const char* wptr = find_if(str, str + MAXLEN,
                                     compose2(not2(logical_or<bool>()),
                                              bind2nd(equal_to<char>(), ' '),
                                              bind2nd(equal_to<char>(), '"n')));

          一元函數(shù)對(duì)象

          negate:
          transform(V1.begin(), V1.end(), V2.begin(),
                    negate<int>());

          一元斷定函數(shù)對(duì)象

          logical_not:
            transform(V.begin(), V.end(), V.begin(), logical_not<bool>());

          一元邏輯函數(shù)

          unary_negate:


          二   函數(shù)對(duì)象發(fā)生器:主要用來填充序列。


          產(chǎn)生不重復(fù)的隨機(jī)數(shù):
          // Generate unique random numbers from 0 to mod:
          class URandGen {
            std::set<int> used;
            int limit;
          public:
            URandGen(int lim) : limit(lim) {
              srand(time(0));
            }
            int operator()() {
              while(true) {
                int i = int(rand()) % limit;
                if(used.find(i) == used.end()) {
                  used.insert(i);
                  return i;
                }
              }
            }
          };

          const int sz = 10;
          const int max = 50;
          vector<int> x(sz), y(sz), r(sz);
          //An integer random number generator:
          URandGen urg(max);
          generate_n(x.begin(), sz, urg);

          三 函數(shù)對(duì)象適配器 : 將函數(shù)轉(zhuǎn)化為函數(shù)對(duì)象

          ptr_fun:一般函數(shù)適配器

          一元實(shí)例:
          transform(first, last, first,
                    compose1(negate<double>, ptr_fun(fabs)));

          二元實(shí)例:
          list<char*>::iterator item =
                        find_if(L.begin(), L.end(),
                                not1(binder2nd(ptr_fun(strcmp), "OK")));

          not1:對(duì)一元的斷定函數(shù)對(duì)象取反的適配器。

          not2: 對(duì)二元的斷定函數(shù)對(duì)象取反的適配器。

          mem_fun與mem_fun_ref:類成員函數(shù)的適配器,區(qū)別是一個(gè)需要指針,而另一個(gè)僅需要一般對(duì)象。如下:
          shape是一個(gè)指針變量,則foreach(v.begin(),v.end(),mem_fun(&shape::draw));
          但如果shape是一般的變量,不是指針,則foreach(v.begin(),v.end(),mem_fun_ref(&shape::draw));

          四   算法:

          拷貝:
          copy()
          reverse_copy()
          rotate_copy()
          remove_copy()  拷貝不等于某值的元素到另一個(gè)序列。
          remove_copy_if() 拷貝符合條件的到另一個(gè)序列。

          填充和生成:
          fill()
          fill_n() 填充序列中的n個(gè)元素。
          generate()為序列中的每個(gè)元素調(diào)用gen()函數(shù)。

          排列:
          next_permuttion() 后一個(gè)排列。
          prev_permutation()

          partition() 劃分,將滿足條件的元素移動(dòng)到序列的前面。
          stable_partition()

          查找和替換:
          find()
          binary_search() 在一個(gè)已經(jīng)有順序的序列上查找。
          find_if()
          search() 檢查第二個(gè)序列是否在第一個(gè)序列中出現(xiàn),且順序相同。

          刪除:注意必須調(diào)用erase()來真正刪除
          remove()
          unique()刪除相鄰重復(fù)元素,最好現(xiàn)排序。

          合并序列:
          merge()

          數(shù)值算法:
          accumulate() 對(duì)序列的每個(gè)元素進(jìn)行運(yùn)算后求和。
          transform() 也可以對(duì)每個(gè)元素進(jìn)行運(yùn)算。
          計(jì)數(shù):
          size()總個(gè)數(shù)。
          count()等于某值的元素個(gè)數(shù)。

          adjacent_difference 序列中的后一個(gè)減前與他相鄰的前一個(gè)得到新的序列。

          adiacent_find

          五   所有的算法:

               accumlate iterator 對(duì)標(biāo)志的序列中的元素之和,加到一個(gè)由 init 指定的初始值上。重載的版本不再做加法,而是傳進(jìn)來的二元操作符被應(yīng)用到元素上。
          adjacent_different
          :創(chuàng)建一個(gè)新序列,該序列的每個(gè)新值都代表了當(dāng)前元素與上一個(gè)元素的差。重載版本用指定的二元操作計(jì)算相鄰元素的差。
          adjacent_find
          :在 iterator 對(duì)標(biāo)志的元素范圍內(nèi),查找一對(duì)相鄰的重復(fù)元素,如果找到返回一個(gè) ForwardIterator ,指向這對(duì)元素的第一個(gè)元素。否則返回 last 。重載版本使用輸入的二元操作符代替相等的判斷。
          binary_search
          :在有序序列中查找 value ,如果找到返回 true 。重載的版本使用指定的比較函數(shù)對(duì)象或者函數(shù)指針來判斷相等。
          copy
          :復(fù)制序列。
          copy_backward
          :除了元素以相反的順序被拷貝外,別的和 copy 相同。
          count
          :利用等于操作符,把標(biāo)志范圍類的元素與輸入的值進(jìn)行比較,并返回相等元素的個(gè)數(shù)。
          count_if
          :對(duì)于標(biāo)志范圍類的元素,應(yīng)用輸入的操作符,并返回結(jié)果為 true 的次數(shù)。
          equal
          :如果兩個(gè)序列在范圍內(nèi)的元素都相等,則 equal 返回 true 。重載版本使用輸入的操作符代替了默認(rèn)的等于操作符。
          equal_range
          :返回一對(duì) iterator ,第一個(gè) iterator 表示由 lower_bound 返回的 iterator ,第二個(gè)表示由 upper_bound 返回的 iterator 值。
          fill
          :將輸入的值的拷貝賦給范圍內(nèi)的每個(gè)元素。
          fill_n
          :將輸入的值賦值給 first frist+n 范圍內(nèi)的元素。
          find
          :利用底層元素的等于操作符,對(duì)范圍內(nèi)的元素與輸入的值進(jìn)行比較。當(dāng)匹配時(shí),結(jié)束搜索,返回該元素的一個(gè) InputIterator
          find_if
          :使用輸入的函數(shù)替代了等于操作符執(zhí)行了 find
          find_end
          :在范圍內(nèi)查找“由輸入的另外一個(gè) iterator 對(duì)標(biāo)志的第二個(gè)序列”的最后一次出現(xiàn)。重載版本中使用了用戶輸入的操作符替代等于操作。
          find_first_of
          :在范圍內(nèi)查找“由輸入的另外一個(gè) iterator 對(duì)標(biāo)志的第二個(gè)序列”中的任意一個(gè)元素的第一次出現(xiàn)。重載版本中使用了用戶自定義的操作符。
          for_each
          :依次對(duì)范圍內(nèi)的所有元素執(zhí)行輸入的函數(shù)。
          generate
          :通過對(duì)輸入的函數(shù) gen 的連續(xù)調(diào)用來填充指定的范圍。
          generate_n
          :填充 n 個(gè)元素。
          includes
          :判斷 [first1, last1) 的一個(gè)元素是否被包含在另外一個(gè)序列中。使用底層元素的 <= 操作符,重載版本使用用戶輸入的函數(shù)。
          inner_product
          :對(duì)兩個(gè)序列做內(nèi)積 ( 對(duì)應(yīng)的元素相乘,再求和 ) ,并將內(nèi)積加到一個(gè)輸入的的初始值上。重載版本使用了用戶定義的操作。
          inner_merge
          :合并兩個(gè)排過序的連續(xù)序列,結(jié)果序列覆蓋了兩端范圍,重載版本使用輸入的操作進(jìn)行排序。
          iter_swap
          :交換兩個(gè) ForwardIterator 的值。
          lexicographical_compare
          :比較兩個(gè)序列。重載版本使用了用戶自定義的比較操作。
          lower_bound
          :返回一個(gè) iterator ,它指向在范圍內(nèi)的有序序列中可以插入指定值而不破壞容器順序的第一個(gè)位置。重載函數(shù)使用了自定義的比較操作。
          max
          :返回兩個(gè)元素中的較大的一個(gè),重載版本使用了自定義的比較操作。
          max_element
          :返回一個(gè) iterator ,指出序列中最大的元素。重載版本使用自定義的比較操作。
          min
          :兩個(gè)元素中的較小者。重載版本使用自定義的比較操作。
          min_element
          :類似與 max_element ,不過返回最小的元素。
          merge
          :合并兩個(gè)有序序列,并存放到另外一個(gè)序列中。重載版本使用自定義的比較。
          mismatch
          :并行的比較兩個(gè)序列,指出第一個(gè)不匹配的位置,它返回一對(duì) iterator ,標(biāo)志第一個(gè)不匹配的元素位置。如果都匹配,返回每個(gè)容器的 last 。重載版本使用自定義的比較操作。
          next_permutation
          :取出當(dāng)前范圍內(nèi)的排列,并將其重新排序?yàn)橄乱粋€(gè)排列。重載版本使用自定義的比較操作。
          nth_element
          :將范圍內(nèi)的序列重新排序,使所有小于第 n 個(gè)元素的元素都出現(xiàn)在它前面,而大于它的都出現(xiàn)在后面,重載版本使用了自定義的比較操作。
          partial_sort
          :對(duì)整個(gè)序列做部分排序,被排序元素的個(gè)數(shù)正好可以被放到范圍內(nèi)。重載版本使用自定義的比較操作。
          partial_sort_copy
          :與 partial_sort 相同,除了將經(jīng)過排序的序列復(fù)制到另外一個(gè)容器。
          partial_sum
          :創(chuàng)建一個(gè)新的元素序列,其中每個(gè)元素的值代表了范圍內(nèi)該位置之前所有元素之和。重載版本使用了自定義操作替代加法。
          partition
          :對(duì)范圍內(nèi)元素重新排序,使用輸入的函數(shù),把計(jì)算結(jié)果為 true 的元素都放在結(jié)果為 false 的元素之前。
          prev_permutation
          :取出范圍內(nèi)的序列并將它重新排序?yàn)樯弦粋€(gè)序列。如果不存在上一個(gè)序列則返回 false 。重載版本使用自定義的比較操作。
          random_shuffle
          :對(duì)范圍內(nèi)的元素隨機(jī)調(diào)整次序。重載版本輸入一個(gè)隨機(jī)數(shù)產(chǎn)生操作。
          remove
          :刪除在范圍內(nèi)的所有等于指定的元素,注意,該函數(shù)并不真正刪除元素。內(nèi)置數(shù)組不適合使用 remove remove_if 函數(shù)。
          remove_copy
          :將所有不匹配的元素都復(fù)制到一個(gè)指定容器,返回的 OutputIterator 指向被拷貝的末元素的下一個(gè)位置。
          remove_if
          :刪除所有范圍內(nèi)輸入操作結(jié)果為 true 的元素。
          remove_copy_if
          :將所有不匹配的元素拷貝到一個(gè)指定容器。
          replace
          :將范圍內(nèi)的所有等于 old_value 的元素都用 new_value 替代。
          replace_copy
          :與 replace 類似,不過將結(jié)果寫入另外一個(gè)容器。
          replace_if
          :將范圍內(nèi)的所有操作結(jié)果為 true 的元素用新值替代。
          replace_copy_if
          :類似與 replace_if ,不過將結(jié)果寫入另外一個(gè)容器。
          reverse
          :將范圍內(nèi)元素重新按反序排列。
          reverse_copy
          :類似與 reverse ,不過將結(jié)果寫入另外一個(gè)容器。
          rotate
          :將范圍內(nèi)的元素移到容器末尾,由 middle 指向的元素成為容器第一個(gè)元素。
          rotate_copy
          :類似與 rotate ,不過將結(jié)果寫入另外一個(gè)容器。
          search
          :給出了兩個(gè)范圍,返回一個(gè) iterator ,指向在范圍內(nèi)第一次出現(xiàn)子序列的位置。重載版本使用自定義的比較操作。
          search_n
          :在范圍內(nèi)查找 value 出現(xiàn) n 次的子序列。重載版本使用自定義的比較操作。
          set_difference
          :構(gòu)造一個(gè)排過序的序列,其中的元素出現(xiàn)在第一個(gè)序列中,但是不包含在第二個(gè)序列中。重載版本使用自定義的比較操作。
          set_intersection
          :構(gòu)造一個(gè)排過序的序列,其中的元素在兩個(gè)序列中都存在。重載版本使用自定義的比較操作。
          set_symmetric_difference
          :構(gòu)造一個(gè)排過序的序列,其中的元素在第一個(gè)序列中出現(xiàn),但是不出現(xiàn)在第二個(gè)序列中。重載版本使用自定義的比較操作。
          set_union
          :構(gòu)造一個(gè)排過序的序列,它包含兩個(gè)序列中的所有的不重復(fù)元素。重載版本使用自定義的比較操作。
          sort
          :以升序重新排列范圍內(nèi)的元素,重載版本使用了自定義的比較操作。
          stable_partition
          :與 partition 類似,不過它不保證保留容器中的相對(duì)順序。
          stable_sort
          :類似與 sort ,不過保留相等元素之間的順序關(guān)系。
          swap
          :交換存儲(chǔ)在兩個(gè)對(duì)象中的值。
          swap_range
          :將在范圍內(nèi)的元素與另外一個(gè)序列的元素值進(jìn)行交換。
          transform
          :將輸入的操作作用在范圍內(nèi)的每個(gè)元素上,并產(chǎn)生一個(gè)新的序列。重載版本將操作作用在一對(duì)元素上,另外一個(gè)元素來自輸入的另外一個(gè)序列。結(jié)果輸出到指定的容器。
          unique
          :清除序列中重復(fù)的元素,和 remove 類似,它也不能真正的刪除元素。重載版本使用了自定義的操作。
          unique_copy
          :類似與 unique ,不過它把結(jié)果輸出到另外一個(gè)容器。
          upper_bound
          :返回一個(gè) iterator ,它指向在范圍內(nèi)的有序序列中插入 value 而不破壞容器順序的最后一個(gè)位置,該位置標(biāo)志了一個(gè)大于 value 的值。重載版本使用了輸入的比較操作。
          堆算法: C++ 標(biāo)準(zhǔn)庫(kù)提供的是 max-heap 。一共由以下 4 個(gè)泛型堆算法。
          make_heap
          :把范圍內(nèi)的元素生成一個(gè)堆。重載版本使用自定義的比較操作。
          pop_heap
          :并不是真正的把最大元素從堆中彈出,而是重新排序堆。它把 first last-1 交換,然后重新做成一個(gè)堆。可以使用容器的 back 來訪問被“彈出“的元素或者使用 pop_back 來真正的刪除。重載版本使用自定義的比較操作。
          push_heap
          :假設(shè) first last-1 是一個(gè)有效的堆,要被加入堆的元素在位置 last-1 ,重新生成堆。在指向該函數(shù)前,必須先把元素插入容器后。重載版本使用指定的比較。
          sort_heap
          :對(duì)范圍內(nèi)的序列重新排序,它假設(shè)該序列是個(gè)有序的堆。重載版本使用自定義的比較操作。

          接下來: STL容器學(xué)習(xí)

          posted on 2010-08-27 16:11 何克勤 閱讀(316) 評(píng)論(0)  編輯  收藏 所屬分類: C/C++
          主站蜘蛛池模板: 彝良县| 苏州市| 潞城市| 湘乡市| 淮安市| 惠水县| 新宁县| 遵化市| 茌平县| 自治县| 凉城县| 巴南区| 措勤县| 甘孜| 游戏| 昭苏县| 舟曲县| 科尔| 南投县| 梁河县| 乌海市| 土默特左旗| 阳新县| 句容市| 青海省| 当雄县| 益阳市| 金华市| 和林格尔县| 聂拉木县| 通海县| 修水县| 峨眉山市| 乐清市| 桃园市| 枣强县| 韶关市| 安塞县| 威宁| 新乐市| 如皋市|