1.C++標(biāo)準(zhǔn)庫(kù)的算法，是什么東西日川？
從語(yǔ)言的層面講蔓腐，STL的算法都長(zhǎng)下面兩個(gè)樣子：
template<typename Iterator>
Algorithm(Iterator itr1, Iterator itr2)
{
//...
}
template<typename Iterator, typename Cmp>
Algorithm(Iterator itr1, Iterator itr2, Cmp comp)
{
//...
}
上面這兩個(gè)東西是Function template（函數(shù)模板），一般情況算法都有兩個(gè)版本龄句，一個(gè)是兩個(gè)參數(shù)的回论，一個(gè)是有三個(gè)參數(shù)的版本。前面兩個(gè)參數(shù)是兩個(gè)迭代器分歇，用來(lái)讓算法知道需要操作的對(duì)象的范圍傀蓉，第三個(gè)參數(shù)是為了增加算法的彈性，用戶可以在其中加上自己的準(zhǔn)則职抡，比如：sort函數(shù)葬燎，默認(rèn)是從小到大排序，如果加上第三個(gè)參數(shù)（指定從大到懈克Α）谱净，那么sort就會(huì)將數(shù)據(jù)按照指定的方式操作。
算法是看不見(jiàn)容器的擅威，對(duì)其一無(wú)所知壕探，一切信息都是從iterator中得到。iterator就是算法和容器之間的橋梁郊丛。
1.1各種容器的iterators的iterator_category
STL中有五中iterator_category分別是：
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirectional_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirectional_iterator_tag{};
Array李请，Vector，Deque這三種容器支持隨機(jī)訪問(wèn)厉熟，是連續(xù)空間（deque模仿出連續(xù)的假象）导盅，使用的是random_access_iterator_tag
list，set庆猫，map认轨，multiset，multimap月培，都是關(guān)聯(lián)性容器嘁字，不支持隨機(jī)訪問(wèn)，使用的是bidirectional_iterator_tag
forward_list杉畜，unordered_set纪蜒，unordered_map，unordered_multiset此叠，unordered_multimap是單向連續(xù)性空間纯续，不支持隨機(jī)訪問(wèn)，使用的是forward_iterator_tag
istream，ostream分別使用的是input_iterator_tag猬错，output_inerator_tag
注：typeid(iter).name()窗看，可以直接得到對(duì)象的類(lèi)型名稱(chēng)
1.2iterator_category對(duì)算法的影響
使用distance函數(shù)求得一個(gè)容器begin和end之間的距離
template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last)
{
typedef typename iterator_traits<InputIterator>::iterator_category category;
return __distance(first, last, category);
}
當(dāng)傳入vector.begin()和vector.end()函數(shù)，通過(guò)萃取機(jī)iterator_traits得到他的iterator_category類(lèi)型倦炒，然后去調(diào)用：
template<typename RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last, input_iterator_tag)
{
return last - first;
}
因?yàn)檫B續(xù)空間的容器显沈，所以直接首尾相減，就能得到距離逢唤，速度非忱叮快
當(dāng)傳入的是list.begin()和list.end()函數(shù)，通過(guò)萃取機(jī)iterator_traits得到他的iterator_category類(lèi)型鳖藕，然后去調(diào)用：
template<typename InputIterator>
inline iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
iterator_traits<InputIterator>::difference_type n = 0;
while(first != last)
{
++first;
++n;
}
return n;
}
因?yàn)槭欠沁B續(xù)空間容器魔慷，所以只能通過(guò)迭代的方式，一個(gè)一個(gè)向后偏移得到距離著恩。速度很慢院尔。
由此可以想象，不同的iterator_category對(duì)算法的影響是非常大的页滚。在算法中召边，會(huì)做非常多的檢查，讓算法使用正確的最快的迭代器分類(lèi)去操作容器裹驰，使用STL其實(shí)是一件非常幸福的事情（想想c程序員隧熙。。幻林。）
2.仿函數(shù)
仿函數(shù)其實(shí)是一個(gè)類(lèi)重載了()運(yùn)算符贞盯，在STL中如下：
template <typename T>
struct plus: public binary_function<T,T,T>
{
T operator () (const T& x, const T& y)
{
return x+y;
}
}
在使用STL的算法時(shí)，可以使用函數(shù)來(lái)指定第三參數(shù)沪饺，也可以用仿函數(shù)指定躏敢，例如：
// 使用函數(shù)指定
bool myfunc(int i, int j)
{
return i < j;
}
sort(myvec.begin(), myvec.end(), myfunc);
// 使用仿函數(shù)指定
template <typename T>
struct less: public binary_function<T, T, bool>
{
bool operator () (const T& x, const T& y) const
{
return x < y;
}
}
sort(myvec.begin(), myvec.end(), less<int>());
less<int>()是一個(gè)臨時(shí)對(duì)象，將其傳入sort之后整葡，sort會(huì)自動(dòng)調(diào)用class less里頭的operator ()件余，就像調(diào)用函數(shù)一樣（仿函數(shù)比函數(shù)更有彈性），因?yàn)榉潞瘮?shù)可以被適配器修改遭居。
如果我們自己寫(xiě)了一個(gè)仿函數(shù)啼器，需要繼承STL的兩個(gè)類(lèi)：
``
// 一個(gè)操作數(shù)繼承
unary_functiontemplate <class Arg, class Result>
struct unary_function
{
typedef Arg argument_type;
typedef Result result_type;
};
// 兩個(gè)操作數(shù)繼承
binary_functiontemplate <class Arg1, class Arg2, class Result>
struct binary_function
{
typedef Arg1 fist_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
STL規(guī)定每一個(gè)Adaptable Function都要挑選適當(dāng)?shù)膩?lái)繼承，因?yàn)镕unction Adapter將會(huì)提問(wèn)問(wèn)題俱萍，例如：
template <class Operation>
class binder2nd: public unary_function<typename Operation::fist_argument_type,typename Operation::result_type>
{
protected: Operation op;
// 這里就是function adapter在問(wèn)問(wèn)題
typename Operation::second_argument_type value;
public:
// ....
};
typename Operation::second_argument_type value;
這一句就是在問(wèn)仿函數(shù)問(wèn)題端壳，你的第二個(gè)參數(shù)類(lèi)型是什么，如果這一句可以編譯通過(guò)枪蘑，那么函數(shù)適配器就得到了仿函數(shù)的第二個(gè)參數(shù)類(lèi)型损谦，仿函數(shù)就可以被改造岖免。
一個(gè)仿函數(shù)想要能被STL中的適配器改造，就需要繼承適當(dāng)?shù)念?lèi)融入STL照捡。
3. Adapter
STL的算法可以讓用戶提供第三參數(shù)颅湘，用于給用戶自定義算法處理數(shù)據(jù)的方式，上面講述了可以使用仿函數(shù)作為第三參數(shù)栗精，仿函數(shù)可以被適配器改造栅炒，下面就來(lái)看一下適配器是如何改造仿函數(shù)的。
3.1 bind2nd
以泛型算法count_if為例：
template <class InputIterator, class Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred)
{
typename iterator_traits<InputIterator>::difference_type n = 0;
for(; first != last; ++first)
{
if(pred(*first))
{
++n;
}
} return n;
}
在使用count_if時(shí)如下：
count_if(vi.begin(), vi.end(), bind2nd(less<int>(), 40));
bind2nd就是一個(gè)適配器术羔，用于將仿函數(shù)less的第二參數(shù)綁定為40。
bind2nd源碼如下：
template <class Operation, class T>
inline binder2nd<Operation> bind2nd(const Operation& op, const T& x)
{
typedef typename Operation::second_argument_type arg2_type;
return binder2nd<Operation>(op, arg2_type(x));
}
在bind2nd中返回的是一個(gè)binder2nd類(lèi)型的臨時(shí)對(duì)象乙漓，bind2nd函數(shù)其實(shí)是一個(gè)中間層级历，因?yàn)閎inder2nd類(lèi)模板不可以自動(dòng)推導(dǎo)類(lèi)型參數(shù)，只有模板函數(shù)可以叭披，所以使用中間層給類(lèi)模板指定模板參數(shù)Operation寥殖。
class binder2nd源碼如下：
template <class Operation>
class binder2nd
: public unary_function<typename Operation::first_argument_type,
typename Operation::result_type>
{
protected:
Operation op;
typename Operation::second_argument_type value;
public:
binder2nd(const Operation& x, const typename Operation::second_argument_type& y)
:op(x), value(y)
{ }
typename Operation::result_type
operator () (const typename Operation::first_argument_type& x) const
{
return op(x, value);
}
}
當(dāng)在count_if中傳入第三參數(shù)bind2nd(less<int>(), 40)后，先會(huì)調(diào)用bind2nd函數(shù)涩蜘，函數(shù)確定Operation 和 T的類(lèi)型函數(shù)變成如下：
inline binder2nd<less<int>> bind2nd(const less<int>& op, const int& x)
{
typedef less<int>::second_argument_type arg2_type;
return binder2nd<less<int>>(op, arg2_type(x));
}
然后先讓class binder2nd確定模板參數(shù)
class binder2nd
: public unary_function<less<int>::fist_argument_type, less<int>::result_type>
{
protected:
less<int> op;
less<int>::second_argument_type value;
public:
binder2nd(const less<int>& x, const less<int>::second_argument_type& y)
:op(x), value(y)
{ }
less<int>::result_type operator () (const less<int>::first_argument_type& x) const
{
return op(x, value);
}
}
再在函數(shù)內(nèi)部調(diào)用class binder2nd的構(gòu)造函數(shù)嚼贡，實(shí)例化一個(gè)binder2nd類(lèi)型的臨時(shí)對(duì)象，將less<int>()和40分別記錄在op和value里頭同诫。
最后count_if的第三個(gè)參數(shù)就得到一個(gè)binder2nd類(lèi)型的臨時(shí)對(duì)象粤策，其中包涵了less<int>和40，count_if函數(shù)變成如下：
// 加上vi是容器list的實(shí)例化
ptrdiff_t count_if(list<int>::iterator first, list<int>::iterator last, binder2nd pred)
{
ptrdiff_t n = 0;
for(; first != last; ++first)
{
if(pred(*first))
{
++n;
}
}
return n;
}
在count_if中調(diào)用pred這個(gè)仿函數(shù)時(shí)（pred就是binder2nd類(lèi)型的臨時(shí)對(duì)象的別名）误窖，會(huì)觸發(fā)class binder2nd中的 operator()叮盘，在operator()中
op(x, 40)；
40就被綁定到less<int>()的第二參數(shù)上
這就是仿函數(shù)適配器的工作原理（真的非常的巧妙）霹俺。
3.2 inserter
當(dāng)我們想用copy函數(shù)進(jìn)行容器間的拷貝動(dòng)作時(shí)柔吼，一種是提前將空間預(yù)留
int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvec(7);
copy(myints, myints+7, myvec.begin());
提前預(yù)留空間是因?yàn)閏opy函數(shù)只是單純的移動(dòng)迭代器，向迭代器所指的地方插入數(shù)據(jù)丙唧，源碼如下：
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
{
while(first != last)
{
result = *first;
++result;
++first;
}
return result;
}
假設(shè)我們的容器其中本來(lái)就有數(shù)據(jù)愈魏，沒(méi)有預(yù)留空間，那么直接使用copy函數(shù)會(huì)造成一顆定時(shí)炸彈（越界訪問(wèn)）想际，在這種時(shí)候就需要使用適配器來(lái)改造拷貝動(dòng)作培漏。
將copy的第三參數(shù)改寫(xiě)成迭代適配器：
copy(myints, myints+7, inserter(myvec, iter)); //iter為迭代器，指向容器內(nèi)任意地方
inserter源碼如下：
template <class Container, class iterator>
inline insert_iterator<Container>
insert(Container& x, Iterator i)
{
typedef typename Container::iterator iter;
return insert_iterator<Container>(x, iter(i));
}
inserter與bind2nd一樣沼琉，也是一個(gè)輔助函數(shù)北苟，幫助class insert_iterator確定模板參數(shù)。
class insert_iterator源碼如下：
template <class Container>
class insert_iterator
{
protected:
Container* container;
typename Container::iterator iter;
public:
typedef output_iterator_tag iterator_category;
insert_iterator(Container& x, typename Container::iterator i)
:container(&x), iter(i)
{ }
insert_iterator<Container>&
operator = (const typename Container::value_type& value)
{
iter = container->insert(iter, value);
return *this;
}
typename Container::iterator& operator ++ ()
{
return ++iter;
}
};
inserter函數(shù)返回一個(gè)insert_iterator類(lèi)型的臨時(shí)對(duì)象打瘪，在這個(gè)臨時(shí)對(duì)象中友鼻，容器myvec被記錄到了容器指針container中傻昙，myvec的迭代器iter被記錄到了臨時(shí)對(duì)象中的的iter里，當(dāng)copy函數(shù)在執(zhí)行：
result = *first;
++result;
以上兩個(gè)操作的時(shí)候彩扔，會(huì)觸發(fā)class insert_iterator里的兩個(gè)操作符重載函數(shù)妆档。
這樣copy函數(shù)從原來(lái)一個(gè)傻傻的，只會(huì)一個(gè)一個(gè)拷貝的底層函數(shù)虫碉，搖身一變成了一個(gè)智能的插入拷貝函數(shù)（C++技術(shù)相當(dāng)奇妙贾惦，這就是操作符重載的好處）。
4. iostream iterator
標(biāo)準(zhǔn)庫(kù)定義有提供給輸入輸出使用的 iostream iterator敦捧，稱(chēng)為istream_iterator 和 ostream_iterator须板，他們分別支持單個(gè)元素的讀取和寫(xiě)入。
使用這兩個(gè)迭代器需要包涵#include <iterator>
4.1 ostream_iterator
ostream_iterator的使用方法如下：
// 將out_it綁定到cout輸出設(shè)備
ostream_iterator<int> out_it(cout);
// 將out_it綁定到cout輸出設(shè)備兢卵，并且在輸出元素后加上一個(gè)字符串
ostream_iterator<int> out_it(cout, ",");
include <iostream>
include <vector>
include <algorithm>
include <iterator>
using namespace std;
int main()
{
vector<int> vec;
for(int i = 0; i < 10; ++i)
{
vec.push_back(i);
}
ostream_iterator<int> outit(cout, ",");
copy(vec.begin(), vec.end(), outit);
return 0;
}
4.2 istream_iterator
使用方法如下：
// 定義一個(gè)指向輸入流結(jié)束位置的迭代器
istream_iterator<double> eos;
// 定義一個(gè)指向標(biāo)準(zhǔn)輸入的迭代器
istream_iterator<double> iit(cin)
當(dāng) iit = eos時(shí)习瑰，說(shuō)明流中的數(shù)據(jù)已經(jīng)全部讀取結(jié)束，操作iit讓其加一秽荤，可以讓迭代器指向下一個(gè)流中的數(shù)據(jù)
include <iostream>
include <iterator>
using namespace std;
int main()
{
double value1, value2;
cout << "please insert two value: ";
istream_iterator<double> eos;
istream_iterator<double> iit(cin);
if(iit != eos)
{
value1 = *iit;
}
++iit;
if(iit != eos)
{
value2 = *iit;
}
cout << value1 << ' ' << value2 << endl;
return 0;
}
這里值得注意的是甜奄，當(dāng)我們把
cout << "please insert two value: ";
寫(xiě)到
istream_iterator<double> iit(cin);
后面
在執(zhí)行程序的時(shí)候，我們發(fā)現(xiàn)窃款，當(dāng)輸入第一個(gè)數(shù)字之后课兄，cout這句輸出才會(huì)被打印出來(lái)，造成這樣的原因是晨继，當(dāng)定義了iit之后烟阐，其構(gòu)造函數(shù)已經(jīng)對(duì)iit加一，讀取已經(jīng)開(kāi)始踱稍，所以cout的輸出被放在后面曲饱。
注：
ifstream infile("./test/01.cpp");
istream_iterator<string> eos;
istream_iterator<string> iit(infile);
ofstream outfile("./2.cpp");
ostream_iterator<string> out_it(outfile, " ")
（轉(zhuǎn)載）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)珠月，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處扩淀。