c++boost.gif Iterator Concepts

イテレータはベクタや行列の中を指し示す制限されたポインタのような(pointer-like)オブジェクトである。

Indexed Bidirectional Iterator

Description

インデックス付き双方向イテレータ(Indexed Biderectional Iteretor)は参照外し、インクリメント、デクリメントすることができ、 インデックスの情報を持つイテレータである。

Refinement of

Assignable, 等値比較可能(Equality Comparable), デフォルトコンストラクト可能(Default Constructible)

Associated types

Value type インデックスつき双方向イテレータを参照外しして得られる値の型
Container type インデックス付き双方向イテレータが指しているコンテナの型

Notation

I インデックス付き双方向イテレータのモデルの型
T Iの値型(value type)
C Iのコンテナ型(container type)
it, itt, it1, it2 I型のオブジェクト
t T型のオブジェクト
c C型のオブジェクト

Definitions

インデックス付き双方向イテレータはmutable（その型のオブジェクトによって参照される値が変更可能であることを意味する）、 またはconstant（変更可能であることを意味しない）のどちらかである。 もし、イテレータ型がmutableであるなら値型がAssignableのモデルであることを暗に示している。しかし、もしconstantならそうである必要はない。

インデックス付き双方向イテレータは単一の(singular)値を持つ。つまり、ほとんどの演算（等値比較を含む）は定義されない。 サポートが保証されるのはひとつだけでない(nonsingular)イテレータを単一のイテレータに割り当てることだけである。

インデックス付き双方向イテレータは参照外し可能な(dereferenceable)値を持つ。つまりその値を参照外しすることで明確に定義された(well-defined)値を 得ることができる。参照外し可能なイテレータは常に単一でない(nonsigular)。しかし逆は必ずしも真ではない。

インデックス付き双方向イテレータは、もしコンテナの最後の要素より向こうを指しているときはpast-the-endである。 Past-the-endな値は単一でなく(nonsingular)参照外し不可である。

Valid expressions

Assignable、等値比較可能(Equality Comparable)、デフォルトコンストラクト可能(Default Constructible)に加えて、以下が正当である必要がある。

名前 式 型に関する要求 戻り値
Default constructor I it    
Dereference *it   Tに変換可能
Dereference assignment *it = t Iがmutableであること  
Member access it->m Tはt.mについて定義されている型  
Preincrement ++ it   I &
Postincrement it ++   I
Predecrement -- it   I &
Postdecrement it --   I
Function call it ()   C &に変換可能
Index it.index ()   C::size_type

Expression Semantics

式のセマンティクスはAssignable、等値比較可能な(Equality Comparable)、デフォルトコンストラクト可能な(Default Constructable)で定義されるものと 異なっていたり、もしくは定義されていない時だけ定義される。

名前 式 事前条件 セマンティクス 事後条件
Default constructor I it     itがsingularであること
Dereference *it itが参照外し可能であること    
Dereference assignment *it = t *itと同じ   *itはtのコピー
Member access it->m itが参照外し可能であること (*it).mと同じ  
Preincrement ++ it itが参照外し可能であること it は次の要素を指すように変更される itは参照外し可能であるか、もしくはpast-the-endである
&it == &++ it.
If it1 == it2,
then ++ it1 == ++ it2.
Postincrement it ++ Same as for ++ it. {
 I itt = it;
 ++ it;
 return itt;
} と同じ		 it は参照外し可能、もしくは、past-the-endである
Predecrement -- it it が参照外し可能であるか、もしくは、past-the-endであること
参照外し可能なイテレータittが存在する。たとえばit == ++ itt. 		it は前の要素を指すように変更される it が参照外し可能であること
&it = &-- it.
If it1 == it2,
then -- it1 == -- it2.
Postdecrement it -- -- itと同じ {
 I itt = it;
 -- it;
 return itt;
}と同じ		 itが参照外し可能であること. 
Function call it () itが参照外し可能、もしくはpast-the-endであること もし it がコンテナc内を指しているなら it () = c.  
Index it.index () it が参照外し可能、もしくはpast-the-endであること it.index () >= 0
and
it.index () <= it ().size ()		 もしit1 == it2ならば
it1.index () == it2.index ().
もしit1 == it2ならば
it1.index () < (++ it2).index().
もしit1 == it2ならば
it1.index () > (-- it2).index ().

Complexity guarantees

インデックス付き双方向イテレータの演算に関する計算量は、償却定数時間であると保証されている。

Invariants

同一性(Identity) it1 == it2if and only if &*it1 == &*it2.
インクリメントとデクリメントの対称性 もしitが参照外し可能であるなら、++it; --it;は何もしない演算である。 同じように--it; ++it;も何もしない演算である。
イテレータのインデックスとコンテナ要素の関係 もしitが参照外し可能なら*it ==it() (it.index ()).

Models

Indexed Random Access Iterator

Description

インデックス付きランダムアクセスイテレータ(Indexed Random Access Iterator)は, 参照外し、前進、後退が可能で、インデックス情報を持っている、コンテナのイテレータである。

Refinement of

小なり比較可能な(LessThanComparable), インデックス付き双方向イテレータ(Indexed Bidirectional Iterator)

Associated types

Value type インデックス付きランダムアクセスイテレータを参照外しして得られる値の型
Container type インデックス付きランダムアクセスイテレータが指すコンテナの型

Notation

I インデックス付きランダムアクセスイテレータのモデルの型
T Iの値型(value type)
C Iのコンテナ型(container type)
it, itt, it1, it2 I型のオブジェクト
t T型のオブジェクト
n C::difference_type型のオブジェクト

Definitions

インデックス付きランダムアクセスイテレータ it1 は、以下の条件が成り立つとき インデックス付きランダムアクセスイテレータ it2 から到達可能reachableである。
もし operator++ を it2 に有限回適用したあとで it1 == it2 が成り立つなら。

Valid expressions

Indexed Bidirectional Iteratorでの定義に加えて、以下の式が正当である必要がある。

名前 式 型に関する要求事項 戻り値
Forward motion it += n   I &
Iterator addition it + n   I
Backward motion i -= n   I &
Iterator subtraction it - n   I 
Difference it1 - it2   C::difference_type
Element operator it [n]   Tに変換可能
Element assignment it [n] = t Iがmutableであること Tに変換可能

Expression Semantics

式のセマンティクスはIndexed BidirectionalIteratorと異なっていたり、もしくは 定義されていない場合にのみ定義される。

名前 式 事前条件 セマンティクス 事後条件
Forward motion it += n it自身を含みitの前または後のイテレータは、n個の参照外しまたは
past-the-end可能なイテレータが存在する必要がある。前か後かは
nの値の正負に依存する。		 もし、n > 0なら、++itを n回実行するのと同じ。
もし、n < 0なら、-- itを n回実行するのと同じ。
もし、n == 0ならこれは何もしない演算。		 itが参照外し可能、または
past-the-endであること
Iterator addition it + n i += nと同じ {
 I itt = it;
 return itt += n;
}と同じ		 結果が参照外し可能、または
past-the-endであること
Backward motion it -= n it自身を含みitの前または後のイテレータは、n個の参照外しまたは
past-the-end可能なイテレータが存在する必要がある。前か後かは
nの値の正負に依存する。		 it += (-n)と同じ itが参照外し可能、または
past-the-endであること
Iterator subtraction it - n i -= nと同じ {
 I itt = it;
 return itt -= n;
}と同じ		 結果が参照外し可能、または
past-the-endであること
Difference it1 - it2 it1がit2から到達可能(reachable)であるか、または
it2がit1から到達可能であるか、または
その両方が成立すること		 it1 == it2 + nを満たすようなnを返す  
Element operator it [n] it + nが存在し、且つ参照外し可能であること *(it + n)と同じ  
Element assignment i[n] = t it [n]と同じ *(it + n) = tと同じ  

Complexity guarantees

インデックス付きランダムアクセスイテレータの演算の計算量は償却定数時間であると保証される。

Invariants

加算減算の対称性 もし it + n が明確に定義される(well-defined)なら it+= n; it -= n;と (it + n) - n は何もしない演算である。
同様に もしit - nが明確に定義されるなら it -=n; it += n; and (it - n) + n は何もしない演算である。
距離と加算の関係 もし it1 - it2 が明確に定義される(well-defined)なら it1 == it2 + (it1 - it2).
到達可能性(Reachability)と距離 もし it1 が it2 へ到達可能(reachable)なら, it1 - it2 >= 0 .

Models

Indexed Bidirectional Column/Row Iterator

Description

インデックス付き双方向の列/行イテレータは参照外し、インクリメント、デクリメントが可能で、インデックス情報を持つ、コンテナのイテレータである。

Refinement of

Assignable, 等値比較可能(Equality Comparable), デフォルトコンストラクト可能(Default Constructible)

Associated types

Value type インデックスつき双方向の列/行イテレータを参照外しして得られる値の型
Container type インデックス付き双方向の列/行イテレータが指しているコンテナの型。

Notation

I1 インデックス付き双方向の列/行イテレータのモデルの型
I2 インデックス付き双方向の列/行イテレータのモデルの型
T I1 とI2 の値型(value type)
C I1 とI2 のコンテナ型(container type)
it1, it1t, it11, it12 I1型のオブジェクト
it2, it2t I2型のオブジェクト
t T型のオブジェクト
c C型のオブジェクト

Definitions

Valid expressions

Assignable, 等値比較可能(Equality Comparable)、デフォルトコンストラクト可能(Default Constructible)、での定義に加えて、 以下の式が政党である必要がある。

名前 式 型に関する要求 戻り値
Default constructor I1 it1    
Dereference *it1   Tに変換可能
Dereference assignment *it1 = t I1がmutableであること  
Member access it1->m Tがt.mについて定義されている型  
Preincrement ++ it1   I1 &
Postincrement it1 ++   I1
Predecrement -- it1   I1 &
Postdecrement it1 --   I1
Function call it1 ()   C &へ変換可能であること
Row Index it1.index1 ()   C::size_type
Column Index it1.index2 ()   C::size_type
Row/Column Begin it1.begin ()   I2
Row/Column End it1.end ()   I2
Reverse Row/Column Begin it1.rbegin ()   reverse_iterator<I2>
Reverse Row/Column End it1.rend ()   reverse_iterator<I2>

Expression Semantics

式のセマンティクスはAssignable, 等値比較可能(Equality Comparable)、デフォルトコンストラクト可能(Default Constructible)での定義と異なったり もしくは、定義されていない時にのみ定義される。

名前 式 事前条件 セマンティクス 事後条件
Default constructor I1 it1     it1がsingularであること
Dereference *it1 it1が参照外し可能であること    
Dereference assignment *it1 = t *it1と同じ   *it1は istのコピー
Member access it1->m it1が参照外し可能であること (*it1).mと同じ  
Preincrement ++ it1 it1が参照外し可能であること it1が次の列/行の要素を指すように変更される。
i.e.列iteratorsについては、
it1.index1 () < (++ it1).index1 () and
it1.index2 () == (++ it1).index2 (),
行 iterators holdsについては
it1.index1 () == (++ it1).index1 () and
it1.index2 () < (++ it1).index2 ().
 it1が参照外し可能
または past-the-endであること
&it1 == &++ it1.
もし it11 == it12,
ならば ++ it11 == ++ it12.
Postincrement it1 ++ ++ it1と同じ {
 I1 it1t = it1;
 ++ it1;
 return it1t;
} と同じ		 it1が参照外し可能
またはpast-the-endであること
Predecrement -- it1 it1が参照外し可能、またはpast-the-endであること
参照外しイテレータit1tが存在する。たとえば、it1 == ++ it1t. 		it1 は列/行前の要素を指すように変更する。
i.e. column iterators holdsについては
it1.index1 () > (-- it1).index1 () and
it1.index2 () == (-- it1).index2 (),
row iterators holdsについては
it1.index1 () == (-- it1).index1 () and
it1.index2 () > (-- it1).index2 (). 		it1が参照外し可能であること
&it1 = &-- it1.
もしit11 == it12,
ならば-- it11 == -- it12.
Postdecrement it1 -- -- it1と同じ {
 I1 it1t = it1;
 -- it1;
 return it1t;
}と同じ		 it1が参照外し可能であること
Function call it1 () it1が参照外し可能、past-the-endであること もし it1 がコンテナc内を指すなら it1 () = c.  
Row Index it1.index1 () it1が参照外し可能、またはpast-the-endであること it1.index1 () >= 0 and
it1.index1 () <= it () .size1 ()		 もしit11 == it12ならば
it11.index1 () == it12.index1 ()
もしit11,it12がインデックスつき双方向の行イテレータで it11 == it12ならば
it11.index1 () < (++ it12).index1().
もしit11,it12がインデックス付き双方向の行イテレータで it11 == it12ならば
it11.index1 () > (-- it12).index1().
Column Index it1.index2 () it1が参照外し可能、またはpast-the-endであること it1.index2 () >= 0 and
it1.index2 () <= it () .size2 ()		 もしit11 == it12ならば
it11.index2 () == it12.index2 ()
もしit11,it12がインデックス付き双方向の列イテレータで it11 == it12ならば
it11.index2 () < (++ it12).index2()
もしit11,it12がインデックス付き双方向の列イテレータで it11 == it12ならば
it11.index2 () > (-- it12).index2().
Row/Column Begin it1.begin () it1 is dereferenceable. もしit1がインデックス付き双方向の列イテレータならば
it2 = it1.begin () はインデックス付き双方向の行イテレータであり it2.index1 () == it1.index1 ()

もしit1がインデックス付き双方向の行イテレータならば
it2 = it1.begin () はインデックス付き双方向の列イテレータであり it2.index2 () == it1.index2 ()

  
Row/Column End it1.end () it1が参照外し可能であること If it1がインデックス付き双方向の列イテレータならば
then it2 = it1.end ()はインデックス付き双方向の行イテレータであり it2.index1 () == it1.index1 ()

If it1がインデックス付き双方向の行イテレータならば
then it2 = it1.end ()はインデックス付き双方向の列イテレータであり it2.index2 () == it1.index2 ()

  
Reverse Row/Column Begin it1.rbegin () it1が参照外し可能であること reverse_iterator<I2>(it1.end ())と同じ  
Reverse Row/Column End it1.rend () it1が参照外し可能であること reverse_iterator<I2>(it1.begin ())と同じ  

Complexity guarantees

インデックス付き双方向の列/行イテレータの演算の計算量はコンテナのサイズにたいして対数オーダーである。
ひとつのイテレータの計算量（記憶域のレイアウトに依存する)は償却定数時間にまで引き上げることができる。
他のイテレータの計算量(記憶域のレイアウトとコンテナに依存する)は、最初の列と最初の行に関しては償却定数時間にまで引き上げることができる。

Invariants

同一性(Identity) it11 == it12 if and only if &*it11 == &*it12
インクリメントとデクリメントの対称性 もしit1が参照外し可能ならば ++it1; --it1; は何もしない演算である。同じように、 --it1; ++ it1; も何もしない演算である。
イテレータインデックスとコンテナ要素演算子の関係 もしit1が参照外し可能ならば *it1 == it1 () (it1.index1 (), it2.index2 ())
列/行の始め(begin)とイテレータのインデックスの関係 もしit1がインデックス付き双方向の列イテレータであり、it2 = it1.begin ()ならば
it2t () == it2 () とit2t().index1 () == it2 ().index1 ()が成立する全てのit2tについて it2.index2 () < it2t.index2 ()

もしit1がインデックス付き双方向の行イテレータであり、it2 = it1.begin ()ならば
it2t() == it2 () and it2t ().index2 () == it2().index2 ()が成立する全てのit2t について it2.index1 () <it2t.index1 ()

列/行イテレータとイテレータのインデックスの関係 もしit1がインデックス付き双方向の列イテレータであり、it2 = it1.end ()ならば
it2t () == it2 () and it2t().index1 () == it2 ().index1 ()が成立する全てのit2tについて it2.index2 () > it2t.index2 ()

もしit1がインデックス付き双方向の行イテレータであり、it2 = it1.end () ならば
it2t () == it2 () and it2t ().index2 () == it2().index2()が成立する全てのit2t について it2.index1 () > it2t.index1 ()

Models

Indexed Random Access Column/Row Iterator

Description

インデックス付きランダムアクセスの列/行イテレータは、参照外し、インクリメント、デクリメント可能で、インデックス情報を持つ、 コンテナのイテレータである。

Refinement of

インデックス付き双方向の列/行イテレータ

Associated types

Value type インデックス付きランダムアクセスの列/行イテレータを参照外しして得られる値の型
Container type インデックス付きのランダムアクセスイテレータが指しているコンテナの型

Notation

I インデックス付きランダムアクセスの列/行イテレータのモデルの型
T Iの値型(value type)
C Iのコンテナ型(container type)
it, itt, it1, it2 I型のオブジェクト
t T型のオブジェクト
c C型のオブジェクト

Definitions

Valid expressions

Indexed Bidirectional Column/Row Iteratorでの定義に加えて 以下の式が正当である必要がある。

名前 式 型に関する要求事項 戻り値
Forward motion it += n   I &
Iterator addition it + n   I
Backward motion i -= n   I &
Iterator subtraction it - n   I 
Difference it1 - it2   C::difference_type
Element operator it [n]   Tへ変換可能であること
Element assignment it [n] = t Iがmutableであること Tに変換可能であること

Expression Semantics

式のセマンティクスはIndexed Bidirectional Column/Row Iterator での定義と異なったり、もしくは定義されていない時にのみ定義される。

名前 式 事前条件 セマンティクス 事後条件
Forward motion it += n it自身を含みitの前または後のイテレータは、n個の参照外しまたは
past-the-end可能なイテレータが存在する必要がある。前か後かは
nの値の正負に依存する。		 もし、n > 0なら、++itを n回実行するのと同じ。
もし、n < 0なら、-- itを n回実行するのと同じ。
もし、n == 0ならこれは何もしない演算。		 itが参照外し可能、または
past-the-endであること
Iterator addition it + n i += nと同じ {
 I itt = it;
 return itt += n;
}と同じ		 結果が参照外し可能、または
past-the-endであること
Backward motion it -= n it自身を含みitの前または後のイテレータは、n個の参照外しまたは
past-the-end可能なイテレータが存在する必要がある。前か後かは
nの値の正負に依存する。		 it += (-n)と同じ itが参照外し可能、または
past-the-endであること
Iterator subtraction it - n i -= nと同じ {
 I itt = it;
 return itt -= n;
}と同じ		 結果が参照外し可能、または
past-the-endであること
Difference it1 - it2 it1がit2から到達可能(reachable)であるか、または
it2がit1から到達可能であるか、または
その両方が成立すること		 it1 == it2 + nを満たすようなnを返す  
Element operator it [n] it + nが存在し、且つ参照外し可能であること *(it + n)と同じ  
Element assignment i[n] = t it [n]と同じ *(it + n) = tと同じ  

Complexity guarantees

インデックス付きランダムアクセスの列/行イテレータの計算量は償却定数時間が保証される。

Invariants

加算、減算の対称性Symmetry of addition and subtraction もし、it + nが明確に定義されている(well-defined)ならば、 it+= n; it -= n; と (it + n) - n は何もしない演算である。同じように、 もし、it - nが明確に定義されている(well-defined)なら it -=n; it += n; と (it - n) + nは何もしない演算である。
距離と加算の関係 もしit1 - it2が明確に定義されている(well-defined)ならば it1 == it2 + (it1 - it2).
到達可能性(Reachability)と距離の関係 もしit1がit2から到達可能(reachable)であるなら、 it1 - it2 >= 0.

Models

Copyright (©) 2000-2002 Joerg Walter, Mathias Koch
Permission to copy, use, modify, sell and distribute this document is granted provided this copyright notice appears in all copies. This document is provided ``as is'' without express or implied warranty, and with no claim as to its suitability for any purpose.

Last revised: 1/15/2003

Japanese Translation Copyright (©) 2003 Satoshi Fujimoto
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。 このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、 その利用が適していることを関知しない。

Japanese Translation Last Revised: 4/9/2003

原文 : Boost 1.30.0 Iterator Concepts