<stx/algorithm>
DDJ-J 1998年5月号で紹介したSTL拡張コンポーネント”STX”の改版です。
初版で定義した関数のうち、使用頻度の少ないもの、
既存のアルゴリズムで簡単に置き換えられるものを除き、新たにいくつか追加しました。
- for_each
- for_each_backward
- find_last
- find_last_if
- find_backward
- find_backward_if
- binary_find
- some
- some_if
- every
- every_if
- select_copy
- select_copy_if
- transform_if
- inject_1st
- inject_2nd
- partition_copy
- is_sorted
- lexicographical_compare_3way
for_each
template<class InputIterator1,
class InputIterator2,
class BinaryFunction>
BinaryFunction
for_each(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
BinaryFunction f)
{
while ( first1 != last1 ) {
f(*first1,*first2);
++first1;
++first2;
}
return f;
}
0 <= i < (last-first) に対し、f(*(first1+i), *(first2+i)) を行ないます。このとき f() の戻り値は棄てられます。
// sample
void f(int x, int y) {
cout << (x*y) << endl;
}
vector<int> v;
list<int> l;
for ( int i = 1; i < 10; ++i ) {
v.push_back(i);
l.push_back(i);
}
// 1*1 2*2 ... 9*9 の答を出力
stx::for_each(v.begin(), v.end(), l.begin(), l.end(), f);
for_each_backward
template<class BidirectionalIterator,
class UnaryFunction>
UnaryFunction
for_each_backward(BidirectionalIterator first,
BidirectionalIterator last,
UnaryFunction f)
{
while ( first != last ) {
--last;
f(*last);
}
return f;
}
std::for_each(first,last,f)の逆順すなわち、
f(*(last-1)); f(*(last-2)); ... f(*first);
を行ないます。
// sample
void f(int x, int y) {
cout << (x*y) << endl;
}
vector<int> v;
list<int> l;
for ( int i = 1; i < 10; ++i ) {
v.push_back(i);
l.push_back(i);
}
// 9*9 8*8 ... 1*1の答を出力
stx::for_each_backward(v.begin(), v.end(), l.begin(), l.end(), f);
find_last
template<class InputIterator,
class T>
InputIterator
find_last(InputIterator first,
InputIterator last,
const T& value)
{
InputIterator it = first;
while ( first != last ) {
if ( *first == value ) {
it = first;
}
++first;
}
return it;
}
first <= i < last に対し、*i == value となる最後のiを返します。該当する i が見つからないときは last を返します。※必ず(last – first)回の比較が行なわれます。
// sample
int array[] = { 0, 1, 2, 4, 5 };
int* p = stx::find_last(array, array+5, 4);
cout << (p-array) << endl; // p = &array[3]
find_last_if
template<class InputIterator,
class UnaryPredicate>
InputIterator
find_last_if(InputIterator first,
InputIterator last,
UnaryPredicate pred)
{
InputIterator it = first;
while ( first != last ) {
if ( pred(*first) ) {
it = first;
}
++first;
}
return it;
}
first <= i < last に対し、pred(*i) != false となる最後のiを返します。該当する i が見つからないときは last を返します。必ず (last – first) 回の比較が行なわれます。
// sample
bool gt1(int x) {
return x > 1;
}
int array[] = { 0, 1, 2, 4, 5 };
int* p = stx::find_last_if(array, array+5, gt1);
cout << (p-array) << endl; // p = &array[2]
find_backward
template<class BidirectionalIterator,
class T>
BidirectionalIterator
find_backward(BidirectionalIterator first,
BidirectionalIterator last,
const T& value)
{
BidirectionalIterator it = last;
while ( first != last ) {
--last;
if ( *last == value ) {
return last;
}
}
return it;
}
first <= i < last に対し、*i == value となる最後のiを返します。該当する i が見つからないときは last を返します。find_last()と異なり、シーケンスを逆順(last-1からfirstに向かって)検索します。
// sample
int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::find_backward(array, array+5, 2);
cout << (p-array) << endl; // p = &array[3]
find_backward_if
template<class BidirectionalIterator,
class UnaryPredicate>
BidirectionalIterator
find_backward_if(BidirectionalIterator first,
BidirectionalIterator last,
UnaryPredicate pred)
{
BidirectionalIterator it = last;
while ( first != last ) {
--last;
if ( pred(*last) ) {
return last;
}
}
return it;
}
first <= i < last に対し、pred(*i) != false となる最後のiを返します。該当する i が見つからないときは last を返します。find_last()と異なり、シーケンスを逆順(last-1からfirstに向かって)検索します。
// sample
bool gt1(int x) {
return x > 1;
}
int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::find_backward_if(array, array+5, gt1);
cout << (p-array) << endl; // p = &array[4]
binary_find
template<class ForwardIterator,
class T>
ForwardIterator
binary_find(ForwardIterator first,
ForwardIterator last,
const T& value)
{
ForwardIterator t = std::lower_bound(first,last,value);
return ( t == last || value < *t ) ? last : t;
}
ソートされたシーケンス[first,last)からvalueと等しい要素を探し、それを指すイテレータを返します。該当する要素が見つからないときは last を返します。バイナリサーチを行なうため、時間計算量は log(last – first) です。
// sample
int array[] = { 0, 1, 2, 2, 5 };
int* p = stx::binary_find(array, array+5, 2);
cout << (p-array) << endl; // p = &array[2]
template<class ForwardIterator,
class T,
class BinaryPredicate>
ForwardIterator
binary_find(ForwardIterator first,
ForwardIterator last,
const T& value,
BinaryPredicate pred)
{
ForwardIterator t = std::lower_bound(first,last,value,pred);
return ( t == last || pred(value,*t) ) ? last : t;
}
predに従ってソートされたシーケンス[first,last)からvalueと等しい要素を探し、それを指すイテレータを返します。該当する要素が見つからないときは last を返します。バイナリサーチを行なうため、時間計算量は log(last – first) です。
// sample
int array[] = { 5, 2, 2, 1, 0 };
int* p = stx::find_backward(array, array+5, 2, greater<int>());
cout << (p-array) << endl; // p = &array[1]
some
template<class InputIterator,
class T>
bool
some(InputIterator first,
InputIterator last,
const T& val)
{
while ( first != last ) {
if ( *first == val ) {
return true;
}
++first;
}
return false;
}
first <= i < last に対し、*i == value となる i が少なくともひとつあれば true を返します。
// sample
int array[] = { 5, 2, 2, 1, 0 };
bool t = stx::some(array, array+5, 1); // t = true;
some_if
template<class InputIterator,
class UnaryPredicate>
bool
some_if(InputIterator first,
InputIterator last,
UnaryPredicate pred)
{
while ( first != last ) {
if ( pred(*first) ) {
return true;
}
++first;
}
return false;
}
first <= i < last に対し、pred(*i) != false となる i が少なくともひとつあれば true を返します。
// sample
bool gt1(int x) {
return x > 1;
}
int array[] = { 0, 1, 0, 1, 0 };
bool t = stx:some_if(array, array+5, gt1); // t = false;
every
template<class InputIterator,
class T>
bool
every(InputIterator first,
InputIterator last,
const T& val)
{
while ( first != last ) {
if ( !(*first == val) ) {
return false;
}
++first;
}
return true;
}
first <= i < last であるすべての i に対し、*i == value であれば true を返します。
// sample
int array[] = { 2, 3, 4, 5, 6 };
bool t = stx::every(array, array+5, 3); // t = false;
every_if
template<class InputIterator,
class UnaryPredicate>
bool
every_if(InputIterator first,
InputIterator last,
UnaryPredicate pred)
{
while ( first != last ) {
if ( !pred(*first) ) {
return false;
}
++first;
}
return true;
}
first <= i < last であるすべての i に対し、pred(*i) != false であれば true を返します。
// sample
bool gt1(int x) {
return x > 1;
}
int array[] = { 2, 3, 4, 5, 6 };
bool t = stx::every(array, array+5, 3); // t = true;
select_copy
template<class InputIterator,
class OutputIterator,
class T>
OutputIterator
select_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T& value)
{
while ( first != last ) {
if ( *first == value ) {
*result = *first;
++result;
}
++first;
}
return result;
}
first <= i < last に対し、*i == value となる *i を [result,RET)にコピーします。RET は select_copy の戻り値です。
// sample
int array[] = { 5, 1, 2, 1, 0 };
vector<int> v;
stx::select_copy(array, array+5,back_inserter(V), 1); // v = { 1, 1 }
select_copy_if
template<class InputIterator,
class OutputIterator,
class UnaryPredicate>
OutputIterator
select_copy_if(InputIterator first,
InputIterator last,
OutputIterator result,
UnaryPredicate pred)
{
while ( first != last ) {
if ( pred(*first) ) {
*result = *first;
++result;
}
++first;
}
return result;
}
first <= i < last に対し、pred(*i) != false となる *i を [result,RET)にコピーします。RET は select_copy の戻り値です。
// sample
bool gt1(int x) {
return x > 1;
}
int array[] = { 5, 1, 2, 1, 0 };
vector<int> v;
stx::select_copy_if(array, array+5,back_inserter(V), gt1); // v = { 5, 2 }
transform_if
template<class InputIterator,
class OutputIterator,
class UnaryFunction,
class UnaryPredicate>
OutputIterator
transform_if(InputIterator first,
InputIterator last,
OutputIterator result,
UnaryFunction fn,
UnaryPredicate pred)
{
while ( first != last ) {
if ( pred(*first) ) {
*result = fn(*first);
++result;
}
++first;
}
return result;
}
first <= i < last , pred(*i) != false となる i に対し、fn(*i)を [result,RET)にコピーします。RET は select_copy の戻り値です。
// sample
bool positive(int x) {
return x > 0;
}
int twice(int x) {
return x*2;
}
int array[] = { -2, 1, 0, 3, 2 };
vector<int> v;
stx::transform_if(array, array+5,back_inserter(V), twice, positive); // v = { 1*2, 3*2, 2*2 }
template<class InputIterator1,
class InputIterator2,
class OutputIterator,
class BinaryFunction,
class BinaryPredicate>
OutputIterator
transform_if(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
OutputIterator result,
BinaryFunction fn,
BinaryPredicate pred)
{
while ( first1 != last1 ) {
if ( pred(*first1,*first2) ) {
*result = fn(*first1,*first2);
++result;
}
++first1;
++first2;
}
return result;
}
0 <= i < (last1 - first1), pred(*(first1+i),*(first2+i)) != false となる i に対し、fn(*(first1+i),*(first2+i))を [result,RET)にコピーします。RET は select_copy の戻り値です。
// sample
bool positive(int x, int y) {
return x * y > 0;
}
int array1[] = { -2, 1, 0, 3, -2 };
int array2[] = { -2, -1, 0, 4, 2 };
vector<int> v;
stx::transform_if(array1, array1+5,
array2, back_inserter(V),
multiplies<int>(), positive); // v = { 2*-2, 3*4 }
inject_1st
template<class InputIterator,
class BinaryFunction,
class T>
T
inject_1st(InputIterator first,
InputIterator last,
BinaryFunction fn,
const T& init)
{
T result(init);
while ( first != last ) {
result = fn(result,*first);
++first;
}
return result;
}
first <= i < last に対し、x = fn(x,*i); を順に適用し、最終的に選られたxを返します。x の型は T, 初期値は init です。
// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = stx::inject_1st(array, array+5, plus<int>(), 0); // n = 15
inject_2nd
template<class InputIterator,
class BinaryFunction,
class T>
T
inject_2nd(InputIterator first,
InputIterator last,
BinaryFunction fn,
const T& init)
{
T result(init);
while ( first != last ) {
result = fn(*first,result);
++first;
}
return result;
}
first <= i < last に対し、x = fn(*i,x); を順に適用し、最終的に選られたxを返します。x の型は T, 初期値は init です。
// sample
int array[] = { 1, 2, 3, 4, 5 };
int n = stx::inject_2nd(array, array+5, plus<int>(), 0); // n = 15
partition_copy
template<class InputIterator,
class OutputIterator1,
class OutputIterator2,
class UnaryPredicate>
std::pair<OutputIterator1,OutputIterator2>
partition_copy(InputIterator first,
InputIterator last,
OutputIterator1 result1,
OutputIterator2 result2,
UnaryPredicate pred)
{
while ( first != last ) {
if ( pred(*first) ) {
*result1 = *first;
++result1;
} else {
*result2 = *first;
++result2;
}
++first;
}
return std::pair<OutputIterator1,OutputIterator2>(result1,result2);
}
first < i <= last に対し、pred(*i) != false ならば [result1,RET.first)に、pred(*i) == false ならば [result2,RET.second)に *iをコピーします。RET は partition_copy() の戻り値です。
// sample
bool positive(int x) {
return x > 0;
}
int array[] = { 1, -2, 3, -4, 5 };
vector<int> v;
list<int> l;
stx::partition_copy(array, array+5,
back_inserter(v), back_insserter(l),
positive); // v = { 1, 3, 5 }, l = { -2, -4 }
is_sorted
template<class InputIterator>
bool
is_sorted(InputIterator first,
InputIterator last)
{
if ( first == last ) {
return true;
}
InputIterator next = first;
++next;
while ( next != last ) {
if ( *next < *first ) {
return false;
}
++first;
++next;
}
return true;
}
first <= i , i+1 <= last なるすべての i,i+1 に対し、*i < *(i+1) であれば true を返します。
// sample
int array[] = { 0, 1, 1, 2, 3 };
bool t = stx::is_sorted(array, array+5); // t = true;
template<class InputIterator,
class BinaryFunction>
bool
is_sorted(InputIterator first,
InputIterator last,
BinaryFunction comp)
{
if ( first == last ) {
return true;
}
InputIterator next = first;
++next;
while ( next != last ) {
if ( comp(*next,*first) ) {
return false;
}
++first;
++next;
}
return true;
}
first <= i , i+1 <= last なるすべての i,i+1 に対し、comp(*(i+1),*i) == false であれば true を返します。
// sample
int array[] = { 3, 2, 2, 1, 0 };
bool t = stx::is_sorted(array, array+5, greater<int>()); // t = true;
lexicographical_compare_3way
template <class InputIterator1,
class InputIterator2>
int
lexicographical_compare_3way(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2)
{
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2) {
return -1;
}
if (*first2 < *first1) {
return 1;
}
++first1;
++first2;
}
if (first2 == last2) {
return !(first1 == last1);
} else {
return -1;
}
}
2つのシーケンス[first1,last1), [first2,last2)を辞書順に比較し、[first1,last1) < [first2,last2) ならば -1、[first1,last1) = [first2,last2) ならば 0、[first1,last1) > [first2,last2) ならば 1 を返します。
// sample string s1 = "apple"; const char* s2 = "apple"; int t = stx::lexicographical_compare_3way(s1.begin(), s1.end(), s2, s2+strlen(s2)); // t = 0
template <class InputIterator1,
class InputIterator2,
class BinaryPredicate>
int
lexicographical_compare_3way(InputIterator1 first1,
InputIterator1 last1,
InputIterator2 first2,
InputIterator2 last2,
BinaryPredicate pred)
{
while (first1 != last1 && first2 != last2) {
if ( pred(*first1,*first2) ) {
return -1;
}
if ( pred(*first2,*first1) ) {
return 1;
}
++first1;
++first2;
}
if (first2 == last2) {
return !(first1 == last1);
} else {
return -1;
}
}
2つのシーケンス[first1,last1), [first2,last2)をpredに従って辞書順に比較し、[first1,last1) < [first2,last2) ならば -1、[first1,last1) = [first2,last2) ならば 0、[first1,last1) > [first2,last2) ならば 1 を返します。
// sample
bool ignorecase_less(char x, char y) {
return toupper(x) < toupper(y);
}
string s1 = "apple";
const char* s2 = "APPLA";
int t = stx::lexicographical_compare_3way(s1.begin(), s1.end(), s2, s2+strlen(s2),
ignorecase_less); // t = -1