9

value_type がコンテナーに直接格納されていない適合コンテナーを作成することは不可能であるという結論に多かれ少なかれ到達しました。値の型が部分的に計算されているか、不連続な部分から組み立てられているコンテナがあればいいのにと思うことがよくあるので、これは残念だと思います（以下の例ですが、質問には直接関係ありません）。プロキシ オブジェクトを使用するイテレータの書き方は知っていますが、かなり面倒です。しかし、私は今、C++ 標準にそのような野獣のための余地があるかどうか疑問に思っています。ここにはおそらく言い回しが多すぎます。tl;dr バージョンは単純です: §24.2.5 のパラグラフ 1 と 6 は実際には何を意味するのでしょうか? また、明白な意味に違反すると、標準アルゴリズムがどの程度破られるのでしょうか? 別の言い方をすれば、プロキシ イテレータを許可するように解釈するにはどうすればよいでしょうか。

Pete Becker が指摘するように、標準ライブラリ コンテナーに設定された要件にコンテナーが準拠することを強制するものは実際には何もありません。しかし、コンテナを多くの標準アルゴリズムで使用するためには、少なくとも a の適合するイテレータを持たなければならないか、それforward_iterator_tagについて嘘をついても、特定のアルゴリズムがそのイテレータに課す運用上の (正式ではないにしても) 要件を満たすことができる必要があります。 .

これが私の推論です：

表 96 (§ 23.2.1)、コンテナー要件には、以下が含まれます。

Expression     Return type         Assertion/note
------------   -------------       ---------------------
X::iterator    iterator type       any iterator category
               whose value         that meets the
               type is T           forward iterator
                                   requirements.
                                   Convertible to
                                   const_iterator.

 a.begin()     iterator;
               const_iterator for
               constant a.

さて、フォワードイテレータ：

§ 24.2.5、パラ。1:

クラスまたはポインター型Xは、次の場合に前方反復子の要件を満たします。

—X可変イテレータの場合reference、 への参照Tです。ifXは const イテレータでreference、への参照ですconst T

*a直接返す必要がないのは事実ですreference(ここaで は type ですX)。要件は次のとおりです。

from Table 107 (入力イテレータ)が参照解除可能である*a場合、「T に変換可能」でなければなりませんa。

表 106 から (イテレータ)*rは型を持たなければならずreference、ここでrは型でX&あり、参照解除可能です。

ただし、表 106 では、 が を++r返すことも指定されているX&ため、 である*++r必要がありますreference。また、(表 107 に従って) である*a++必要がありますがreference、(表 109)a[n]は「参照に変換可能」である必要があるだけです。*awhere ais of typeXと*rwhere ris of typeがどのように異なるかはわかりませんX&が、微妙な点が欠けている可能性があります。

ここには多少の余裕があるかもしれませんが、それほど多くはありません。ある時点で、T実際にコンテナーに がない場合は、それへの参照を提供できるように を作成する準備をする必要があります。

しかしキッカーは

§ 24.2.5、パラ。6 (aとbは type の値X):aとbが両方とも逆参照可能である場合、 とが同じオブジェクトにバインドされているa == b場合に限ります。*a*b

の正式な定義は見つかりませんbound toが、アドレス指定できないオブジェクトのイテレータを作成するための通常の戦略は、プロキシ オブジェクトを作成することであり、通常はイテレータ自体の内部に格納されるようです。この場合、たとえそれらが論理的に同じ位置を示していたとしても、2 つの異なる反復子オブジェクト間で成功する等価比較を禁止する以外の方法で 24.2.5/6 を解釈するには、「バインド先」が何を意味するのかについて非常に寛大な理解が必要です。コンテナで。

一方、知っておくべきディートマー・キュールは、この質問への回答で次のように述べています。

C++ 2011 では要件が緩和され、イテレータは必ずしも左辺値を生成する必要はありません

では、イテレータはプロキシを返すことができますか? 可能であれば、そのようなプロキシの性質は何ですか? そのようなイテレータが非準拠であるという私の推論はどこで失敗しますか?

約束どおり、有効な value_types がコンテナーに連続して格納されないいくつかのコンテナー:

1) キーと値の型を 2 つの個別のベクトルに効率的に格納できるコンパクトな連想コンテナー。(キーをベクトルに保持すると、割り当てのオーバーヘッドを削減するだけでなく、キャッシュの使いやすさも向上します。)

2)vector<T>として偽装し、map<integer_type, T>他の型との相互運用性を簡素化するmap<X, T>。

tuple3) いくつかの他のコンテナーを圧縮することによって形成される論理コンテナーであり、圧縮されたコンテナーの値の型への参照である論理 value_type を生成します。(一部のアプリケーションでは、圧縮されたコンテナーの 1 つ以上が、他の値の関数として、またはシーケンス番号として完全に計算される場合があります。)

4) 一部の値のみを持つ集約タイプのコンテナーのビュー。(おそらく、基になるコンテナーとビューの両方がタプルであり、ビューのタプルの型リストは、基になるコンテナーの型の、おそらく異なる順序のサブセットです)。

他の人がこのリストに簡単に追加できると確信しています。これらは、私が過去数か月の間に何らかの方法でハッキングしたものにすぎません。

4

2 に答える 2

2

「適合コンテナ」について考えて自分を制限しないでください。標準には、コンテナを持つことに依存するものは何もありません。コンテナーの要件は、標準で定義されているコンテナーの要件を簡単に説明する方法と考えてください。これ以上何もない。コンテナーが生成する反復子が有効である限り、対応するすべてのアルゴリズムに問題がなく、おそらく自分で作成したアルゴリズムにも問題はありません。

于 2012-12-13T23:59:40.437 に答える
2

最適なモデルはstd::vector< bool >. 可能な限り準拠に近づいていますが、イテレータはプロキシを生成します。

標準では、それstd::vector<bool>::referenceがクラスであることも指定されています。しかし、コンテナー要件の表では、X::reference「T の左辺値」を生成することが指定されています。したがって、厳密には非準拠です。

しかし、反復子は にバインドされていませんT。イテレータvalue_typeは である必要がTあり、入力イテレータの要件を参照して、 にreference変換する必要がありますvalue_type。

Pete Becker が言及しているように、要件の表はかなり大まかなブランケットであり、個々のアルゴリズムが必要なものを指定します。reference本当に参照である必要があるアルゴリズムだけが壊れます。これは、明らかなことを述べているだけです。

于 2012-12-17T06:10:15.117 に答える