STL算法简介

偏执的太偏执、 2022-04-11 05:52 152阅读 0赞

转自  
\[url\]http://www.cppblog.com/mzty/archive/2007/03/14/19819.html\[/url\]  
  
  
\[size=medium\]\[b\]前提:\[/b\]\[/size\]  
下载stl源码：\[url\]http://www.sgi.com/tech/stl/download.html\[/url\]  
打开网页：\[url\]http://www.sgi.com/tech/stl/stl\_index.html\[/url\]  
  
\[color=red\]\[b\]一函数对象：\[/b\]\[/color\] \[b\]因为很多的算法中多使用了函数对象\[/b\]  
二元函数对象，V1和V2为输入，V3为结果

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

其他的二元函数对象：minus,multiples,divieds,modulus.  
  
二元断言函数对象，使用时需要bind2nd（）或bind1st（）来绑定比较对象。

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

其他的二元断言函数： equal\_to,notequal\_to,greater,greater\_equal,less\_equal,logical\_and,logical\_or  
  
二元逻辑函数  
\[b\] binary\_negate:\[/b\]

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

一元函数对象  
  
\[b\] negate：\[/b\]

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

一元断定函数对象  
  
\[b\]logical\_not:\[/b\]

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

一元逻辑函数  
unary\_negate:  
\[color=red\]\[b\]二 函数对象发生器：\[/b\]\[/color\]\[b\]主要用来填充序列。\[/b\]  
  
  
产生不重复的随机数：

// 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);

\[color=red\]\[b\]三 函数对象适配器 \[/b\]\[/color\]： \[b\]将函数转化为函数对象\[/b\]  
  
ptr\_fun:一般函数适配器  
  
一元实例：

transform(first, last, first, compose1(negate<double>, ptr_fun(fabs)));

二元实例：

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

not1：对一元的断定函数对象取反的适配器。  
not2: 对二元的断定函数对象取反的适配器。  
  
mem\_fun与mem\_fun\_ref：类成员函数的适配器,区别是一个需要指针，而另一个仅需要一般对象。如下：  
shape是一个指针变量，则foreach(v.begin(),v.end(),mem\_fun(&shape::draw));  
但如果shape是一般的变量，不是指针，

foreach（v.begin(),v.end(),mem_fun_ref(&shape::draw)）；

\[color=red\]\[b\]四 算法：\[/b\]\[/color\]  
  
\[b\]拷贝：\[/b\]  
\[quote\]copy（）  
reverse\_copy()  
rotate\_copy()  
remove\_copy() 拷贝不等于某值的元素到另一个序列。  
remove\_copy\_if() 拷贝符合条件的到另一个序列。\[/quote\]  
  
\[b\]填充和生成\[/b\]：  
\[quote\]fill()  
fill\_n() 填充序列中的n个元素。  
generate（）为序列中的每个元素调用gen（）函数\[/quote\]。  
  
\[b\]排列：\[/b\]  
\[quote\]next\_permuttion() 后一个排列。  
prev\_permutation()  
  
partition() 划分，将满足条件的元素移动到序列的前面。  
stable\_partition()\[/quote\]  
  
\[b\]查找和替换：\[/b\]  
\[quote\]find（）  
binary\_search() 在一个已经有顺序的序列上查找。  
find\_if()  
search() 检查第二个序列是否在第一个序列中出现，且顺序相同。\[/quote\]  
  
\[b\]删除：注意必须调用erase（）来真正删除\[/b\]  
\[quote\]remove（）  
unique（）删除相邻重复元素，最好现排序。  
\[/quote\]  
  
\[b\]合并序列：\[/b\]  
\[quote\]merge（）\[/quote\]  
  
\[b\]数值算法：\[/b\]  
\[quote\]accumulate（） 对序列的每个元素进行运算后求和。  
transform（） 也可以对每个元素进行运算。\[/quote\]  
  
\[b\]计数：\[/b\]  
\[quote\]size（）总个数。  
count（）等于某值的元素个数。  
adjacent\_difference 序列中的后一个减前与他相邻的前一个得到新的序列。  
adiacent\_find\[/quote\]  
  
  
\[size=medium\]\[b\]五 所有的算法：\[/b\]\[/size\]  
\[b\]accumlate ：\[/b\] iterator 对标志的序列中的元素之和，加到一个由 init 指定的初始值上。重载的版本不再做加法，而是传进来的二元操作符被应用到元素上。  
adjacent\_different ：创建一个新序列，该序列的每个新值都代表了当前元素与上一个元素的差。重载版本用指定的二元操作计算相邻元素的差。  
\[b\]adjacent\_find ：\[/b\]在 iterator 对标志的元素范围内，查找一对相邻的重复元素，如果找到返回一个 ForwardIterator ，指向这对元素的第一个元素。否则返回 last 。重载版本使用输入的二元操作符代替相等的判断。  
\[b\]binary\_search ：\[/b\]在有序序列中查找 value ，如果找到返回 true 。重载的版本使用指定的比较函数对象或者函数指针来判断相等。  
\[b\]copy ：\[/b\]复制序列。  
\[b\]copy\_backward ：\[/b\]除了元素以相反的顺序被拷贝外，别的和 copy 相同。  
\[b\]count ：\[/b\]利用等于操作符，把标志范围类的元素与输入的值进行比较，并返回相等元素的个数。  
\[b\]count\_if ：\[/b\]对于标志范围类的元素，应用输入的操作符，并返回结果为 true 的次数。  
\[b\]equal ：\[/b\]如果两个序列在范围内的元素都相等，则 equal 返回 true 。重载版本使用输入的操作符代替了默认的等于操作符。  
\[b\]equal\_range ：\[/b\]返回一对 iterator ，第一个 iterator 表示由 lower\_bound 返回的 iterator ，第二个表示由 upper\_bound 返回的 iterator 值。  
\[b\]fill ：\[/b\]将输入的值的拷贝赋给范围内的每个元素。  
\[b\]fill\_n ：\[/b\]将输入的值赋值给 first 到 frist+n 范围内的元素。  
\[b\]find ：\[/b\]利用底层元素的等于操作符，对范围内的元素与输入的值进行比较。当匹配时，结束搜索，返回该元素的一个 InputIterator 。  
\[b\]find\_if ：\[/b\]使用输入的函数替代了等于操作符执行了 find 。  
\[b\]find\_end ：\[/b\]在范围内查找“由输入的另外一个 iterator 对标志的第二个序列”的最后一次出现。重载版本中使用了用户输入的操作符替代等于操作。  
find\_first\_of ：在范围内查找“由输入的另外一个 iterator 对标志的第二个序列”中的任意一个元素的第一次出现。重载版本中使用了用户自定义的操作符。  
\[b\]for\_each ：\[/b\]依次对范围内的所有元素执行输入的函数。  
\[b\]generate ：\[/b\]通过对输入的函数 gen 的连续调用来填充指定的范围。  
\[b\]generate\_n ：\[/b\]填充 n 个元素。  
\[b\]includes ：\[/b\]判断 \[first1, last1) 的一个元素是否被包含在另外一个序列中。使用底层元素的 <= 操作符，重载版本使用用户输入的函数。  
\[b\]inner\_product ：\[/b\]对两个序列做内积 ( 对应的元素相乘，再求和 ) ，并将内积加到一个输入的的初始值上。重载版本使用了用户定义的操作。  
\[b\]inner\_merge ：\[/b\]合并两个排过序的连续序列，结果序列覆盖了两端范围，重载版本使用输入的操作进行排序。  
\[b\]iter\_swap ：\[/b\]交换两个 ForwardIterator 的值。  
\[b\]lexicographical\_compare ：\[/b\]比较两个序列。重载版本使用了用户自定义的比较操作。  
\[b\]lower\_bound ：\[/b\]返回一个 iterator ，它指向在范围内的有序序列中可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用了自定义的比较操作。  
\[b\]max ：\[/b\]返回两个元素中的较大的一个，重载版本使用了自定义的比较操作。  
\[b\]max\_element ：\[/b\]返回一个 iterator ，指出序列中最大的元素。重载版本使用自定义的比较操作。  
\[b\] min ：\[/b\]两个元素中的较小者。重载版本使用自定义的比较操作。  
\[b\]min\_element ：\[/b\]类似与 max\_element ，不过返回最小的元素。  
\[b\]merge ：\[/b\]合并两个有序序列，并存放到另外一个序列中。重载版本使用自定义的比较。  
\[b\]mismatch ：\[/b\]并行的比较两个序列，指出第一个不匹配的位置，它返回一对 iterator ，标志第一个不匹配的元素位置。如果都匹配，返回每个容器的 last 。重载版本使用自定义的比较操作。  
\[b\]next\_permutation ：\[/b\]取出当前范围内的排列，并将其重新排序为下一个排列。重载版本使用自定义的比较操作。  
\[b\]nth\_element ：\[/b\]将范围内的序列重新排序，使所有小于第 n 个元素的元素都出现在它前面，而大于它的都出现在后面，重载版本使用了自定义的比较操作。  
\[b\]partial\_sort ：\[/b\]对整个序列做部分排序，被排序元素的个数正好可以被放到范围内。重载版本使用自定义的比较操作。  
\[b\]partial\_sort\_copy ：\[/b\]与 partial\_sort 相同，除了将经过排序的序列复制到另外一个容器。  
\[b\]partial\_sum ：\[/b\]创建一个新的元素序列，其中每个元素的值代表了范围内该位置之前所有元素之和。重载版本使用了自定义操作替代加法。  
\[b\]partition ：\[/b\]对范围内元素重新排序，使用输入的函数，把计算结果为 true 的元素都放在结果为 false 的元素之前。  
\[b\]prev\_permutation ：\[/b\]取出范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回 false 。重载版本使用自定义的比较操作。  
\[b\] random\_shuffle ：\[/b\]对范围内的元素随机调整次序。重载版本输入一个随机数产生操作。  
\[b\]remove ：\[/b\]删除在范围内的所有等于指定的元素，注意，该函数并不真正删除元素。内置数组不适合使用 remove 和 remove\_if 函数。  
\[b\]remove\_copy ：\[/b\]将所有不匹配的元素都复制到一个指定容器，返回的 OutputIterator 指向被拷贝的末元素的下一个位置。  
\[b\]remove\_if ：\[/b\]删除所有范围内输入操作结果为 true 的元素。  
\[b\]remove\_copy\_if ：\[/b\]将所有不匹配的元素拷贝到一个指定容器。  
\[b\]replace ：\[/b\]将范围内的所有等于 old\_value 的元素都用 new\_value 替代。  
\[b\]replace\_copy ：\[/b\]与 replace 类似，不过将结果写入另外一个容器。  
\[b\]replace\_if ：\[/b\]将范围内的所有操作结果为 true 的元素用新值替代。  
\[b\]replace\_copy\_if ：\[/b\]类似与 replace\_if ，不过将结果写入另外一个容器。  
\[b\]reverse ：\[/b\]将范围内元素重新按反序排列。  
\[b\]reverse\_copy \[/b\]：类似与 reverse ，不过将结果写入另外一个容器。  
\[b\]rotate \[/b\]：将范围内的元素移到容器末尾，由 middle 指向的元素成为容器第一个元素。  
\[b\]rotate\_copy ：\[/b\]类似与 rotate ，不过将结果写入另外一个容器。  
\[b\]search ：\[/b\]给出了两个范围，返回一个 iterator ，指向在范围内第一次出现子序列的位置。重载版本使用自定义的比较操作。  
\[b\]search\_n ：\[/b\]在范围内查找 value 出现 n 次的子序列。重载版本使用自定义的比较操作。  
\[b\]set\_difference ：\[/b\]构造一个排过序的序列，其中的元素出现在第一个序列中，但是不包含在第二个序列中。重载版本使用自定义的比较操作。  
\[b\]set\_intersection ：\[/b\]构造一个排过序的序列，其中的元素在两个序列中都存在。重载版本使用自定义的比较操作。  
\[b\]set\_symmetric\_difference ：\[/b\]构造一个排过序的序列，其中的元素在第一个序列中出现，但是不出现在第二个序列中。重载版本使用自定义的比较操作。  
\[b\]set\_union ：\[/b\]构造一个排过序的序列，它包含两个序列中的所有的不重复元素。重载版本使用自定义的比较操作。  
\[b\]sort ：\[/b\]以升序重新排列范围内的元素，重载版本使用了自定义的比较操作。  
\[b\]stable\_partition ：\[/b\]与 partition 类似，不过它不保证保留容器中的相对顺序。  
\[b\]stable\_sort ：\[/b\]类似与 sort ，不过保留相等元素之间的顺序关系。  
\[b\]swap ：\[/b\]交换存储在两个对象中的值。  
\[b\]swap\_range ：\[/b\]将在范围内的元素与另外一个序列的元素值进行交换。  
\[b\]transform ：\[/b\]将输入的操作作用在范围内的每个元素上，并产生一个新的序列。重载版本将操作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定的容器。  
\[b\]unique ：\[/b\]清除序列中重复的元素，和 remove 类似，它也不能真正的删除元素。重载版本使用了自定义的操作。  
\[b\]unique\_copy ：\[/b\]类似与 unique ，不过它把结果输出到另外一个容器。  
\[b\]upper\_bound ：\[/b\]返回一个 iterator ，它指向在范围内的有序序列中插入 value 而不破坏容器顺序的最后一个位置，该位置标志了一个大于 value 的值。重载版本使用了输入的比较操作。  
堆算法： C++ 标准库提供的是 max-heap 。一共由以下 4 个泛型堆算法。  
\[b\]make\_heap ：\[/b\]把范围内的元素生成一个堆。重载版本使用自定义的比较操作。  
\[b\]pop\_heap ：\[/b\]并不是真正的把最大元素从堆中弹出，而是重新排序堆。它把 first 和 last-1 交换，然后重新做成一个堆。可以使用容器的 back 来访问被“弹出“的元素或者使用 pop\_back 来真正的删除。重载版本使用自定义的比较操作。  
\[b\]push\_heap ：\[/b\]假设 first 到 last-1 是一个有效的堆，要被加入堆的元素在位置 last-1 ，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较。  
\[b\]sort\_heap ：\[/b\]对范围内的序列重新排序，它假设该序列是个有序的堆。重载版本使用自定义的比较操作。