範囲の概念、パート 1/4:区切られた範囲

私は最近範囲を掘り下げていて、それらが単なるイテレータのペア以上のものであることを発見しました。一連の投稿では、今日の STL 内で簡単または効率的に表現できないある種の範囲をカバーするために、範囲とは何かという概念を拡張します:delimited 範囲と無限 範囲。この投稿では、STL イテレータで区切られた範囲を表す際の問題を扱います。

区切られた範囲

コンセプトを模索するときは、いくつかの具体的な例を念頭に置いておくことが不可欠です。したがって、「区切られた範囲」と言うときは、null で終わる C スタイルの文字列と考えてください。シーケンスの最後は、既知の位置ではありません。むしろ、区切り文字が見つかると予想される未知の位置、またはより一般的には、述語が真になる未知の位置です。興味深いことに、もう 1 つの例は istream の範囲です。その場合の区切り文字は、istream エクストラクタが失敗したときです。それでも、標準には std::istream_iterator があります であるため、明らかに、区切られた範囲を STL に押し込むことは不可能ではありません。その方法と、「靴べら」という用語を使用する理由を説明します。

STL で区切られた範囲

私の「靴べら」の主張を証明するために、完全に STL 準拠のイテレータを使用した C スタイルの文字列の区切り範囲を次に示します。

#include <cassert>
#include <iostream>
#include <boost/iterator/iterator_facade.hpp>

struct c_string_range
{
private:
    char const *str_;
public:
    using const_iterator = struct iterator
      : boost::iterator_facade<
            iterator
          , char const
          , std::forward_iterator_tag
        >
    {
    private:
        friend class boost::iterator_core_access;
        friend struct c_string_range;
        char const * str_;
        iterator(char const * str)
          : str_(str)
        {}
        bool equal(iterator that) const
        {
            return str_
                ? (that.str_ == str_ ||
                     (!that.str_ && !*str_))
                : (!that.str_ || !*that.str_);
        }
        void increment()
        {
            assert(str_ && *str_);
            ++str_;
        }
        char const& dereference() const
        {
            assert(str_ && *str_);
            return *str_;
        }
    public:
        iterator()
          : str_(nullptr)
        {}
    };
    c_string_range(char const * str)
      : str_(str)
    {
        assert(str_);
    }
    iterator begin() const
    {
        return iterator{str_};
    }
    iterator end() const
    {
        return iterator{};
    }
    explicit operator bool() const
    {
        return !!*str_;
    }
};

int main()
{
    for(char c : c_string_range("hello world!"))
        std::cout << c;
    std::cout << 'n';
}

コードは、最初に末尾を計算せずに文字シーケンスをトラバースします。ダミーの終了イテレータ (センチネル) を作成して、実際のイテレータと比較するたびに、実際のイテレータが null ターミネータを指しているかどうかを確認します。全体的なロジックはすべて c_string_range::iterator::equal にあります メンバー関数。このコードを美しいとかエレガントだと言う人はいません。

現在の STL では、開始と終了の 2 つの反復子で範囲が指定されます。 std::istream_iterator のような反復子の場合 または c_string_range::iterator イテレータがセンチネルになることができる場合、最初に一方または両方のイテレータがセンチネルであるかどうかを判断する必要があるため、イテレータの等価性テストに分岐が追加されます。式 a == b 次の真理値表に従って評価されます:

a == end ? b == end ? a == b ?
true true true
true false *b == 0
false true *a == 0
false false &*a == &*b

上記のテストは実行時に評価する必要があります! アプリオリを知る方法はありません イテレータが実際のイテレータかダミーのイテレータか。そして、そのチェックはすべて高価です。これが、区切られた範囲を STL に "押し込む" ことができると私が言っていることです。快適なフィット感ではありません。

コンパイラが同意

そして、それが不快なフィット感だと言うとき、それは私の意見だけではありません.次の 2 つの関数のコードを生成しました:

int c_strlen(char const *sz)
{
    int i = 0;
    for(; *sz; ++sz)
        ++i;
    return i;
}

int range_strlen(
    c_string_range::iterator begin,
    c_string_range::iterator end)
{
    int i = 0;
    for(; begin != end; ++begin)
        ++i;
    return i;
}

2 つの関数はまったく同じことを行うため、理論上は同じコードを生成するはずです。 c_string_range::iterator::equal の複雑な条件ロジックを見た後では、Spidey 感覚がうずくはずです。 .実際、彼らが生成するコードは比較にならないほどです:

c_strlen range_strlen
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %ecx
    xorl    %eax, %eax
    cmpb    $0, (%ecx)
    je  LBB1_3
    xorl    %eax, %eax
    .align  16, 0x90
LBB1_2:
    cmpb    $0, 1(%ecx,%eax)
    leal    1(%eax), %eax
    jne LBB1_2
LBB1_3:
    popl    %ebp
    ret
        
    pushl   %ebp
    movl    %esp, %ebp
    pushl   %esi
    leal    8(%ebp), %ecx
    movl    12(%ebp), %esi
    xorl    %eax, %eax
    testl   %esi, %esi
    movl    8(%ebp), %edx
    jne LBB2_4
    jmp LBB2_1
    .align  16, 0x90
LBB2_8:
    incl    %eax
    incl    %edx
    movl    %edx, (%ecx)
LBB2_4:
    testl   %edx, %edx
    jne LBB2_5
    cmpb    $0, (%esi)
    jne LBB2_8
    jmp LBB2_6
    .align  16, 0x90
LBB2_5:
    cmpl    %edx, %esi
    jne LBB2_8
    jmp LBB2_6
    .align  16, 0x90
LBB2_3:
    leal    1(%edx,%eax), %esi
    incl    %eax
    movl    %esi, (%ecx)
LBB2_1:
    movl    %edx, %esi
    addl    %eax, %esi
    je  LBB2_6
    cmpb    $0, (%esi)
    jne LBB2_3
LBB2_6:
    popl    %esi
    popl    %ebp
    ret
        

オーマイ!これらすべてのテストとブランチを見てください。上記のコードは -O3 -DNDEBUG の clang 3.4 で生成されました .実際には、コンパイラは range_strlen のより良いコードを生成できることが多いことを付け加えておきます。 . もし コンパイラは静的に end を推論できます 実際には歩哨であり、if range_strlen の定義 をインライン化できる場合、コンパイラはより適切なコードを生成します。実際、ほぼ最適です。しかし、それらはいくつかの大きな「If」です。

その上、人々は一般的に c_string_range を書くことによって自分自身をゆがめるようなことはしません。 区切り文字列を扱うときのクラス。彼らはstrlenと呼んでいます 次に、範囲を1回ではなく2回トラバースするアルゴリズム。しかし、istream 範囲の場合を考えてみましょう。終了イテレータを見つけるだけで範囲が消費されるため、入力範囲で同じトリックを行うことはできません! std::istream_iterator の理由がわかりました ダミーの歩哨を持っています。他に方法はありません。

最後に、c_string_range::iterator に注目してください。 フォワードです 生の char const* という事実にもかかわらず、イテレータ ラップはランダムアクセスです。これは、センチネルを減らすことができないためです。範囲のイテレータは、センチネルと同じくらい強力であることができますが、これは非常に弱いものです.

だから何?

そのため、C スタイルの文字列に対して STL アルゴリズムを効率的に使用することはできません。大したことですよね?実際、そうです。つまり、ほぼすべて 一般的な文字列アルゴリズムは、C スタイルの文字列では使用できません。 Boost.String_algo のすべてのジューシーな文字列アルゴリズムを見てください。ドキュメントは、サポートする文字列型について次のように述べています:

Boost.String_algo の C スタイルの文字列は好きではありません。ところで、std::regex_search を呼び出すとどうなると思いますか? Cスタイルの文字列で?最初に strlen を呼び出します !したがって、文字列の長さがメガバイトで、一致が最前部にある場合でも、最初に 全体 をトラバースする必要があります 端がどこにあるかがわかるように、ひもで結びます。これはまったく無意味です。

「とにかく、C スタイルの文字列を使用するべきではありません」とあなたは言います。しかし、問題は C スタイルの文字列よりも大きくなります。 すべて 区切られた範囲にはこの問題があります。標準ライブラリだけでも istream_iterator あります 、 istreambuf_iteratorregex_iterator 、および regex_token_iterator 、それらにはすべてダミーの歩哨があり、上に示したように靴べらが埋め込まれています。きっと他の人も思いつくでしょう。

ディートマー・キュールは、別の興味深い事例について私に警告してくれました。一般的なアルゴリズムを呼び出したいと思ったのに、ある条件下で早期にループから抜け出したくてできなかったことがありますか?その述語と終了反復子を使用して、区切られた範囲を構築できると想像してください。これで、その範囲をアルゴリズムに渡すことができ、述語が真になるか、シーケンスの最後に到達したときに停止します。出来上がり!標準アルゴリズムがさらに便利になりました。しかし、このイテレータ型は他のものと同じように押し込める必要があり、センチネルをデクリメントできないため、フォワード イテレータ以上を必要とするアルゴリズムを呼び出すことはできません。

結論、とりあえず…

私のポイントは何ですか?私の要点は次のとおりです。私たちがよく知っていて、抽象化コストが低くなるように設計されたイテレータのペアの範囲抽象化には、区切られた範囲では避けられない実際の抽象化コストがあります。また、区切られた範囲がそうでない場合よりも弱い概念をモデル化することを強制し、その実装を扱いにくくします。解決策は何ですか?私はします 具体的な提案がありますが、まだそこにはありません。まず、無限の範囲について話したいと思います。次に、区切られた、無限の、ペアの反復子の範囲がすべて、より大きな範囲の概念にどのように組み込まれるかを見ていきます。次回もどうぞ…

謝辞

範囲のアイデアを策定し、この記事をレビューするのを手伝ってくれた、Dietmar Kuehl と Andrew Sutton に感謝します。

x
x