閱讀504 返回首頁    go 阿裏雲 go 技術社區[雲棲]

STL中Algorithm

來源：沒有代碼的日子

toupper,tolower
地球人都知道 C++ 的 string 沒有 toupper ，好在這不是個大問題，因為我們有 STL 算法：

string s("heLLo");
transform(s.begin(), s.end(), s.begin(), ::toupper);
cout << s << endl;
transform(s.begin(), s.end(), s.begin(), ::tolower);
cout << s << endl;

當然，我知道很多人希望的是 s.to_upper() ，但是對於一個這麼通用的 basic_string 來說，的確沒辦法把這些專有的方法放進來。如果你用 boost stringalgo ，那當然不在話下，你也就不需要讀這篇文章了。

------------------------------------------------------------------------
trim
我們還知道 string 沒有 trim ，不過自力更生也不困難，比 toupper 來的還要簡單：

    string s("   hello   ");
    s.erase(0, s.find_first_not_of(" \n"));
    cout << s << endl;
    s.erase(s.find_last_not_of(' ') + 1);
    cout << s << endl;

注意由於 find_first_not_of 和 find_last_not_of 都可以接受字符串，這個時候它們尋找該字符串中所有字符的 absence ，所以你可以一次 trim 掉多種字符。

-----------------------------------------------------------------------
erase
string 本身的 erase 還是不錯的，但是隻能 erase 連續字符，如果要拿掉一個字符串裏麵所有的某個字符呢？用 STL 的 erase + remove_if 就可以了，注意光 remove_if 是不行的。

    string s("   hello, world. say bye   ");
    s.erase(remove_if(s.begin(),s.end(),
        bind2nd(equal_to<char>(), ' ')),
    s.end());

上麵的這段會拿掉所有的空格，於是得到 hello,world.saybye。

-----------------------------------------------------------------------
replace
string 本身提供了 replace ，不過並不是麵向字符串的，譬如我們最常用的把一個 substr 換成另一個 substr 的操作，就要做一點小組合：

    string s("hello, world");
    string sub("ello, ");
    s.replace(s.find(sub), sub.size(), "appy ");
    cout << s << endl;

輸出為 happy world。注意原來的那個 substr 和替換的 substr 並不一定要一樣長。

-----------------------------------------------------------------------
startwith, endwith
這兩個可真常用，不過如果你仔細看看 string 的接口，就會發現其實沒必要專門提供這兩個方法，已經有的接口可以幹得很好：

    string s("hello, world");
    string head("hello");
    string tail("ld");
    bool startwith = s.compare(0, head.size(), head) == 0;
    cout << boolalpha << startwith << endl;
    bool endwith = s.compare(s.size() - tail.size(), tail.size(), tail) == 0;
    cout << boolalpha << endwith << endl;

當然了，沒有 s.startwith("hello") 這樣方便。

------------------------------------------------------------------------
toint, todouble, tobool...
這也是老生常談了，無論是 C 的方法還是 C++ 的方法都可以，各有特色：

    string s("123");
    int i = atoi(s.c_str());
    cout << i << endl;
   
    int ii;
    stringstream(s) >> ii;
    cout << ii << endl;
   
    string sd("12.3");
    double d = atof(sd.c_str());
    cout << d << endl;
   
    double dd;
    stringstream(sd) >> dd;
    cout << dd << endl;
   
    string sb("true");
    bool b;
    stringstream(sb) >> boolalpha >> b;
    cout << boolalpha << b << endl;

C 的方法很簡潔，而且賦值與轉換在一句裏麵完成，而 C++ 的方法很通用。

------------------------------------------------------------------------
split
這可是件麻煩事，我們最希望的是這樣一個接口： s.split(vect, ',') 。用 STL 算法來做有一定難度，我們可以從簡單的開始，如果分隔符是空格、tab 和回車之類，那麼這樣就夠了：

    string s("hello world, bye.");
    vector<string> vect;
    vect.assign(
        istream_iterator<string>(stringstream(s)),
        istream_iterator<string>()
    );

不過要注意，如果 s 很大，那麼會有效率上的隱憂，因為 stringstream 會 copy 一份 string 給自己用。

------------------------------------------------------------------------
concat
把一個裝有 string 的容器裏麵所有的 string 連接起來，怎麼做？希望你不要說是 hand code 循環，這樣做不是更好？

    vector<string> vect;
    vect.push_back("hello");
    vect.push_back(", ");
    vect.push_back("world");
   
    cout << accumulate(vect.begin(), vect.end(), string(""));

不過在效率上比較有優化餘地。

-------------------------------------------------------------------------

reverse
其實我比較懷疑有什麼人需要真的去 reverse 一個 string ，不過做這件事情的確是很容易：

  std::reverse(s.begin(), s.end());

上麵是原地反轉的方法，如果需要反轉到別的 string 裏麵，一樣簡單：

  s1.assign(s.rbegin(), s.rend());

效率也相當理想。

-------------------------------------------------------------------------

解析文件擴展名
字數多點的寫法：

    std::string filename("hello.exe");

    std::string::size_type pos = filename.rfind('.');
    std::string ext = filename.substr(pos == std::string::npos ? filename.length() : pos + 1);

不過兩行，合並成一行呢？也不是不可以：

    std::string ext = filename.substr(filename.rfind('.') == std::string::npos ? filename.length() : filename.rfind('.') + 1);

我知道，rfind 執行了兩次。不過第一，你可以希望編譯器把它優化掉，其次，擴展名一般都很短，即便多執行一次，區別應該是相當微小。

STL 算法
distance
很多時候我們希望在一個 vector ，或者 list ，或者什麼其他東西裏麵，找到一個值在哪個位置，這個時候 find 幫不上忙，而有人就轉而求助手寫循環了，而且是原始的手寫循環：

for ( int i = 0; i < vect.size(); ++i)
    if ( vect[i] == value ) break;

如果編譯器把 i 看作 for scope 的一部分，你還要把 i 的聲明拿出去。真的需要這樣麼？看看這個：

    int dist =
        distance(col.begin(),
            find(col.begin(), col.end(), 5));

其中 col 可以是很多容器，list, vector, deque... 當然這是你確定 5 就在 col 裏麵的情形，如果你不確定，那就加點判斷：

    int dist;
    list<int>::iterator pos = find(col.begin(), col.end(), 5);
    if ( pos != col.end() )
        dist = distance(col.begin(), pos);

我想這還是比手寫循環來的好些吧。

--------------------------------------------------------------------------
max, min
這是有直接的算法支持的，當然複雜度是 O(n)，用於未排序容器，如果是排序容器...老兄，那還需要什麼算法麼？

max_element(col.begin(), col.end());
min_element(col.begin(), col.end());

注意返回的是 iterator ，如果你關心的隻是值，那麼好：

*max_element(col.begin(), col.end());
*min_element(col.begin(), col.end());

max_element 和 min_element 都默認用 less 來排序，它們也都接受一個 binary predicate ，如果你足夠無聊，甚至可以把 max_element 當成 min_element 來用，或者反之：

*max_element(col.begin(), col.end(), greater<int>()); // 返回最小值！
*min_element(col.begin(), col.end(), greater<int>()); // 返回最大值

當然它們的本意不是這個，而是讓你能在比較特殊的情況下使用它們，例如，你要比較的是每個元素的某個成員，或者成員函數的返回值。例如：

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <boost/bind.hpp>

using namespace boost;
using namespace std;

struct Person
{
    Person(const string& _name, int _age)
        : name(_name), age(_age)
    {}
    int age;
    string name;
};

int main()
{
    list<Person> col;
    list<Person>::iterator pos;

    col.push_back(Person("Tom", 10));
    col.push_back(Person("Jerry", 12));
    col.push_back(Person("Mickey", 9));

    Person eldest =
        *max_element(col.begin(), col.end(),
            bind(&Person::age, _1) < bind(&Person::age, _2));//>=1.33
   
    cout << eldest.name;
}

輸出是 Jerry ，這裏用了 boost.bind ，原諒我不知道用 bind2nd, mem_fun 怎麼寫，我也不想知道...

-------------------------------------------------------------------------
copy_if
沒錯，STL 裏麵壓根沒有 copy_if ，這就是為什麼我們需要這個：

template<typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(
    InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{
    while (begin != end)
    {
        if (p(*begin))*destBegin++ = *begin;
        ++begin;
    }
    return destBegin;
}

把它放在自己的工具箱裏，是一個明智的選擇。

------------------------------------------------------------------------
慣用手法：erase(iter++)
如果你要去除一個 list 中的某些元素，那可千萬小心：（下麵的代碼是錯的！！！）

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    for ( std::list<int>::iterator iter = lst.begin();
          iter != lst.end(); ++iter)
        if ( *iter % 2 == 0 )
            lst.erase(iter);
           
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

當 iter 被 erase 掉的時候，它已經失效，而後麵卻還會做 ++iter ，其行為無可預期！如果你不想動用 remove_if ，那麼唯一的選擇就是：

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    for ( std::list<int>::iterator iter = lst.begin();
          iter != lst.end(); )
        if ( *iter % 2 == 0 )
            lst.erase(iter++);
        else
            ++iter;
          
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

但是上麵的代碼不能用於 vector, string 和 deque ，因為對於這些容器， erase 不光令 iter 失效，還令 iter 之後的所有 iterator 失效！

-------------------------------------------------------------------------
erase(remove...) 慣用手法
上麵的循環如此難寫，如此不通用，如此不容易理解，還是用 STL 算法來的好，但是注意，光 remove_if 是沒用的，必須使用 erase(remove...) 慣用手法：

#include <iostream>
#include <algorithm>
#include <iterator>
#include <list>
#include <functional>
#include <boost/bind.hpp>

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::list<int> lst(arr, arr + 10);

    lst.erase(remove_if(lst.begin(), lst.end(),
        boost::bind(std::modulus<int>(), _1, 2) == 0),
        lst.end()
    );
          
    std::copy(lst.begin(), lst.end(),
        std::ostream_iterator<int>(std::cout, " "));
}

當然，這裏借助了 boost.bind ，讓我們不用多寫一個沒用的 functor 。

簡單常識——關於stream
從文件中讀入一行

簡單，這樣就行了：

ifstream ifs("input.txt");
char buf[1000];

ifs.getline(buf, sizeof buf);

string input(buf);

當然，這樣沒有錯，但是包含不必要的繁瑣和拷貝，況且，如果一行超過1000個字符，就必須用一個循環和更麻煩的緩衝管理。下麵這樣豈不是更簡單？

string input;
input.reserve(1000);
ifstream ifs("input.txt");
getline(ifs, input);

不僅簡單，而且安全，因為全局函數 getline 會幫你處理緩衝區用完之類的麻煩，如果你不希望空間分配發生的太頻繁，隻需要多 reserve 一點空間。

這就是“簡單常識”的含義，很多東西已經在那裏，隻是我一直沒去用。

---------------------------------------------------------------------------

一次把整個文件讀入一個 string

我希望你的答案不要是這樣：

string input;
while( !ifs.eof() )
{
    string line;
    getline(ifs, line);
    input.append(line).append(1, '\n');
}

當然了，沒有錯，它能工作，但是下麵的辦法是不是更加符合 C++ 的精神呢？

string input(
    istreambuf_iterator<char>(instream.rdbuf()),
    istreambuf_iterator<char>()
);

同樣，事先分配空間對於性能可能有潛在的好處：

string input;
input.reserve(10000);
input.assign(
    istreambuf_iterator<char>(ifs.rdbuf()),
    istreambuf_iterator<char>()
);

很簡單，不是麼？但是這些卻是我們經常忽略的事實。
補充一下，這樣幹是有問題的：

    string input;
    input.assign(
        istream_iterator<char>(ifs),
        istream_iterator<char>()
    );

因為它會忽略所有的分隔符，你會得到一個純“字符”的字符串。最後，如果你隻是想把一個文件的內容讀到另一個流，那沒有比這更快的了：

    fstream fs("temp.txt");
    cout << fs.rdbuf();

因此，如果你要手工 copy 文件，這是最好的（如果不用操作係統的 API）：

   ifstream ifs("in.txt");
   ofstream ofs("out.txt");
   ofs << in.rdbuf();

-------------------------------------------------------------------------

open 一個文件的那些選項

ios::in     Open file for reading
ios::out    Open file for writing
ios::ate    Initial position: end of file
ios::app    Every output is appended at the end of file
ios::trunc  If the file already existed it is erased
ios::binary Binary mode

-------------------------------------------------------------------------

還有 ios 的那些 flag

flag effect if set
ios_base::boolalpha input/output bool objects as alphabetic names (true, false).
ios_base::dec input/output integer in decimal base format.
ios_base::fixed output floating point values in fixed-point notation.
ios_base::hex input/output integer in hexadecimal base format.
ios_base::internal the output is filled at an internal point enlarging the output up to the field width.
ios_base::left the output is filled at the end enlarging the output up to the field width.
ios_base::oct input/output integer in octal base format.
ios_base::right the output is filled at the beginning enlarging the output up to the field width.
ios_base::scientific output floating-point values in scientific notation.
ios_base::showbase output integer values preceded by the numeric base.
ios_base::showpoint output floating-point values including always the decimal point.
ios_base::showpos output non-negative numeric preceded by a plus sign (+).
ios_base::skipws skip leading whitespaces on certain input operations.
ios_base::unitbuf flush output after each inserting operation.
ios_base::uppercase output uppercase letters replacing certain lowercase letters.

There are also defined three other constants that can be used as masks:

constant value
ios_base::adjustfield left | right | internal
ios_base::basefield dec | oct | hex
ios_base::floatfield scientific | fixed

--------------------------------------------------------------------------

用我想要的分隔符來解析一個字符串，以及從流中讀取數據

這曾經是一個需要不少麻煩的話題，由於其常用而顯得尤其麻煩，但是其實 getline 可以做得不錯：

    getline(cin, s, ';');   
    while ( s != "quit" )
    {
        cout << s << endl;
        getline(cin, s, ';');
    }

簡單吧？不過注意，由於這個時候 getline 隻把 ; 作為分隔符，所以你需要用 ;quit; 來結束輸入，否則 getline 會把前後的空格和回車都讀入 s ，當然，這個問題可以在代碼裏麵解決。

同樣，對於簡單的字符串解析，我們是不大需要動用什麼 Tokenizer 之類的東西了：

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string s("hello,world, this is a sentence; and a word, end.");
    stringstream ss(s);
   
    for ( ; ; )
    {
        string token;
        getline(ss, token, ',');
        if ( ss.fail() ) break;
       
        cout << token << endl;
    }
}

輸出：

hello
world
 this is a sentence; and a word
 end.

很漂亮不是麼？不過這麼幹的缺陷在於，隻有一個字符可以作為分隔符。

--------------------------------------------------------------------------

把原本輸出到屏幕的東西輸出到文件，不用到處去把 cout 改成 fs

#include <iostream>
#include <fstream>
using namespace std;
int main()
{    
    ofstream outf("out.txt"); 
    streambuf *strm_buf=cout.rdbuf();    
    cout.rdbuf(outf.rdbuf()); 
    cout<<"write something to file"<<endl; 
    cout.rdbuf(strm_buf);   //recover 
    cout<<"display something on screen"<<endl;
    system("PAUSE");
    return 0;
}
 

輸出到屏幕的是：

display something on screen

輸出到文件的是：

write something to file

也就是說，隻要改變 ostream 的 rdbuf ，就可以重定向了，但是這招對 fstream 和 stringstream 都沒用。

--------------------------------------------------------------------------

關於 istream_iterator 和 ostream_iterator

經典的 ostream_iterator 例子，就是用 copy 來輸出：

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main()
{  
    vector<int> vect;
    for ( int i = 1; i <= 9; ++i )
        vect.push_back(i);
       
    copy(vect.begin(), vect.end(),
        ostream_iterator<int>(cout, " ")
    );
    cout << endl;
   
    ostream_iterator<double> os_iter(cout, " ~ ");
    *os_iter = 1.0;
    os_iter++;
    *os_iter = 2.0;
    *os_iter = 3.0;
}

輸出：

1 2 3 4 5 6 7 8 9
1 ~ 2 ~ 3 ~

很明顯，ostream_iterator 的作用就是允許對 stream 做 iterator 的操作，從而讓算法可以施加於 stream 之上，這也是 STL 的精華。與前麵的“讀取文件”相結合，我們得到了顯示一個文件最方便的辦法：

    copy(istreambuf_iterator<char>(ifs.rdbuf()),
         istreambuf_iterator<char>(),
         ostreambuf_iterator<char>(cout)
    );

同樣，如果你用下麵的語句，得到的會是沒有分隔符的輸出：

    copy(istream_iterator<char>(ifs),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

那多半不是你要的結果。如果你硬是想用 istream_iterator 而不是 istreambuf_iterator 呢？還是有辦法：

    copy(istream_iterator<char>(ifs >> noskipws),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

但是這樣不是推薦方法，它的效率比第一種低不少。
如果一個文件 temp.txt 的內容是下麵這樣，那麼我的這個從文件中把數據讀入 vector 的方法應該會讓你印象深刻。

12345 234 567
89    10

程序：

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main()
{  
    ifstream ifs("temp.txt");
   
    vector<int> vect;
    vect.assign(istream_iterator<int>(ifs),
        istream_iterator<int>()
    );

    copy(vect.begin(), vect.end(), ostream_iterator<int>(cout, " "));
}

輸出：

12345 234 567 89 10

很酷不是麼？判斷文件結束、移動文件指針之類的苦工都有 istream_iterator 代勞了。

-----------------------------------------------------------------------

其它算法配合 iterator

計算文件行數：

    int line_count =
        count(istreambuf_iterator<char>(ifs.rdbuf()),
              istreambuf_iterator<char>(),
              '\n');       

當然確切地說，這是在計算文件中回車符的數量，同理，你也可以計算文件中任何字符的數量，或者某個 token 的數量：

    int token_count =
        count(istream_iterator<string>(ifs),
              istream_iterator<string>(),
              "#include");       

注意上麵計算的是 “#include” 作為一個 token 的數量，如果它和其他的字符連起來，是不算數的。

------------------------------------------------------------------------
Manipulator

Manipulator 是什麼？簡單的說，就是一個接受一個 stream 作為參數，並且返回一個 stream 的函數，比如上麵的 unskipws ，它的定義是這樣的：

  inline ios_base&
  noskipws(ios_base& __base)
  {
    __base.unsetf(ios_base::skipws);
    return __base;
  }

這裏它用了更通用的 ios_base 。知道了這一點，你大概不會對自己寫一個 manipulator 有什麼恐懼感了，下麵這個無聊的 manipulator 會忽略 stream 遇到第一個分號之前所有的輸入（包括那個分號）：

template <class charT, class traits>
inline std::basic_istream<charT, traits>&
ignoreToSemicolon (std::basic_istream<charT, traits>& s)
{
    s.ignore(std::numeric_limits<int>::max(), s.widen(';'));
    return s;
}

不過注意，它不會忽略以後的分號，因為 ignore 隻執行了一次。更通用一點，manipulator 也可以接受參數的，下麵這個就是ignoreToSemicolon 的通用版本，它接受一個參數， stream 會忽略遇到第一個該參數之前的所有輸入，寫起來稍微麻煩一點：

struct IgnoreTo {
    char ignoreTo;
    IgnoreTo(char c) : ignoreTo(c)
    {}
};
   
std::istream& operator >> (std::istream& s, const IgnoreTo& manip)
{
    s.ignore(std::numeric_limits<int>::max(), s.widen(manip.ignoreTo));
    return s;
}

但是用法差不多：

    copy(istream_iterator<char>(ifs >> noskipws >> IgnoreTo(';')),
         istream_iterator<char>(),
         ostream_iterator<char>(cout)
    );

其效果跟 IgnoreToSemicolon 一樣。

 

STL算法學習，小結如下：

前提:

下載stl源碼： https://www.sgi.com/tech/stl/download.html 打開網頁：     https://www.sgi.com/tech/stl/stl_index.html

一   函數對象： 因為很多的算法中多使用了函數對象

二元函數對象，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

二元邏輯函數

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

一元函數對象

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

一元斷定函數對象

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

一元邏輯函數

unary_negate:

二   函數對象發生器：主要用來填充序列。 產生不重複的隨機數： // Generate unique random numbers from 0 to mod: classURandGen { std::set<int> used; int limit; public: URandGen(intlim) : 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);

三 函數對象適配器 ： 將函數轉化為函數對象

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)）；

四   算法：

拷貝： copy（） reverse_copy() rotate_copy() remove_copy() 拷貝不等於某值的元素到另一個序列。 remove_copy_if() 拷貝符合條件的到另一個序列。

填充和生成： fill() fill_n() 填充序列中的n個元素。 generate（）為序列中的每個元素調用gen（）函數。

排列： next_permuttion() 後一個排列。 prev_permutation()

partition() 劃分，將滿足條件的元素移動到序列的前麵。 stable_partition()

查找和替換： find（） binary_search() 在一個已經有順序的序列上查找。 find_if() search() 檢查第二個序列是否在第一個序列中出現，且順序相同。

刪除：注意必須調用erase（）來真正刪除 remove（） unique（）刪除相鄰重複元素，最好現排序。

合並序列： merge（）

數值算法： accumulate（） 對序列的每個元素進行運算後求和。 transform（） 也可以對每個元素進行運算。 計數： size（）總個數。 count（）等於某值的元素個數。

adjacent_difference 序列中的後一個減前與他相鄰的前一個得到新的序列。

adiacent_find

五   所有的算法：

     accumlate ： iterator 對標誌的序列中的元素之和，加到一個由 init 指定的初始值上。重載的版本不再做加法，而是傳進來的二元操作符被應用到元素上。

adjacent_different ：創建一個新序列，該序列的每個新值都代表了當前元素與上一個元素的差。重載版本用指定的二元操作計算相鄰元素的差。

adjacent_find ：在 iterator 對標誌的元素範圍內，查找一對相鄰的重複元素，如果找到返回一個 ForwardIterator ，指向這對元素的第一個元素。否則返回 last 。重載版本使用輸入的二元操作符代替相等的判斷。

binary_search ：在有序序列中查找 value ，如果找到返回 true 。重載的版本使用指定的比較函數對象或者函數指針來判斷相等。

copy ：複製序列

copy_backward ：除了元素以相反的順序被拷貝外，別的和 copy 相同。 count ：利用等於操作符，把標誌範圍類的元素與輸入的值進行比較，並返回相等元素的個數

count_if ：對於標誌範圍類的元素，應用輸入的操作符，並返回結果為 true 的次數。

equal ：如果兩個序列在範圍內的元素都相等，則 equal 返回 true 。重載版本使用輸入的操作符代替了默認的等於操作符。

equal_range ：返回一對 iterator ，第一個 iterator 表示由 lower_bound 返回的 iterator ，第二個表示由 upper_bound 返回的 iterator 值。

fill ：將輸入的值的拷貝賦給範圍內的每個元素。

fill_n ：將輸入的值賦值給 first 到 frist+n 範圍內的元素。

find ：利用底層元素的等於操作符，對範圍內的元素與輸入的值進行比較。當匹配時，結束搜索，返回該元素的一個 InputIterator 。

find_if ：使用輸入的函數替代了等於操作符執行了 find 。

find_end ：在範圍內查找“由輸入的另外一個 iterator 對標誌的第二個序列”的最後一次出現。重載版本中使用了用戶輸入的操作符替代等於操作。

find_first_of ：在範圍內查找“由輸入的另外一個 iterator 對標誌的第二個序列”中的任意一個元素的第一次出現。重載版本中使用了用戶自定義的操作符。

for_each ：依次對範圍內的所有元素執行輸入的函數。

generate ：通過對輸入的函數 gen 的連續調用來填充指定的範圍。

generate_n ：填充 n 個元素。

includes ：判斷 [first1, last1) 的一個元素是否被包含在另外一個序列中。使用底層元素的 <= 操作符，重載版本使用用戶輸入的函數。

inner_product ：對兩個序列做內積 ( 對應的元素相乘，再求和 ) ，並將內積加到一個輸入的的初始值上。重載版本使用了用戶定義的操作。

inner_merge ：合並兩個排過序的連續序列，結果序列覆蓋了兩端範圍，重載版本使用輸入的操作進行排序。

iter_swap ：交換兩個 ForwardIterator 的值。

lexicographical_compare ：比較兩個序列。重載版本使用了用戶自定義的比較操作。

lower_bound ：返回一個 iterator ，它指向在範圍內的有序序列中可以插入指定值而不破壞容器順序的第一個位置。重載函數使用了自定義的比較操作。 max ：返回兩個元素中的較大的一個，重載版本使用了自定義的比較操作。

max_element ：返回一個 iterator ，指出序列中最大的元素。重載版本使用自定義的比較操作。

min ：兩個元素中的較小者。重載版本使用自定義的比較操作。

min_element ：類似與 max_element ，不過返回最小的元素。

merge ：合並兩個有序序列，並存放到另外一個序列中。重載版本使用自定義的比較。

mismatch ：並行的比較兩個序列，指出第一個不匹配的位置，它返回一對 iterator ，標誌第一個不匹配的元素位置。如果都匹配，返回每個容器的 last 。重載版本使用自定義的比較操作。 next_permutation ：取出當前範圍內的排列，並將其重新排序為下一個排列。重載版本使用自定義的比較操作。

nth_element ：將範圍內的序列重新排序，使所有小於第 n 個元素的元素都出現在它前麵，而大於它的都出現在後麵，重載版本使用了自定義的比較操作。

partial_sort ：對整個序列做部分排序，被排序元素的個數正好可以被放到範圍內。重載版本使用自定義的比較操作。

 partial_sort_copy ：與 partial_sort 相同，除了將經過排序的序列複製到另外一個容器。 partial_sum ：創建一個新的元素序列，其中每個元素的值代表了範圍內該位置之前所有元素之和。重載版本使用了自定義操作替代加法。

partition ：對範圍內元素重新排序，使用輸入的函數，把計算結果為 true 的元素都放在結果為 false 的元素之前。

prev_permutation ：取出範圍內的序列並將它重新排序為上一個序列。如果不存在上一個序列則返回 false 。重載版本使用自定義的比較操作。

random_shuffle ：對範圍內的元素隨機調整次序。重載版本輸入一個隨機數產生操作。

remove ：刪除在範圍內的所有等於指定的元素，注意，該函數並不真正刪除元素。內置數組不適合使用 remove 和 remove_if 函數。

remove_copy ：將所有不匹配的元素都複製到一個指定容器，返回的 OutputIterator 指向被拷貝的末元素的下一個位置。

remove_if ：刪除所有範圍內輸入操作結果為 true 的元素。

remove_copy_if ：將所有不匹配的元素拷貝到一個指定容器。

replace ：將範圍內的所有等於 old_value 的元素都用 new_value 替代。 replace_copy ：與 replace 類似，不過將結果寫入另外一個容器。

replace_if ：將範圍內的所有操作結果為 true 的元素用新值替代。

replace_copy_if ：類似與 replace_if ，不過將結果寫入另外一個容器。

reverse ：將範圍內元素重新按反序排列。

reverse_copy ：類似與 reverse ，不過將結果寫入另外一個容器。

rotate ：將範圍內的元素移到容器末尾，由 middle 指向的元素成為容器第一個元素。

rotate_copy ：類似與 rotate ，不過將結果寫入另外一個容器。

search ：給出了兩個範圍，返回一個 iterator ，指向在範圍內第一次出現子序列的位置。重載版本使用自定義的比較操作。

search_n ：在範圍內查找 value 出現 n 次的子序列。重載版本使用自定義的比較操作。 set_difference ：構造一個排過序的序列，其中的元素出現在第一個序列中，但是不包含在第二個序列中。重載版本使用自定義的比較操作。

set_intersection ：構造一個排過序的序列，其中的元素在兩個序列中都存在。重載版本使用自定義的比較操作。

set_symmetric_difference ：構造一個排過序的序列，其中的元素在第一個序列中出現，但是不出現在第二個序列中。重載版本使用自定義的比較操作。

set_union ：構造一個排過序的序列，它包含兩個序列中的所有的不重複元素。重載版本使用自定義的比較操作。

sort ：以升序重新排列範圍內的元素，重載版本使用了自定義的比較操作。

stable_partition ：與 partition 類似，不過它不保證保留容器中的相對順序。

stable_sort ：類似與 sort ，不過保留相等元素之間的順序關係。

swap ：交換存儲在兩個對象中的值。

swap_range ：將在範圍內的元素與另外一個序列的元素值進行交換。

transform ：將輸入的操作作用在範圍內的每個元素上，並產生一個新的序列。重載版本將操作作用在一對元素上，另外一個元素來自輸入的另外一個序列。結果輸出到指定的容器。

unique ：清除序列中重複的元素，和 remove 類似，它也不能真正的刪除元素。重載版本使用了自定義的操作。

unique_copy ：類似與 unique ，不過它把結果輸出到另外一個容器。

upper_bound ：返回一個 iterator ，它指向在範圍內的有序序列中插入 value 而不破壞容器順序的最後一個位置，該位置標誌了一個大於 value 的值。重載版本使用了輸入的比較操作。 堆算法： C++ 標準庫提供的是 max-heap 。一共由以下 4 個泛型堆算法。

make_heap ：把範圍內的元素生成一個堆。重載版本使用自定義的比較操作。

pop_heap ：並不是真正的把最大元素從堆中彈出，而是重新排序堆。它把 first 和 last-1 交換，然後重新做成一個堆。可以使用容器的 back 來訪問被“彈出“的元素或者使用 pop_back 來真正的刪除。重載版本使用自定義的比較操作。

push_heap ：假設 first 到 last-1 是一個有效的堆，要被加入堆的元素在位置 last-1 ，重新生成堆。在指向該函數前，必須先把元素插入容器後。重載版本使用指定的比較。

sort_heap ：對範圍內的序列重新排序，它假設該序列是個有序的堆。重載版本使用自定義的比較操作。


最後更新：2017-04-02 15:14:59

  上一篇：go 5個數求最值
  下一篇：go 擅長排列的小明