STL学習ノート----15.STLアルゴリズム(序文区間アルゴリズム)
一.概要
すべては、順序区間に対して実行されるアルゴリズムです.
binarysearch()
ある区間に要素が含まれているかどうかを判断します.
includes()
ある区間の各要素が別の区間に含まれているかどうかを判断します.
lower.bound()
最初の「与えられた値以上」の要素を検索します.
uper_bound()
最初の「与えられた値より大きい」要素を検索します.
equal_レンゲ()
指定値に等しいすべての要素からなる区間を返します.
merge()
二つの区間を統合する
setユニオン()
二つの区間の集合を求めます.
setインターセレクション
二つの区間の交差点を求めます.
setディfference()
第一の区間に位置していますが、第二の区間に位置していないすべての要素を求めて、序文区間を形成します.
setsymmetric_ディfference()
二つの区間の一つにしか現れないすべての要素を見つけて、一つの順序区間を形成します.
inplace.merge()
二つの連続した順序区間を結合します.
二.検索要素
1.要素があるかどうかを確認する
1.二つの順番に集合した合計(Sum)
すべては、順序区間に対して実行されるアルゴリズムです.
binarysearch()
ある区間に要素が含まれているかどうかを判断します.
includes()
ある区間の各要素が別の区間に含まれているかどうかを判断します.
lower.bound()
最初の「与えられた値以上」の要素を検索します.
uper_bound()
最初の「与えられた値より大きい」要素を検索します.
equal_レンゲ()
指定値に等しいすべての要素からなる区間を返します.
merge()
二つの区間を統合する
setユニオン()
二つの区間の集合を求めます.
setインターセレクション
二つの区間の交差点を求めます.
setディfference()
第一の区間に位置していますが、第二の区間に位置していないすべての要素を求めて、序文区間を形成します.
setsymmetric_ディfference()
二つの区間の一つにしか現れないすべての要素を見つけて、一つの順序区間を形成します.
inplace.merge()
二つの連続した順序区間を結合します.
二.検索要素
1.要素があるかどうかを確認する
// [beg, end) value
bool
binary_search (ForwardIterator beg, ForwardIterator end,
const T& value)
bool
binary_search (ForwardIterator beg, ForwardIterator end,
const T& value,
BinaryPredicate op)
2.いくつかの値が存在するかどうかを確認する// [beg, end) [searchBeg, searchEnd)
bool
includes (InputIterator1 beg, InputIterator1 end,
InputIterator2 searchBeg, InputIterator2 searchEnd)
bool
includes (InputIterator1 beg, InputIterator1 end,
InputIterator2 searchBeg, InputIterator2 searchEnd,
BinaryPredicate op)
3.最初または最後の可能な位置を検索する// " value" , end
ForwardIterator
lower_bound (ForwardIterator beg, ForwardIterator end,
const T& value)
ForwardIterator
lower_bound (ForwardIterator beg, ForwardIterator end,
const T& value,
BinaryPredicate op)
// " value"
ForwardIterator
upper_bound (ForwardIterator beg, ForwardIterator end,
const T& value)
ForwardIterator
upper_bound (ForwardIterator beg, ForwardIterator end,
const T& value,
BinaryPredicate op)
4.最初と最後の可能な位置を検索する// " value "
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator beg, ForwardIterator end,
const T& value)
pair<ForwardIterator,ForwardIterator>
equal_range (ForwardIterator beg, ForwardIterator end,
const T& value,
BinaryPredicate op)
三.要素の結合1.二つの順番に集合した合計(Sum)
//source1: 1 2 2 4 6 7 7 9
//source2: 2 2 2 3 6 6 8 9
//Sum: 1 2 2 2 2 2 3 4 6 6 6 7 7 8 9 9
// [source1Beg, source1End) [source2Beg, source2End)
// destBeg
OutputIterator
merge (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
Output Iterator destBeg)
OutputIterator
merge (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
2.2つの順序セットの統合(ユニオン)//source1: 1 2 2 4 6 7 7 9
//source2: 2 2 2 3 6 6 8 9
//Union: 1 2 2 2 3 4 6 6 7 7 8 9
// ,
OutputIterator
set_union (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg)
OutputIterator
set_union (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
3.順番に集合した二つのインターレース(Intersection)//source1: 1 2 2 4 6 7 7 9
//source2: 2 2 2 3 6 6 8 9
//Inter: 2 2 6 9
//
OutputIterator
set_intersection (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg)
OutputIterator
set_intersection (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator sotirce2End,
OutputIterator destBeg,
BinaryPredicate op)
4.順番に集合した二つの差集合(ディfference)//source1: 1 2 2 4 6 7 7 9
//source2: 2 2 2 3 6 6 8 9
//differ: 1 4 7 7
// ,
OutputIterator
set_difference (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg)
OutputIterator
set_difference (InputIterator source1Beg, InputIterator source1End,
InputIterator source2Beg, InputIterator source2End,
OutputIterator destBeg,
BinaryPredicate op)
5.連結された順序区間を統合する// [beg1, end1beg2) [end1beg2, end2) ,
// [beg1, end2)
void
inplace_merge (BidirectionalIterator beg1,
BidirectionalIterator end1beg2,
BidirectionalIterator end2)
void
inplace_merge (BidirectionalIterator beg1,
BidirectionalIterator end1beg2,
BidirectionalIterator end2,
BinaryPredicate op)