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（）來(lái)綁定比較對(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ā)生器：主要用來(lái)填充序列。
產(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（）來(lái)真正刪除
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)來(lái)的二元操作符被應(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ù)指針來(lái)判斷相等。
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
：通過(guò)對(duì)輸入的函數(shù)
gen
的連續(xù)調(diào)用來(lái)填充指定的范圍。
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è)排過(guò)序的連續(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
，不過(guò)返回最小的元素。
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)過(guò)排序的序列復(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
類似，不過(guò)將結(jié)果寫入另外一個(gè)容器。
replace_if
：將范圍內(nèi)的所有操作結(jié)果為
true
的元素用新值替代。
replace_copy_if
：類似與
replace_if
，不過(guò)將結(jié)果寫入另外一個(gè)容器。
reverse
：將范圍內(nèi)元素重新按反序排列。
reverse_copy
：類似與
reverse
，不過(guò)將結(jié)果寫入另外一個(gè)容器。
rotate
：將范圍內(nèi)的元素移到容器末尾，由
middle
指向的元素成為容器第一個(gè)元素。
rotate_copy
：類似與
rotate
，不過(guò)將結(jié)果寫入另外一個(gè)容器。
search
：給出了兩個(gè)范圍，返回一個(gè)
iterator
，指向在范圍內(nèi)第一次出現(xiàn)子序列的位置。重載版本使用自定義的比較操作。
search_n
：在范圍內(nèi)查找
value
出現(xiàn)
n
次的子序列。重載版本使用自定義的比較操作。
set_difference
：構(gòu)造一個(gè)排過(guò)序的序列，其中的元素出現(xiàn)在第一個(gè)序列中，但是不包含在第二個(gè)序列中。重載版本使用自定義的比較操作。
set_intersection
：構(gòu)造一個(gè)排過(guò)序的序列，其中的元素在兩個(gè)序列中都存在。重載版本使用自定義的比較操作。
set_symmetric_difference
：構(gòu)造一個(gè)排過(guò)序的序列，其中的元素在第一個(gè)序列中出現(xiàn)，但是不出現(xiàn)在第二個(gè)序列中。重載版本使用自定義的比較操作。
set_union
：構(gòu)造一個(gè)排過(guò)序的序列，它包含兩個(gè)序列中的所有的不重復(fù)元素。重載版本使用自定義的比較操作。
sort
：以升序重新排列范圍內(nèi)的元素，重載版本使用了自定義的比較操作。
stable_partition
：與
partition
類似，不過(guò)它不保證保留容器中的相對(duì)順序。
stable_sort
：類似與
sort
，不過(guò)保留相等元素之間的順序關(guān)系。
swap
：交換存儲(chǔ)在兩個(gè)對(duì)象中的值。
swap_range
：將在范圍內(nèi)的元素與另外一個(gè)序列的元素值進(jìn)行交換。
transform
：將輸入的操作作用在范圍內(nèi)的每個(gè)元素上，并產(chǎn)生一個(gè)新的序列。重載版本將操作作用在一對(duì)元素上，另外一個(gè)元素來(lái)自輸入的另外一個(gè)序列。結(jié)果輸出到指定的容器。
unique
：清除序列中重復(fù)的元素，和
remove
類似，它也不能真正的刪除元素。重載版本使用了自定義的操作。
unique_copy
：類似與
unique
，不過(guò)它把結(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
來(lái)訪問(wèn)被“彈出“的元素或者使用
pop_back
來(lái)真正的刪除。重載版本使用自定義的比較操作。
push_heap
：假設(shè)
first
到
last-1
是一個(gè)有效的堆，要被加入堆的元素在位置
last-1
，重新生成堆。在指向該函數(shù)前，必須先把元素插入容器后。重載版本使用指定的比較。
sort_heap
：對(duì)范圍內(nèi)的序列重新排序，它假設(shè)該序列是個(gè)有序的堆。重載版本使用自定義的比較操作。
接下來(lái)： STL容器學(xué)習(xí)