#include

C++ STL iterator アルゴリズム（初級）

for_each
便利そうだけど当分使いそうもない。

template< class InputIterator, class UnaryFunction >
UnaryFunction for_each( InputIterator first, InputIterator last, UnaryFunction f );

template struct increment : public unary_function { //継承してる
    void operator()(T& x)
    {
        x++;
    }
};  //xの値が書き換えられる．


remove
実際には消えていない．消す要素を上書きするだけ．

int arr[5] = {3, 6, 4, 3, 5};
vector<int> nums(arr, arr+5);

// vectorの中から3を削除する
remove( nums.begin(), nums.end(), 3 ); //{6, 4, 5, 3, 5} <--0,1,2番目の要素は上書きされるが、3,4ばんの要素はeraseされずそのまま残っている．


next_permutation
しらみつぶしに見ていかないと解答が出せない時．
配列のタッグでかなり便利な存在になる．

int next_permutation_test(vector a) {
  int sz = a.size();
  vector best;
  for(int i = 0; i < sz; i++) {
    best.push_back(i);
  }
  do {
    //for(int i = 0; i < sz; i++) {
    //a[i]の処理
    //}
    ...
  } while(next_permutation(best.begin(), best.end() ));
//a = {2, 5, 7, 9}とかのとき、
//a[0]a[1]a[2]a[3] --> a[0]a[1]a[3]a[2] ---> a[0]a[2]a[1]a[3] ... みたいに順々に列挙できる．
//Combinationのときはhttp://d.hatena.ne.jp/kenta11626918/20110419/1303204508参照

しかしながら、配列の数が15~20以上になると速度的にかなり使いにくくなる．


max_element, min_element
最大、最小を求める関数なのだが。
mapでは、Keyの最大のiteratorが出てくる．

int main() {
  map nameMap;
  nameMap["Ti"] = 1;
  nameMap["Ak"] = 4;
  nameMap["hi"] = 2;
  nameMap["nim"] = 3;
  map::iterator max_it = max_element(nameMap.begin(), nameMap.end(), nameMap.value_comp() );
  cout << max_it->second << max_it->first << endl;  //nim 3
}

なので、正直、使いどころがいまいちない。

vector win;
//最大値を代入
int m = *max_element(win.begin(), win.end());

//最大値のindexを代入
int index = max_element(win.begin(), win.end()) - win.begin();


unique

配列内で連続して重複した要素を取り除く

#include 
 
template< class ForwardIterator >
ForwardIterator unique( ForwardIterator first, ForwardIterator last );
 
template< class ForwardIterator, class BinaryPredicate >
ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate p );
//ソートとは違って戻り値がイテレータであることに注意。



1 2 2 3 3 4 4 4 5 5 
        \
1 2 3 4 5 2 3 4 4 5
        ↑戻り値は5の後の2を指し示す

sortとeraseの併用でそれなりに、場合によってはかなり使える関数になる。
string型ではsetを使うのもったいないので、しばしばsortとeraseの併用の手法が使われる．

sort(a.begin(), a.end());
erase(unique(a.begin(), a.end()), a.end())  //重複した数字がすっかり消える。

実はあんまり使い道なかったりする。重複を取り除きたければ、setをつかって、insertすればいいから。
set(v.begin(), v.end());  //とやれば済む話。

template< class InputIterator >
set( InputIterator first, InputIterator last,           
     const Compare& comp = Compare(),
     const Allocator& alloc = Allocator() );

set_difference　(⇔ set_intersection:共通のものを抜き出す)
共通していないものを抜き出す。共通している要素の数を数えたりとか、意図的に排除する配列を作り出して、共通化することで、意図した要素を排除できたり。内部結合。
set_symmetric_difference:外部結合っぽい

accumulate



T accumulate( input_iterator start, input_iterator end, T val );  //T valの項を書き忘れないように。

配列全体をかけたり足したりできる。

多重forでややこしくなるときとかはこれを使えばコードが見やすくなると思う。



partial_sum

なんか便利なのか使いどころがないのかよくわからない関数．



#include 
output_iterator partial_sum( input_iterator start, input_iterator end, output_iterator result );
output_iterator partial_sum( input_iterator start, input_iterator end, output_iterator result, BinOp p );

//実験
vector a(10, 0);
for(int i = 0; i < a.size(); i++) {
  a[i] = i;
}
partial_sum(a.begin(), a.end(), a.begin());
for(int i = 0; i < a.size(); i++) {
cout << a[i] << endl;
}
a : 0 1 2 3  4 5 6 7 8 9(before)
a : 0 1 3 6 10 15 ...(after)

fill

memset は基本0とか、-1とかに初期化するときしか使わない方が良い．



#include 
void fill( forward_iterator start, forward_iterator end, const T& val)



//普通の配列で初期化したい．
    fill(step[0], step[0]+sizeof step/sizeof step[0][0], INF);
//stepに添え字がつくstep[0]になることに注意。

第三引数に初期化したい数を持ってこればOK!





count

fillも配列に関して使ったが、countも、ほかの関数も配列に関して同様に使用できる。



bool flag[row][col];
memset(flag, false, sizeof flag);
//何らかの処理でflag[i][j]の値が変わる。
return count(flag[0], flag[0]+row*col, false);
//falseの個数をカウントする。

partition, stable_partition

stableのほうは順序を崩さずに。普通のpartitionだと順序が崩れるので、stable_のほうが使いやすいと思う。



//イテレータを返すことに注意。
template 
  BidirectionalIterator partition ( BidirectionalIterator first,
                                    BidirectionalIterator last, Predicate pred )
{
  while (true)
  {
    while (first!=last && pred(*first)) ++first;
    if (first==last--) break;
    while (first!=last && !pred(*last)) --last;
    if (first==last) break;
    swap (*first++,*last);
  }
  return first;
}

//
vector::iterator bound = stable_partition(order.begin(), order.end(), IsEven);
//indexを移動して、並び変える動作をするというのも手。
//vector order  //順序 
//vector card   //カード
vector tmp(n, 0);
for(int i = 0; i < n; i++) {
	tmp[i] = card[order[i]];	
}
card = tmp;

before : 1 2 3 4 5 6 7 8
  after  : 2 4 6 8 1 3 5 7
               -       -
              begin   bound

inner_product

かんたんにいうと、a[0]*b[0]+a[1]*b[1]+