ベースよりも大きい最初の要素を見つけるにはstd::find_if
、現在ポイントされている要素がベース イテレータによってポイントされている要素よりも大きい場合に true を返すラムダ述語を使用してみることができます。残念ながら、ラムダは多相的ではないstd::iterator_traits
ため、(ポインターに対しても機能するように) を使用して型を指定する必要があります。
ベースよりも大きい最小の要素を見つけるには、残りのリストでベースよりも大きい最初の要素を繰り返し検索する線形スキャンを実行し、それが現在の最小値よりも小さいかどうかを確認します。最小値を更新するたびに、反復子も現在の最小値まで増やします。これにより、残りのセクションで次の候補を探すだけで済みます。これにより、このアルゴリズムO(N)
は要素数になりますN
。
#include <algorithm>
#include <array>
#include <iostream>
#include <iterator>
template<typename FwdIt>
FwdIt first_larger(FwdIt first, FwdIt last, FwdIt base)
{
typedef typename std::iterator_traits<FwdIt>::value_type T;
return std::find_if(first, last, [=](T const& elem) {
return elem > *base;
});
}
template<typename FwdIt>
FwdIt first_larger(FwdIt first, FwdIt last)
{
return first_larger(first, last, first);
}
template<typename FwdIt>
FwdIt min_larger(FwdIt first, FwdIt last)
{
typedef typename std::iterator_traits<FwdIt>::value_type T;
auto min = last;
auto found = false;
for(auto it = first; it != last; ++it) {
auto m = first_larger(it, last, first);
if (m == last) break;
it = min = m;
found = true;
}
return found? min : last;
}
int main()
{
std::array<int,11> arr = {{ 54, 314, 5, 7, 1, -1, 0, 14, 9, 8, 6 }};
auto b = &arr[3];
auto f = first_larger(b, arr.end());
auto m = min_larger(b, arr.end());
std::cout << *b << "\n"; // 7
if(f != arr.end()) std::cout << *f << "\n"; // 14
if(m != arr.end()) std::cout << *m << "\n"; // 8
return 0;
}
おそらくこれを関数に一般化できます
template<typename FwdIt, typename Pred, typename Cmp>
FwdIt min_element_if(FwdIt first, FwdIt last, Pred pred, Cmp cmp)
{
// return iterator to smallest element satisfying Predicate
}
残念ながら、 STLには、より基本Cmp
的operator<
なアルゴリズムのそのような組み合わせは含まれていません。Boost.Iteratorを見て、フィルター アダプターを使用できます。
// equivalent to min_element_if(first, last, pred)
min_element(boost::make_filter_iterator(first, last, pred),
boost::make_filter_iterator(last, last, pred));