1

私が欲しいもの：そのベースイテレータが指す要素よりも辞書編集的に大きい（>）別のイテレータ（ベースイテレータと呼びましょう）の後の次の要素へのイテレータ（つまり、「a」があり、残りが[c,d,a,b] b、または b へのイテレータが必要です)。そのために使用できる <algorithm> 関数を認識していないため、必要に応じて「手動で」実行しています。

どうすればできると思いますか: このラムダを、コレクションに対して何らかの累積を使用して実行します。

[mism.first](it_t acc, it_t el) 
{ 
    if(*el > *mism.first) { 
        return iter_min(acc,el); 
    } 
    return acc; 
}

(iter_min(a,b) は *a<=*b の場合、mism.first は「ベース イテレータ」と呼ばれます)。しかし、累積は反復子ではなく値に対して機能するため、できません。イテレータにこのようなものはありますか？もしそうでなければ、私はそれを書くべきだと言いますか (私はそれで自分自身を過度に運動させるとは思いません)、それとも単に「間違った」方法で行っているだけですか (ちなみに、私は交換することになります)これは next_permutation と非常によく似ているように聞こえることはわかっていますが、私が行っていることは順列と多くの関係がありますが、それは私が望んでいるものとはまったく異なります)?

4

3 に答える 3

2

私が見る最も簡単な可能性は、 からの連続する反復子で構成される反復可能な範囲を作成することです[base, end)。これはBoost.Iteratorscounting_iteratorで可能ですが、boost がなくてもかなり簡単に実装できるはずです。

提案されたラムダは、ほぼそのまま機能します。

some_iterator base = ..., end = ...;
some_iterator the_next_least_thing =
  std::accumulate(boost::make_counting_iterator(base),
                  boost::make_counting_iterator(end),
                  end,
                  [=](some_iterator acc, some_iterator cur) { 
                     return (*cur > *base && (acc == end || *cur < *acc)) ? cur : acc });
于 2012-10-18T22:02:13.183 に答える
1

find_if を使用して、開始点として iterator+1 を指定します。

bool mycomp (char c1, char c2)
{ return lexicographical_compare(*c1,*c1,*c2,*c2); }    

vector<char>::iterator nextBigger = find_if(it+1,end,mycomp)

std lib の lexicographic_compare ルーチンとfind_ifから適応。

于 2012-10-18T22:20:31.237 に答える
1

ベースよりも大きい最初の要素を見つけるには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));
于 2012-10-18T20:00:15.353 に答える