C++
標準ライブラリアルゴリズム
サーチ…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
効果：
適用f範囲内のすべての反復子を間接参照の結果に[first, last)から出発してfirstすると進むlast - 1 。
パラメーター：
first, last - fを適用する範囲。
f - [first, last)の範囲内のすべての反復子の逆参照の結果に適用される呼び出し可能オブジェクト。
戻り値：
f （C ++ 11まで）およびstd::move(f) （C ++ 11以降）。
複雑：
f last - first時刻に正確に適用します。
例：
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
ベクトルのすべての要素のために与えられた関数を適用しvには、この要素を印刷stdout 。
std :: next_permutation
template< class Iterator >
bool next_permutation( Iterator first, Iterator last );
template< class Iterator, class Compare >
bool next_permutation( Iterator first, Iterator last, Compare cmpFun );
効果：
範囲[最初、最後]のデータシーケンスを次の辞書編集的に高い順列にシフトします。 cmpFunを指定すると、置換ルールがカスタマイズされます。
パラメーター：
first - 置換される範囲の開始点、包括的
last - 置換される範囲の終わり、排他的
戻り値：
そのような順列が存在する場合はtrueを返します。
さもなければ、範囲は辞書編集的に最小の順列にスワップされ、falseを返す。
複雑：
O（n）、nはfirstからlastまでの距離です。
例 ：
std::vector< int > v { 1, 2, 3 };
do
{
for( int i = 0; i < v.size(); i += 1 )
{
std::cout << v[i];
}
std::cout << std::endl;
}while( std::next_permutation( v.begin(), v.end() ) );
辞書順に1,2,3のすべての順列の場合を印刷します。
出力：
123
132
213
231
312
321
std :: accumulate
ヘッダ<numeric>定義されてい<numeric>
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init); // (1)
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation f); // (2)
効果：
std :: accumulateは、累算器の値としてinit始まる範囲[first, last) f関数を使用してフォールド演算を実行します。
効果的にそれは以下のものと同等です：
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
バージョン（1）では、 f代わりにoperator+が使用されるため、コンテナ上に累積すると、コンテナ要素の合計と等価です。
パラメーター：
first, last - fを適用する範囲。
init - アキュムレータの初期値。
f - バイナリフォールディング関数。
戻り値：
fアプリケーションの累積値。
複雑：
O（n×k） 、ここで、 nはfirstからlastまでの距離であり、 O（k）はf関数の複雑さでf 。
例：
単純な和の例：
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
出力：
10
数字を数字に変換する：
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
以降
const int ds[3] = {1, 2, 3};
int n = std::accumulate(ds, ds + 3, 0, Converter());
std::cout << n << std::endl;
const std::vector<int> ds = {1, 2, 3};
int n = std::accumulate(ds.begin(), ds.end(),
0,
[](int a, int d) { return a * 10 + d; });
std::cout << n << std::endl;
出力：
123
std :: find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
エフェクト
範囲内のvalの最初の出現を検索します（最初、最後）
パラメーター
first =>範囲の先頭を指すイテレータlast =>範囲の終わりを指すイテレータval =>範囲内で検索する値
戻る
等しい（==）からvalまでの範囲内の最初の要素を指すイテレータで、valが見つからない場合はイテレータが最後を指します。
例
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create a vector
vector<int> intVec {4, 6, 8, 9, 10, 30, 55,100, 45, 2, 4, 7, 9, 43, 48};
//define iterators
vector<int>::iterator itr_9;
vector<int>::iterator itr_43;
vector<int>::iterator itr_50;
//calling find
itr_9 = find(intVec.begin(), intVec.end(), 9); //occurs twice
itr_43 = find(intVec.begin(), intVec.end(), 43); //occurs once
//a value not in the vector
itr_50 = find(intVec.begin(), intVec.end(), 50); //does not occur
cout << "first occurence of: " << *itr_9 << endl;
cout << "only occurence of: " << *itr_43 << Lendl;
/*
let's prove that itr_9 is pointing to the first occurence
of 9 by looking at the element after 9, which should be 10
not 43
*/
cout << "element after first 9: " << *(itr_9 + 1) << ends;
/*
to avoid dereferencing intVec.end(), lets look at the
element right before the end
*/
cout << "last element: " << *(itr_50 - 1) << endl;
return 0;
}
出力
first occurence of: 9
only occurence of: 43
element after first 9: 10
last element: 48
std :: count
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
エフェクト
valに等しい要素の数を数えます。
パラメーター
first =>範囲の先頭を指すイテレータ
last =>範囲の最後を指すイテレータ
val =>範囲内のこの値の出現がカウントされます
戻る
範囲内でvalと等しい（==）要素の数。
例
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create vector
vector<int> intVec{4,6,8,9,10,30,55,100,45,2,4,7,9,43,48};
//count occurences of 9, 55, and 101
size_t count_9 = count(intVec.begin(), intVec.end(), 9); //occurs twice
size_t count_55 = count(intVec.begin(), intVec.end(), 55); //occurs once
size_t count_101 = count(intVec.begin(), intVec.end(), 101); //occurs once
//print result
cout << "There are " << count_9 << " 9s"<< endl;
cout << "There is " << count_55 << " 55"<< endl;
cout << "There is " << count_101 << " 101"<< ends;
//find the first element == 4 in the vector
vector<int>::iterator itr_4 = find(intVec.begin(), intVec.end(), 4);
//count its occurences in the vector starting from the first one
size_t count_4 = count(itr_4, intVec.end(), *itr_4); // should be 2
cout << "There are " << count_4 << " " << *itr_4 << endl;
return 0;
}
出力
There are 2 9s
There is 1 55
There is 0 101
There are 2 4
std :: count_if
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate red);
エフェクト
指定された述語関数が真である範囲内の要素の数を数えます。
パラメーター
first =>範囲の先頭を指すイテレータlast =>範囲の終わりを指すイテレータred =>述語関数（trueまたはfalseを返します）
戻る
述部関数がtrueを戻した、指定された範囲内の要素の数。
例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
Define a few functions to use as predicates
*/
//return true if number is odd
bool isOdd(int i){
return i%2 == 1;
}
//functor that returns true if number is greater than the value of the constructor parameter provided
class Greater {
int _than;
public:
Greater(int th): _than(th){}
bool operator()(int i){
return i > _than;
}
};
int main(int argc, const char * argv[]) {
//create a vector
vector<int> myvec = {1,5,8,0,7,6,4,5,2,1,5,0,6,9,7};
//using a lambda function to count even numbers
size_t evenCount = count_if(myvec.begin(), myvec.end(), [](int i){return i % 2 == 0;}); // >= C++11
//using function pointer to count odd number in the first half of the vector
size_t oddCount = count_if(myvec.begin(), myvec.end()- myvec.size()/2, isOdd);
//using a functor to count numbers greater than 5
size_t greaterCount = count_if(myvec.begin(), myvec.end(), Greater(5));
cout << "vector size: " << myvec.size() << endl;
cout << "even numbers: " << evenCount << " found" << endl;
cout << "odd numbers: " << oddCount << " found" << endl;
cout << "numbers > 5: " << greaterCount << " found"<< endl;
return 0;
}
出力
vector size: 15
even numbers: 7 found
odd numbers: 4 found
numbers > 5: 6 found
std :: find_if
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
エフェクト
述語関数predがtrueを返す範囲内の最初の要素を検索predます。
パラメーター
first =>範囲の先頭を指すイテレータlast =>範囲の終わりを指すイテレータpred =>述語関数（trueまたはfalseを返します）
戻る
述部関数predの範囲内の最初の要素を指すイテレーターはtrueを返します。イテレータは、valが見つからない場合には最後を指す
例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
define some functions to use as predicates
*/
//Returns true if x is multiple of 10
bool multOf10(int x) {
return x % 10 == 0;
}
//returns true if item greater than passed in parameter
class Greater {
int _than;
public:
Greater(int th):_than(th){
}
bool operator()(int data) const
{
return data > _than;
}
};
int main()
{
vector<int> myvec {2, 5, 6, 10, 56, 7, 48, 89, 850, 7, 456};
//with a lambda function
vector<int>::iterator gt10 = find_if(myvec.begin(), myvec.end(), [](int x){return x>10;}); // >= C++11
//with a function pointer
vector<int>::iterator pow10 = find_if(myvec.begin(), myvec.end(), multOf10);
//with functor
vector<int>::iterator gt5 = find_if(myvec.begin(), myvec.end(), Greater(5));
//not Found
vector<int>::iterator nf = find_if(myvec.begin(), myvec.end(), Greater(1000)); // nf points to myvec.end()
//check if pointer points to myvec.end()
if(nf != myvec.end()) {
cout << "nf points to: " << *nf << endl;
}
else {
cout << "item not found" << endl;
}
cout << "First item > 10: " << *gt10 << endl;
cout << "First Item n * 10: " << *pow10 << endl;
cout << "First Item > 5: " << *gt5 << endl;
return 0;
}
出力
item not found
First item > 10: 56
First Item n * 10: 10
First Item > 5: 6
std :: min_element
template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last,Compare comp);
エフェクト
範囲内の最小要素を検索します。
パラメーター
first - 反復子が範囲の先頭を指している
last - 範囲の終わりを指すイテレータcomp - 2つの引数をとり、引数が引数2より小さいかどうかを示すtrueまたはfalseを返す関数ポインタまたは関数オブジェクト。この関数は入力を変更するべきではない
戻る
範囲内の最小要素までのイテレータ
複雑
比較される要素の数より1つ少ない線形。
例
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility> //to use make_pair
using namespace std;
//function compare two pairs
bool pairLessThanFunction(const pair<string, int> &p1, const pair<string, int> &p2)
{
return p1.second < p2.second;
}
int main(int argc, const char * argv[]) {
vector<int> intVec {30,200,167,56,75,94,10,73,52,6,39,43};
vector<pair<string, int>> pairVector = {make_pair("y", 25), make_pair("b", 2), make_pair("z", 26), make_pair("e", 5) };
// default using < operator
auto minInt = min_element(intVec.begin(), intVec.end());
//Using pairLessThanFunction
auto minPairFunction = min_element(pairVector.begin(), pairVector.end(), pairLessThanFunction);
//print minimum of intVector
cout << "min int from default: " << *minInt << endl;
//print minimum of pairVector
cout << "min pair from PairLessThanFunction: " << (*minPairFunction).second << endl;
return 0;
}
出力
min int from default: 6
min pair from PairLessThanFunction: 2
std :: nth_elementを使用してメディアン（またはその他の数量）を検索する
std::nth_elementアルゴリズムは、最初のイテレータ、 n番目の位置、および最後の3つのイテレータを使用します。関数が復帰すると、 n番目の要素（順序で）はn番目に小さい要素になります。 （この関数には、より複雑なオーバーロードがあります（例えば、いくつかの比較関数を使用するなど）。すべてのバリエーションについては上のリンクを参照してください。
メモこの関数は非常に効率的です - 線形の複雑さがあります。
この例のために、長さnのシーケンスの中央値を位置⌈n/2⌉にある要素として定義しましょう。例えば、長さ5のシーケンスの中央値は3番目に小さいエレメントであり、長さ6のシーケンスの中央値も同様である。
この関数を使用して中央値を求めるには、以下を使用できます。私たちは
std::vector<int> v{5, 1, 2, 3, 4};
std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();
std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2);
// This makes the 2nd position hold the median.
std::nth_element(b, med, e);
// The median is now at v[2].
p番目の分位数を見つけるには、上の行のいくつかを変更します。
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
ポジションpos分位数を探します。
