1

C++ std アルゴリズムは、入力シーケンスと出力シーケンスを取り、入力シーケンスの要素から出力シーケンスの要素を作成する多数のアルゴリズムを定義します。(最良の例はstd::transform.)

std アルゴリズムは明らかiteratorsにOutputIterator.

あれは：

std::vector<int> v1; // e.g. v1 := {1, 2, 3, 4, 5};

std::vector<int> squared;
squared.reserve(v1.size()); // not strictly necessary
std::transform(v1.begin(), v1.end(), std::back_inserter(squared), 
               [](int x) { return x*x; } ); // λ for convenience, needn't be C++11

そして、これは標準ライブラリに関する限り問題ありません。イテレータが面倒すぎると感じたときは、Boost.Rangeを使って単純化することがよくあります。

ただし、この場合、Boost.Range の変更アルゴリズム もを使用しているようOutputIteratorsです。

だから私は現在、そこに便利なライブラリがあるかどうか疑問に思っています.

std::vector<int> const squared = convenient::transform(v1, [](int x) { return x*x; });

――もし無いのなら、無いのには何か理由があるのでしょうか？

編集：実装例（これがすべての場合に機能するかどうか、およびこれが最も理想的なものであるかどうかは不明です）：

template<typename C, typename F>
C transform(C const& input, F fun) {
   C result;
   std::transform(input.begin(), input.end(), std::back_inserter(result), fun);
   return result;
}

（注：convenient::transform返されたベクトルは（N）RVOのためにコピーされないため、手書きのものと同じパフォーマンス特性を持つと思います。とにかく、この質問ではパフォーマンスは二次的なものだと思います。）

編集/注:これまでに提供された回答(コメント、実際)のうち、Davidは非常に優れた基本的な一般的な例を提供しています。

そしてLuc は、wrtの潜在的な問題について言及していますstd::back_inserter。ジェネリック性。

どちらも、私がこれを自分で作成することをためらう理由と、これを自分でコーディングするよりも「適切な」(適切にテストされた) ライブラリが望ましい理由を示しています。

上記の太字で表現された私の質問、つまり、あるのか、またはない理由があるのか​​ については、ほとんど答えられていません。

4

5 に答える 5

3

これは質問自体への回答ではなく、他の回答を補完するものですが、コメントには収まりません。

まあ-リストやデキュー、またはその他のシーケンスタイプのコンテナが必要な場合-それはかなり制限されています。

namespace detail {

template<typename Iter, typename Functor>
struct transform {
    Iter first, last;
    Functor functor;

    template<typename Container> // SFINAE is also available here
    operator Container()
    {
        Container c;
        std::transform(first, last, std::back_inserter(c), std::forward<Functor>(functor));
        return c;
    }
};

} // detail

template<typename Iter, typename Functor>
detail::transform<Iter, typename std::decay<Functor>::type>
transform(Iter first, Iter last, Functor&& functor)
{ return { first, last, std::forward<Functor>(functor) }; }

std::back_inserter(c)これは少数のコンテナーで機能しますが、コンテナーが(BackInsertable?)と「互換性がある」必要があるため、まだそれほど一般的ではありません。おそらく、SFINAE を使用std::inserterして、c.begin()ifc.push_back()が使用できない場合に代わりに使用できます (読者への演習として残しておきます)。

また、これはすべて、コンテナーが DefaultConstructible であることを前提としています。スコープ付きアロケーターを使用するコンテナーを検討してください。おそらく、「最も単純な」使用法のみをカバーしようとしているため、汎用性の喪失は機能です。

そして、これは実際にはそのようなライブラリを使用しませんが、懸念を分離するためにアルゴリズムのすぐ外側にコンテナを作成してもかまいません。（これは質問に対する私の答えと見なすことができると思います。）

于 2011-08-26T11:46:29.733 に答える
2

私見、そのようなアルゴリズムのポイントは、一般的であること、つまりほとんどコンテナに依存しないことです。あなたが提案しているのは、関数が非常に具体的であり、まあ、必要に応じて、または他のシーケンスタイプのコンテナを返すことです-かなり制限されていますtransform。std::vectorlistdeque

面倒くさいと思ったら、ラップしないのはなぜですか？これを行う独自の小さなユーティリティ ヘッダーを作成します。

于 2011-08-26T10:25:54.810 に答える
1

繰り返しますが、回答はありませんが、コメントから別の回答へのフォローアップです

質問コードで返される型の汎用性について

そのままのコードでは戻り値の型を変換できませんが、2 つのテンプレートを提供することで簡単に解決できます。

template <typename R, typename C, typename F>
R transform( C const & c, F f ) {_
    R res;
    std::transform( c.begin(), c.end(), std::back_inserter(res), f );
    return res;
}
template <typename C, typename F>
C transform( C const & c, F f ) {
    return transform<C,C,F>(c,f);
}
std::vector<int> src;
std::vector<int> v = transform( src, functor );
std::deque<int>  d = transform<std::deque<int> >( src, functor );
于 2011-08-26T12:40:20.300 に答える
1

有効にする唯一の正しい方法はありません

std::vector<int> const squared = 
             convenient::transform(v1, [](int x) { return x*x; });

潜在的なパフォーマンス コストなしで。明示的な

std::vector<int> const squared = 
             convenient::transform<std::vector> (v1, [](int x) { return x*x; });

コンテナーの型が明示的に言及されていることに注意してください。イテレーターは、自分が属するコンテナーについて何も伝えません。これは、コンテナーの反復子が標準で通常のポインターになることが許可されていることを思い出せば明らかです。

アルゴリズムが反復子の代わりにコンテナーを使用できるようにすることも、解決策ではありません。そうすれば、アルゴリズムは最初と最後の要素を正しく取得する方法を知ることができません。たとえば、 -array には、およびのlong intメソッドがありません。また、すべてのコンテナに定義されていないランダム アクセス イテレータがあるわけではありません。したがって、コンテナーを取得する真に一般的な方法はありません。begin()end()length()operator[]


コンテナに依存しない、コンテナを返すアルゴリズムを可能にする別の可能性は、ある種のジェネリック ファクトリです ( http://ideone.com/7d4E2のライブを参照)。

// (not production code; is even lacking allocator-types)
//-- Generic factory. -------------------------------------------
#include <list>
template <typename ElemT, typename CacheT=std::list<ElemT> >
struct ContCreator {

    CacheT cache; // <-- Temporary storage.

    // Conversion to target container type.
    template <typename ContT>
    operator ContT () const {
        // can't even move ...
        return ContT (cache.begin(), cache.end());
    }
};

テンプレート化されたキャスト演算子を除けば、それほど多くの魔法はありません。次に、アルゴリズムからそのものを返します。

//-- A generic algorithm, like std::transform :) ----------------
ContCreator<int> some_ints () {
    ContCreator<int> cc;
    for (int i=0; i<16; ++i) {
        cc.cache.push_back (i*4);
    }
    return cc;
}

最後に、次のように使用してマジック コードを記述します。

//-- Example. ---------------------------------------------------
#include <vector>
#include <iostream>
int main () {
    typedef std::vector<int>::iterator Iter;
    std::vector<int> vec = some_ints();
    for (Iter it=vec.begin(), end=vec.end(); it!=end; ++it) {
        std::cout << *it << '\n';
    }
}

ご覧のとおりoperator T、範囲コピーがあります。

ターゲット コンテナとソース コンテナが同じタイプの場合、テンプレートの特殊化によって移動が可能になる場合があります。

編集: David が指摘しているように、もちろん、変換演算子内で実際の作業を行うことができます。これには、おそらく追加のコストはかかりません (さらに作業を行うと、より便利に行うことができます。これは単なるデモ用です)。

#include <list>
template <typename ElemT, typename Iterator>
struct Impl {
    Impl(Iterator it, Iterator end) : it(it), end(end) {}

    Iterator it, end;

    // "Conversion" + Work.
    template <typename ContT>
    operator ContT () {
        ContT ret;
        for ( ; it != end; ++it) {
            ret.push_back (*it * 4);
        }
        return ret;    
    }
};

template <typename Iterator>
Impl<int,Iterator> foo (Iterator begin, Iterator end) {
    return Impl<int,Iterator>(begin, end);
}

#include <vector>
#include <iostream>
int main () {
    typedef std::vector<int>::iterator Iter;

    const int ints [] = {1,2,4,8};
    std::vector<int> vec = foo (ints, ints + sizeof(ints) / sizeof(int));

    for (Iter it=vec.begin(), end=vec.end(); it!=end; ++it) {
        std::cout << *it << '\n';
    }
}

1 つの要件は、ターゲットにpush_backメソッドがあることです。を使用std::distanceしてサイズを予約すると、target-container-iterator がランダム アクセスでない場合、パフォーマンスが最適化されない可能性があります。

于 2011-08-26T10:33:03.623 に答える
1

Boost.Range.Adaptorsは、コンテナを返すアルゴリズムと見なすことができます。それらを使用しないのはなぜですか？

実行する必要があるcreate<T>のは、適応範囲にパイプできる新しい範囲アダプターを定義し、目的の結果コンテナーを生成することだけです。

template<class T> struct converted{}; // dummy tag class

template<class FwdRange, class T>
T operator|(FwdRange const& r, converted<T>){
  return T(r.begin(), r.end());
}

ええ、それだけです。他に何も必要ありません。アダプターリストの最後にそれをパイプするだけです。

これは、Ideone の実際の例です。残念ながら、そうではありません。Ideone は C++0x モードで Boost を提供していないからです。いずれにせよ、main出力は次のとおりです。

int main(){
  using namespace boost::adaptors;
  auto range = boost::irange(1, 10);
  std::vector<int> v1(range.begin(), range.end());

  auto squared = v1 | transformed([](int i){ return i * i; });
  boost::for_each(squared, [](int i){ std::cout << i << " "; });
  std::cout << "\n========================\n";
  auto modded = squared | reversed
                        | filtered([](int i){ return (i % 2) == 0; })
                        | converted<std::vector<int>>(); // gimme back my vec!
  modded.push_back(1);
  boost::for_each(modded, [](int i){ std::cout << i << " "; });
}

出力：

1 4 9 16 25 36 49 64 81
========================
64 36 16 4 1
于 2012-02-09T05:36:54.887 に答える