3

一般的にソートされていないデータ（たとえば）の配列v（たとえば、いくつかのSTLコンテナ）が与えられます。配列の要素には、たとえば、定義された比較演算子があります。最小限の要素（コピー形式）で配列を作成する必要がありますが、要素はデフォルトで構築可能ではありません（またはコストのかかる操作です）。STLを使用してそれを行う方法は？非変更シーケンスアルゴリズムが必要です。std::vector< double >assert(std::is_same< typeof(v), V >::value);std::lessnv

もともとはを使用して解決する方法と見なされていましたstd::back_insert_iteratorが、さらに説明するようにいくつかの混乱があります。

assert(!std::is_default_constructible< typename V::value_type >::value); // assume

template< class V >
V min_n_elements(typename V::const_iterator begin, typename V::const_iterator end, typename V::size_type const n)
{
    assert(!(std::distance(begin, end) < n));
    V result; // V result(n); not allowed
    result.reserve(n);
    std::partial_sort_copy(begin, end, std::back_inserter(result), /*What should be here? mb something X(result.capacity())?*/, std::less< typename V::value_type >());
    return result;
}

時間とメモリの観点から最適なソリューションを見つけたい（O（1）追加メモリと<= O（std::partial_sort_copy）時間消費）。完全にアルゴリズムは、次の数のメモリで動作する必要があります。入力としてv.size()の変更不可能なソースの要素と、出力としてのソース配列の最小要素のコピーである新しく作成された要素の要素。それで全部です。これは現実的な限界だと思います。vnnv

4

2 に答える 2

2

これらの要素もソートする必要がない限り、おそらく最も簡単で最速の使用方法std::nth_elementは 、次にstd::copy.

template <class InIter, class OutIter>
min_n_elements(InIter b, InIter e, OutIter o, InIter::difference_type n) {
   InIter pos = b+n;
   std::nth_element(b, pos, e);
   std:copy(b, pos, o);
}

std::nth_element指定された要素を見つけるだけでなく、それよりも小さい要素が「左」の 2 つであり、大きい要素が「右」にあることを保証します。

ただし、これは実際の問題を少し回避します。結果のコンテナーを実際に作成する代わりに、ユーザーが正しいタイプのコンテナーを作成し、イテレーター (back_insert_iterator など) を提供して配置することを期待するだけです。データを適切な場所に。同時に、これは本当に正しいことだと思います.N個の最小要素を見つけるアルゴリズムと、宛先のコンテナーの選択は別です。

とにかく特定のコンテナタイプに結果を入れたいのであれば、それはそれほど難しいことではありません:

template <class V>
V n_min_element(V::iterator b, V::iterator e) { 
     V::const_iterator pos = b+n;
     nth_element(b, pos, e);
     V ret(b, pos);
     return V;
}

現状では、これらは入力 (の要素の順序) を変更しますが、入力がソートされていないとあなたが言ったことを考えると、それらの順序は問題ではないと想定しているので、許容されるはずです。それができない場合、おそらく次の可能性は、ポインタのコレクションを作成し、ポインティに基づいて比較する比較関数を使用し、それに対して nth_element を実行し、最後にポインティを新しいコレクションにコピーすることです。

于 2012-11-19T05:36:08.803 に答える
2

編集:ヒープで再実装: 

template< class V > 
V min_n_elements(typename V::const_iterator b, typename V::const_iterator e, typename V::size_type const n) {
   assert(std::distance(b, e) >= n);
   V res(b, b+n);
   make_heap(res.begin(), res.end());

   for (auto i=b+n;  i<e;  ++i) {
        if (*i < res.front())  {
              pop_heap(res.begin(), res.end());
              res.back() = *i;
              push_heap(res.begin(), res.end());
        }
   }

   return std::move(res);
}
于 2012-11-19T05:37:28.487 に答える