勉強@C++ 続き

find
値の走査

// v = { 1, 2, 3, 4, 5 }
find(v.begin(), v.end(), 3); // v.begin() + 2
find(v.begin(), v.end(), 7); // v.end()

count
個数カウント

// v = { 1, 2, 1, 3, 2 }
count(v.begin(), v.end(), 1); // 2

equal
配列の一致

// v = { 1, 2, 3 }, w = { 1, 2, 3 }
equal(v.begin(), v.end(), w.begin()); // true
w[0] = 2;
equal(v.begin(), v.end(), w.begin()); // false

search
部分列を検索。イテレータが返却。

// v = { 1, 2, 3, 4, 5 }, w = { 3, 4 }
search(v.begin(), v.end(), w.begin(), w.end()); // v.begin() + 2

replace
値の置き換え。

// v = { 1, 2, 3, 2, 1 }
replace(v.begin(), v.end(), 2, 4); // v = { 1, 4, 3, 4, 1 }

remove
ある値を消す。新しい末尾位置を示すイテレータが返ってくる。
消した個数だけ後ろにいらないものが付加される。コンテナのeraseなどと一緒に使えば消せる

// v = { 1, 2, 3, 2, 1 }, w = { 1, 2, 3, 2, 1 }
remove(v.begin(), v.end(), 2);                   // v = { 1, 3, 1, ? , ? }
w.erase(remove(w.begin(), w.end(), 2), w.end()); // w = { 1, 3, 1 }

unique
ユニークな値を探す。新しい末尾位置を示すイテレータが返ってくる。

// v = { 1, 1, 2, 2, 3, 3 }
v.erase(unique(v.begin(), v.end()), v.end()); // v = { 1, 2, 3 }

reverse
逆順に並べ替える。

// v = { 1, 2, 3, 4, 5 }
reverse(v.begin(), v.end()); // v = { 5, 4, 3, 2, 1 }

rotate
文字列等の配列をシフトする。第2引数は操作後に新しく先頭になっている要素のイテレータ。

// v = { 1, 2, 3, 4, 5 }
rotate(v.begin(), v.begin() + 2, v.end()); // v = { 3, 4, 5, 1, 2 }

random_shuffle
シャッフル

// v = { 1, 2, 3, 4, 5 }
random_shuffle(v.begin(), v.end()); // v = { 3, 5, 2, 4, 1 } (例えばこうなる)

sort
昇順そーとを行う

// v = { 3, 5, 2, 4, 1 }, w = { 3, 5, 2, 4, 1 }
sort(v.begin(), v.end());   // v = { 1, 2, 3, 4, 5 }
sort(w.rbegin(), v.rend()); // w = { 5, 4, 3, 2, 1 } (greaterを使うより楽！)

lower_bound, upper_bound
ソート済みの配列に対して、ある値を入れるときに、最も早い/遅い位置の直後のイテレータを返す。自動二分探索が行われる

// v = { 1, 2, 2, 3, 3 }
lower_bound(v.begin(), v.end(), 2); // v.begin() + 1
upper_bound(v.begin(), v.end(), 2); // v.begin() + 3

binary_search
二分探索

// v = { 1, 2, 2, 3, 3 }
binary_search(v.begin(), v.end(), 2); // true
binary_search(v.begin(), v.end(), 4); // false

max_element, min_element
配列中の最大値/最小値のイテレータを返却。
添字も帰ってくる。

// v = { 3, 5, 2, 4, 1 }
max_element(v.begin(), v.end());  // v.begin() + 1
*max_element(v.begin(), v.end()); // 5
max_element(v.begin(), v.end()) - v.begin(); // 1 (5のインデックス)

next_permutation, prev_permutation
なんと！順列を求められる（感動）

// v = { 1, 2, 3 }
do{
  // v は ループごとに
  //  { 1, 2, 3 }, { 1, 3, 2 }, 
  //  { 2, 1, 3 }, { 2, 3, 1 },
  //  { 3, 1, 2 }, { 3, 2, 1 }
  // になっている。
}while(next_permutation(v.begin(), v.end()));
// ループ後は v = { 1, 2, 3 }

// 組み合わせを全部試したいときにも使える
// 3個中2個を選びたい場合は
// w = { 0, 1, 1 } としておき以下のように出来る。
do{
  // w[i] = 1 ならば i 番目のものを選んでいる状態
  // w[i] = 0 ならば i 番目のものは選んでいない状態
}while(next_permutation(w.begin(), w.end()));

#include <numeric>

accumulate
総和を計算。

// v = { 1, 2, 3, 4, 5 }
// w = { "Competitive", "Programming", "Advent", "Calendar" }
accumulate(v.begin(), v.end(), 0);   // 15、結果はint
accumulate(v.begin(), v.end(), 0ll); // 15、結果はlong long
accumulate(v.begin(), v.end(), 1, multiplies<int>()); // 120、結果はint
accumulate(w.begin(), w.end(), string()); // "CompetitiveProgrammingAdventCalendar" 

partial_sum
途中までの和を全部求められる

// v = { 1, 2, 3, 4, 5 }
// w.size() >= 5 じゃないとダメ
partial_sum(v.begin(), v.end(), w.begin()); // w = { 1, 3, 6, 10, 15 }
partial_sum(v.begin(), v.end(), v.begin()); // vに上書きもできる v = { 1, 3, 6, 10, 15 }

#incldude <functional>

Algorithmの関数に渡せるものがある

//比較系

equal_to, not_equal_to, greater, less, greater_equal, less_equal
//演算系

plus, minus, multiplies, divides, modulus, negate

sort(v.begin(), v.end(), greater<int>()); // 降順ソート