出力パラメータ、ムーブ セマンティクス、およびステートフル アルゴリズム

9 月の GoingNative で、Andrei Alexandrescu が API 設計と C++11 に関する興味深い質問を投げかけ、1 か月間頭を悩ませました。 std::getlineのデザインについてでした :

// Read a line from sin and fill in buf. Return sin.
std::istream& getline(std::istream& sin, std::string& buf)
{
    buf.clear();
    // ... fill in buf
    return sin;
}

ベテランのプログラマーは、このパターンを認識しています:関数は非 const 参照によってバッファーを取得し、それを埋めます。また、インターフェースがこのように設計されている理由も知っています:std::string のようなコンテナーのため コピーするにはコストが高すぎて、値によって返すことを検討できません。このように設計された API には、伝統的に効率的であるという利点がありましたが、呼び出しサイトでの不便さを犠牲にしてきました:

std::string buf;
std::getline(std::cin, buf);
use_line(buf);

C++11 では、std::string のような標準コンテナ 移動可能であるため、値で 1 つを返すことはほとんど無料です。したがって、おそらくより良い API 設計は次のようになります:

// Should getline look like this instead?
std::string getline(std::istream& sin)
{
    std::string buf;
    // ... fill in buf
    return buf; // This gets moved out efficiently
}

これにより、より簡潔で自然な使用法が可能になり、ユーザーが名前付き変数を作成する必要がなくなります:

use_line(getline(std::cin));

いいですね。つまり、getline かどうかわからないという明らかな欠点は別として、 成功したかどうか。おっとっと。しかし、それを見過ごしても、ここに問題があります。

パフォーマンス、パフォーマンス、パフォーマンス

移動のセマンティクスのおかげで、高価なコレクションを値で返すというお粗末なパフォーマンスについて心配する必要はないと思うかもしれません。その通りです。並べ替え。しかし、この getline の使い方を考えてみてください :

std::string buf;
while(std::getline(std::cin, buf))
    use_line(buf); 

buf を使用する代わりに、このコードが何をするかを考えてみましょう。 出力パラメータとして、getline 新しい string を作成しました 値で返します。さて、新しい string を作成しています 毎回 、当たり前。しかし、上記のコードはそれを行いません。ループを数回繰り返した後、buf おそらく、次に読み取られる行を保持するのに十分な大きさであり、そのスペースはそれ以上の割り当てなしで再利用できます。はるかに高速です。

製図板に戻る

GoingNative の間、Andrei は getline を離れました そこの。 (彼は別のデザインを好むことがわかりました。同様の結論に達するでしょう。)私は議論を続けたいと思いました. Out パラメータは見苦しく使いにくい、API の構成可能性を損なう、オブジェクトを宣言して別の手順で初期化することを強制する、アクネの原因になる、などなどです。

問題のあるコードをもう少し調べました:

std::string buf;
while(std::getline(std::cin, buf))
    use_line(buf); 

このコードは何をしていますか?一連の行を読み取って、一度に 1 つずつ処理していますよね? 範囲を返しているとさえ言うかもしれません 行の。それからそれは私を襲った:std::getline 間違った API です! getlines という名前にする必要があります (複数) であり、文字列の範囲を返す必要があります。ご覧ください:

for(std::string& buf : getlines(std::cin))
    use_line(buf);

この API は、私にとってより適切に感じられます。使いやすいだけでなく (ほら! 1 行少ない!)、オブジェクトの 2 段階の初期化を強制せず、範囲と範囲操作が作成されます。 (これについては後で詳しく説明します。) また、最初に試したときのようなパフォーマンスの問題もありませんが、その理由を確認するには多少の作業が必要です。

レイジーレンジ

私の getlines は何ですか 関数リターン?確かに std::vector には入りません string の と返します。 istream から潜在的に無限の行数を読み取ることができるため、(a) ばかであり、(b) 高価であり、(c) 実際には不可能です。 .代わりに、getlines lazy を返します。

遅延範囲は、必要に応じて要素を生成するものです。 STL にはすでに次のようなものがあります:std::istream_iterator . istream_iterator から範囲を作成できます istream から文字 (または int など) を取得する s オンデマンド。そのようなものが必要ですが、行が必要です。

残念ながら、istream_interator を押すことはできません 私たちのためにサービスを開始します。代わりに、独自のイテレータ型を記述し、そこから有効な範囲を構築する必要があります。これは面倒で冗長なプログラミング作業ですが、Boost.Iterator が役に立ちます。かなり最小限のインターフェイスからイテレータを構築できるいくつかのヘルパーがあります。これ以上苦労することなく、これが lines_iterator です :

struct lines_iterator
  : boost::iterator_facade<
        lines_iterator,
        std::string,            // value type
        std::input_iterator_tag // category
    >
{
    lines_iterator() : psin_{}, pstr_{}, delim_{} {}
    lines_iterator(std::istream *psin,
                   std::string *pstr,
                   char delim)
        : psin_(psin), pstr_(pstr), delim_(delim)
    {
        increment();
    }
private:
    friend class boost::iterator_core_access;

    void increment()
    {
        if(!std::getline(*psin_, *pstr_, delim_))
            *this = lines_iterator{};
    }

    bool equal(lines_iterator const & that) const
    {
        return pstr_ == that.pstr_;
    }

    std::string & dereference() const
    {
        return *pstr_;
    }

    std::istream *psin_;
    std::string *pstr_;
    char delim_;
};

lines_iterator をインクリメントすると魔法が起こります 、これは lines_iterator::increment で発生します . std::getline が呼び出され、pstr_ によって参照されるバッファに入力されます .毎回同じバッファを使用することに注意してください。 lines_iterator を逆参照すると、 、そのバッファへの参照を返します。コピーも不要な割り当てもありません。

pstr_ が参照するバッファはどこですか 住む? lines_rangegetlines によって返されるオブジェクト .

using lines_range_base =
    boost::iterator_range<lines_iterator>;

struct lines_range_data {std::string str_;};

struct lines_range
    : private lines_range_data, lines_range_base
{
    explicit lines_range(std::istream & sin,
                         char delim = 'n')
        : lines_range_base{
              lines_iterator{&sin, &str_, delim},
              lines_iterator{}}
    {}
};

inline
lines_range getlines(std::istream& sin, char delim = 'n')
{
    return lines_range{sin, delim};
}

lines_range 本当にただの boost::iterator_range です lines_iterator の 秒。 str_ を初期化するために多少のゆがみが必要でした のメンバー iterator_range コンストラクターが呼び出されました (したがって、lines_range_data が必要です) ) ですが、これは単なる実装成果物です。

要点は次のとおりです:getlines を呼び出すとき 、あなたは lines_range を返します これは基本的に自由な操作です。 .begin() に電話できるようになりました および .end() または、範囲ベースの for を使用して直接反復処理します 私が示したようにループします。元の std::getline よりも、このインターフェイスを使用してメモリ割り当てが行われることはありません。 API。いいね、え?

範囲と範囲アルゴリズムの構成可能性

範囲ベースの getlines を好む理由はたくさんあります API — および一般的な範囲ベースのインターフェイス。最も直接的なメリットは、範囲ベースの for を使用できることです。 上で示したように、ループします。しかし、レンジ アルゴリズムとレンジ アダプターを使い始めると、真の力が発揮されます。 Boost と Adob​​e の ASL はどちらも、範囲を操作するための強力なユーティリティを提供しており、C++ 標準化委員会には、標準の将来のバージョンの範囲専用のワーキング グループがあります。そして正当な理由があります!範囲操作は構成するため、たとえば、次のようなことができます:

// Read some lines, select the ones that satisfy
// some predicate, transform them in some way and
// echo them back out
boost::copy(
    getlines(std::cin)
        | boost::adaptors::filtered(some_pred)
        | boost::adaptors::transformed(some_func),
    std::ostream_iterator<std::string>(std::cout, "n"));

それは強いものです。ストレート イテレータと STL アルゴリズムを使用した同等のコードがどのようになるかを考えるとぞっとします。

しかし、1 行だけ読みたい場合はどうすればよいでしょうか。新しい getlines ではありませんか この単純な使用シナリオであなたを傷つけましたか?いいえ!必要なのは、範囲の最初の要素を返す 1 つの完全に一般的な関数だけです。 front としましょう :

using std::begin;

// return the front of any range    
template<typename Range>
auto front(Range && rng)
    -> decltype(boost::make_optional(*begin(rng)))
{
    for(auto x : rng)
        return x;
    return boost::none;
}

範囲が空の可能性があるため、optional を返す必要があります . istream から 1 行を読み取ることができるようになりました このように:

if(auto s = front(getlines(std::cin)))
    use_line(*s);

これをオリジナルと比較すると、それほど悪くないことがわかると思います:

std::string str;
if(std::getline(std::cin, str))
    use_line(str);

ステートフル アルゴリズム

getline で Andrei のすべての懸念事項に完全に対処しました。 ?はいといいえ。確かに getline を修正しました 、しかしアンドレイのポイントはもっと大きかった。彼は、ムーブ セマンティクスが魔法のようにプログラムを高速化することを期待して、やみくもに値を渡したり返したりすることはできないことを示していました。そして、それは有効なポイントです。その事実を変えるようなことは何も言えません.

getlineだと思います 一見、純粋な out パラメータのように見えるものは、実際には in/out パラメータであるため、興味深い例です。途中、getline 渡されたバッファの容量を使用して効率を高めます。これは getline を置きます 何かをキャッシュまたは事前計算する機会がある場合に、より適切に機能する大規模なクラスのアルゴリズムに変換されます。 できます それについて何か言ってください。

アルゴリズムがキャッシュまたは事前計算されたデータ構造を必要とする場合、アルゴリズムは本質的にステートフル です。 . 1 つのオプションは、getline のように毎回状態を渡すことです。 します。より良いオプションは、アルゴリズムを実装するオブジェクトに状態をカプセル化することです。私たちの場合、状態はバッファで、オブジェクトは範囲でした。別の例を挙げると、Boyer-Moore 検索は strstr よりも高速です それは物事を事前計算するからです。 Boost 実装では、boyer_moore 事前計算された部分をプライベートに保つステートフルな関数オブジェクトです。

まとめ

主なポイントは次のとおりです。

  • キャッシュまたは事前計算されたデータ構造を使用してアルゴリズムが高速に実行される場合は、ユーザーに状態を渡すよう強制するのではなく、アルゴリズムを実装するオブジェクトに状態をカプセル化してください。
  • API の設計は、予想される API の使用シナリオと、最新の C++11 の一般的なイディオムに基づいている必要があります。
  • 範囲に対する操作が構成されるため、範囲は強力な抽象化です。
  • Boost.Iterator と Boost.Range は、カスタム範囲を実装する作業を大幅に簡素化します。

読んでくれてありがとう!

x