迭代器概念(Iterator Concepts)

一個迭代器是一個指向一個向量或一個矩陣的受限制的(restricted)類似於指向的對象。

索引雙向迭代器(Indexed Bidirectional Iterator)

說明

一個索引雙向迭代器是一個容器的迭代器,可以解引用(dereferenced),遞增(incremented),遞減(decremented)並攜帶索引信息。

優化(Refinement of)

賦值,相等比較,缺省構造。

相關類型(Associated types)

值類型(Value type) 解引用一個索引雙向迭代器(Indexed Bidirectional Iterator)所獲取的值類型。
容器類型(Container type) 索引雙向迭代器(Indexed Bidirectional Iterator)所指向的容器的類型。

記法(Notation)

I 索引雙向迭代器(Indexed Bidirectional Iterator)模型的類型。
T I的值類型。
C I的容器類型。
it, itt, it1, it2 I類型的對象。
t T類型的對象。
c C類型的對象。

定義

一個索引雙向迭代器(Indexed Bidirectional Iterator) 可能是可變的(mutable),意味著被這種迭代器類型所指向的對象的值是可以修改的; 或者是常量(constant) , 意味著它們不可以被修改。如果一個迭代器類型是可變的(mutable),這暗含著它的值類型是可賦值模型( model of Assignable); 反之,就不一定必然是真的。

一個索引雙向迭代器(Indexed Bidirectional Iterator) 可以有一個單一(singular) 值,意味著大多數運算的結果,包括相等比較,是未定義的(undefined)。所保證的唯一的操作是將一個非單一(nonsingular)賦值給一個單一迭代器(singular)。

一個索引雙向迭代器(Indexed Bidirectional Iterator)可能有可解用的(dereferenceable) 值,意味差解引用這種迭代器可以產生一個定義良好的(well-defined)值。可解引用的迭代器永遠都是非單一的(nonsingular),但是反之(非可解引用的迭代器)就不是真的

如果一個索引雙向迭代器(Indexed Bidirectional Iterator)指向超出容器最後一個元素的位置,那麼 個迭代器是past-the-end 。 Past-the-end 值是非單一的(nonsingular)和非可解引用的(nondereferenceable)。

合法表達式(Valid expressions)

除了為賦值,相等比較和缺省構造所定義的表達式之外,下面的表達式也應當是合法的。

名稱 表達式 類型要求(Type requirements) 返回值類型(Return type)
缺省構造函數 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
索引(Index) it.index ()   C::size_type

表達式語義(Expression Semantics)

僅當一個表達式的語義不同於或沒有定義在賦值,相等比較和缺省構造之中時才得以定義。

名稱 表達式 先決條件(Precondition) 語義(Semantics) 後置條件(Postcondition)
缺省構造函數 I it     it是單一的(singular)。
解引用(Dereference) *it it是可解引用的(dereferenceable)。    
解引用賦值(Dereference assignment) *it = t Same as for *it.   *it是t的拷貝。
成員訪問(Member access) it->m it是可解引用的(dereferenceable)。 等價於(*it).m  
前遞增(Preincrement) ++ it it是可解引用的(dereferenceable)。 it被修改為指向下一個元素。 it是可解引用的(dereferenceable)或past-the-end。
&it == &++ it
.
If it1 == it2,
then ++ it1 == ++ it2.
後遞增(Postincrement) it ++ 類似於++ it 等價於
{
 I itt = it;
 ++ it;
 返回 itt;
}
it是可解引用的(dereferenceable)或past-the-end。
前遞減(Predecrement) -- it it是可解引用的(dereferenceable)或past-the-end。
存在一個可解引用的(dereferenceable)的迭代器itt使得 it == ++ itt
it 被修改為指向前一個元素。 it 是可解引用的。
&it = &-- it
如果 it1 == it2,
那麼 -- it1 == -- it2
如果 it2 是可解引用的(dereferenceable)且 it1 == ++it2,
那麼 --it1 == it2
後遞減(Postdecrement) it -- 類似於 -- it 等價於
{
 I itt = it;
 -- it;
 返回 itt;
}
it 是可解引用的(dereferenceable)。 
索引(Index) it.index () it 是可解引用的(dereferenceable)。 it.index () >= 0

it.index () < it ().size ()
如果 it1 == it2,
那麼 it1.index () == it2.index ()
如果 it1 == it2,
那麼 it1.index () < (++ it2).index ().
如果 it1 == it2,
那麼 it1.index () > (-- it2).index ()

複雜度保證(Complexity guarantees)

索引雙向迭代器操作的複雜度保證是攤還常量時間(amortized constant time)。

不變量(Invariants)

相等(Identity) it1 == it2當且僅當 &*it1 == &*it2
遞增遞減對稱(Symmetry of increment and decrement) 如果 it 是可解引用的(dereferenceable), 那麼 ++ it; --it; 是一個空操作(null operation)。類似地,-- it; ++ it;是一個空操作(null operation)。
迭代器索引和容器元素運算符之間的關係(Relation between iterator index and container element operator) 如果 it 是可解引用的(dereferenceable), 那麼*it == it () (it.index ())

模型(Models)

索引隨機訪問迭代器(Indexed Random Access Iterator)

說明

索引隨機訪問迭代器(Indexed Random Access Iterator)是一個容器的迭代器,它可以解引用(dereferenced),向前移動,向後移動並攜帶索引信息。

優化(Refinement of)

小於比較(LessThanComparable),隨機雙向迭代器(Indexed Bidirectional Iterator)

相關類型(Associated types)

Value type 解引用一個索引隨機訪問迭代器(Indexed Random Access Iterator)所獲取的值的類型。
Container type 索引隨機訪問迭代器(Indexed Random Access Iterator)所指向的指向的容器的類型。

記法(Notation)

I 索引隨機訪問迭代器(Indexed Random Access Iterator)類型的對象
T I類型值
C I類型容器
it, itt, it1, it2 I類型對像
t T類型對像
n C::difference_type類型對像

定義

如果將遞增運算符++ 應用於迭代器it2有限次之後,it1 == it2,那麼一個索引隨機訪問迭代器(Indexed Random Access Iterator) it1 是從一個索引隨機訪問迭代器it2可達的(reachable)

合法表達式(Valid expressions)

除了為索引雙向迭代器(Indexed Bidirectional Iterator)所定義的表達式是合法的之外,下面的表達式也應當是合法的。

名稱(Name) 表達式(Expression) 類型要求(Type requirements) 返回 類型(Return type)
向前移動(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 is mutable 可以轉化為T類型。

表達式語義(Expression Semantics)

僅當一個表達式不同於或沒有定義在索引雙向迭代器(Indexed Bidirectional Iterator)中之時,這個表達式的語義才得以定義。

名稱(Name) 表達式(Expression) 先決條件(Precondition) 語義(Semantics) 後置條件(Postcondition)
向前移動(Forward motion) it += n 包括 it 本身,依賴於n是下數或是負數,在it之後或之前必須有n個可解引用的 (dereferenceable)或past-the-end 迭代器。 如果 n > 0, 等價於執行++ it n 次。如果n < 0, 等價於執行 -- it n 次。如果 n == 0, 那麼這就是一個空操作(null operation)。 it是可解引用的(dereferenceable)或past-the-end。
迭代器加法(Iterator addition) it + n 類似於i += n 等價於
{
 I itt = it;
 return itt += n;
}
結果是可解引用的(dereferenceable)或past-the-end。
向後移動(Backward motion) it -= n 包括it本身, 依賴於 n是正數或是負數,在it 之前或之後必須有n個可解引用的(dereferenceable) 或 past-the-end 迭代器。 等價於 it += (-n) it 是可解引用的(dereferenceable)或 past-the-end。
迭代器減法(Iterator subtraction) it - n 類似於 i -= n 等價於
{
 I itt = it;
 return itt -= n;
}
結果是可解引用的(dereferenceable)或 past-the-end。
差值(Difference) it1 - it2 it1it2是可達的(reachable)或 it2it1是可達的(reachable),或者兩者都是彼此可達的(reachable)。 返回數字n使得it1 == it2 + n  
元素操作符(Element operator) it [n] it + n 存在且是可解引用的(dereferenceable)。 等價於 *(it + n)  
元素賦值(Element assignment) i[n] = t 類似於 it [n] 等價於*(it + n) = t  

複雜度保證(Complexity guarantees)

索引隨機訪問迭代器的操作的複雜度保證為攤還常量時間(amortized constant time)。

不變量(Invariants)

加法和減法的對稱(Symmetry of addition and subtraction) 如果 it + n是定義良好的(well-defined), 那麼 it += n; it -= n;(it + n) - n 是空操作(null operations)。 類似地, 如果 it - n 是良定義的(well-defined), 那麼it -= n; it += n;(it - n) + n是空操作(null operations)。
距離和加法之間的關係 如果 it1 - it2 是定義良好的(well-defined), 那麼 it1 == it2 + (it1 - it2)
可達性和距離(Reachability and distance) 如果 it1 是從it2可達的(reachable),那麼 it1 - it2 >= 0

模型(Models)

索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator)

說明

一個容器的索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator)是可解引用的(dereferneced),遞增(incremented),遞減(decremented)並攜帶索引信息。

優化(Refinement of)

賦值,相等比較,缺省構造。

相關類型(Associated types)

值類型(Value type) 解引用一個索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator)所獲取的值的類型。
容器類型(Container type) 一個索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator)所指向的容器的類型。

記法(Notation)

I1 一個索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator) 模型的類型。
I2 一個索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator) 模型的類型。
T I1I2的值類型。
C I1I2的容器類型。
it1, it1t, it11, it12 I1類型的對象。
it2, it2t I2類型的對象。
t T類型的對象
c C類型的對象。

定義

合法表達式(Valid expressions)

除了為賦值,相等比較和缺省構造所定義的表達式之外,下面的表達式也應當是合法的。

名稱(Name) 表達式(Expression) 類型要求(Type requirements) 返回類型(Return type)
缺省構造函數 I1 it    
解引用(Dereference) *it   可以轉化為T類型。
解引用賦值(Dereference assignment) *it = t I1 是可變的(mutable)。  
成員訪問 it->m T是定義t.m的類型。  
前遞增(Preincrement) ++ it   I1 &
後遞增(Postincrement) it ++   I1
前遞減(Predecrement) -- it   I1 &
後遞減(Postdecrement) it --   I1
行索引(Row Index) it.index1 ()   C::size_type
列索引(Column Index) it.index2 ()   C::size_type
行/列開始位置(Row/Column Begin) it.begin ()   I2
行/列結束位置(Row/Column End) it.end ()   I2
反向行/列開始位置(Reverse Row/Column Begin) it.rbegin ()   reverse_iterator<I2>
反向行/列終止位置(Reverse Row/Column End) it.rend ()   reverse_iterator<I2>

表達式語義(Expression Semantics)

僅當一個表達式的語義不同於或沒有定義在賦值,相等比較和缺省構造之中時才得以定義。

名稱(Name) 表達式(Expression) 先決條件(Precondition) 語義(Semantics) 後置條件(Postcondition)
缺省構造函數 I1 it     it是單一的(singular)。
解引用(Dereference) *it it是可解引用的(dereferenceable)。    
解引用賦值(Dereference assignment) *it = t 類似於*it   *it是t的拷貝。
成員訪問(Member Access) it->m it是可解引用的(dereferenceable)。 等價於(*it).m  
前遞增(Preincrement) ++ it it是可解引用的(dereferenceable)。 it被修改為指向下一列/行。 例如,對於列迭代器滿足
it.index1 () < (++ it).index1 ()
it.index2 () == (++ it).index2 (),
對於行迭代器滿足
it.index1 () == (++ it).index1 ()
it.index2 () < (++ it).index2 ()
it 是可解引用的(dereferenceable)或past-the-end。
&it == &++ it
.
如果 it1 == it2,
那麼 ++ it1 == ++ it2
後遞增(Postincrement) it ++ 類似於++ it 等價於
{
 I1 itt = it;
 ++ it;
 return itt;
}
it 是可解引用的(dereferenceable)或 past-the-end。
前遞減(Predecrement) -- it it 是可解引用的(dereferenceable)或past-the-end。
存在一個解引用(dereferenceable)迭代器itt滿足 it == ++ itt
it 修改為指向前行或列的前一個元素, 例如,對於列迭代器滿足
it.index1 () > (-- it).index1 ()
it.index2 () == (-- it).index2 (),
對於行迭代器滿足
it.index1 () == (-- it).index1 ()
it.index2 () > (-- it).index2 ()
it是可解引用的(dereferenceable)。
&it = &-- it
如果 it1 == it2,
那麼 -- it1 == -- it2
後遞減(Postdecrement) it -- 類似於 -- it 等價於
{
 I1 itt = it;
 -- it;
 return itt;
}
it是可解引用的(dereferenceable)。 
行索引(Row Index) it.index1 () 如果 it 是一個行迭代器,那麼it必須是可解引用的(dereferenceable)。 it.index1 () >= 0
it.index1 () < it () .size1 ()
如果 it1 == it2,
那麼 it1.index1 () == 12.index1 ()
如果 it1, it2 行迭代器且it1 == it2,
那麼 it1.index1 () < (++ it2).index1 ()
it1.index1 () > (-- it2)index1 ()
列迭代器(Column Index) it.index2 () 如果it是一個列迭代器,那麼it必須是可解引用的(dereferenceable)。 it.index2 () >= 0
it.index2 () < it () .size2 ()
如果 it1 == it2,
那麼 it1.index2 () == it2.index2 ()
如果 it1, it2 是列迭代器且it1 == i12,
那麼 it1.index2 () < (++ it2).index2 ().
it1.index2 () > (-- it2).index2 ()
行/列開始位置(Row/Column Begin) it.begin () it 是可解引用的(dereferenceable)。 如果 it 是一個列迭代器,那麼
it2 = it.begin () 是一個行迭代器
it2.index1 () == it.index1 ()

如果 it 是一個行迭代器,
那麼 it2 = it.begin () 是一個列迭代器
it2.index2 () == it.index2 ()

 
行/列終止位置(Row/Column End) it.end () it 是可解引用的(dereferenceable)。 如果 it是一個列迭代器,
那麼it2 = it.end ()是一個行迭代器
it2.index1 () == it.index1 ()

如果 it 是一個行迭代器,
那麼 it2 = it.end () 是一個列迭代器
it2.index2 () == it.index2 ()

 
反向行/列開始位置(Reverse Row/Column Begin) it.rbegin () it 是可解引用的(dereferenceable)。 等價於 reverse_iterator<I2> (it.end ())  
反向行/列結束位置(Reverse Row/Column End) it.rend () it是可解引用的(dereferenceable)。 等價於 reverse_iterator<I2> (it.begin ())  

複雜度保證(Complexity guarantees)

索引隨機訪問迭代器的操作的複雜度保證為依賴於容器大小的對數時間。一個迭代器的複雜度(依賴於存儲佈局)可以被提升為攤還常量時間(amortized constant time)。分別對於第一行和第一列,另一個迭代器的複雜度(依賴於容器的存儲佈局)可以被提升為攤還常量時間。

不變量(Invariants)

相等(Identity) it1 == it2 當且僅當&*it1 == &*it2
遞增和遞減的對稱性(Symmetry of increment and decrement) 如果it 是可解引用的(dereferenceable), 那麼++ it; --it;是一個空操作(null operation)。類似地-- it; ++ it;是一個空操作(null operation)。
迭代器索引與容器元素操作符之間的關係 如果 it 是可解引用的(dereferenceable), 那麼*it == it () (it.index1 (), it.index2 ())
迭代器行/列開始位置與迭代器索引之間的關係 如果it是一個列迭代器 且 it2 = it.begin (),那麼對於所有的it2tit2t () == it2 () 以及 it2t ().index1 () == it2 ().index1 ()it2.index2 () < it2t.index2 ()

如果 it 是一個行迭代器且 it2 = it.end () ,那麼對於所有的it2tit2t () == it2 () 以及 it2t ().index2 () == it2 ().index2 ()it2.index1 () > it2t.index1 ()

迭代器行/列終止位置與迭代器索引之間的關係 如果 it 是一個列迭代器 且 it2 = it.end () ,那麼對於所有的it2tit2t () == it2 () 以及 it2t ().index1 () == it2 ().index1 ()it2.index2 () > it2t.index2 ()

如果 it 是一個和列迭代器且 it2 = it.end () ,那麼對於所有的it2tit2t () == it2 () 以及 it2t ().index2 () == it2 ().index2 ()it2.index1 () > it2t.index1 ()

模型(Models)

索引隨機訪問列/行迭代器(Indexed Random Access Column/Row Iterator)

說明

一個容器的索引隨機列/行迭代器(Indexed Random Column/Row Iterator)是可解引用的(dereferneced),遞增(incremented),遞減(decremented)並攜帶索引信息。

優化(Refinement of)

索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator)

相關類型(Associated types)

值類型(Value type) 解引用(dereference)索引隨機訪問列/行迭代器所獲取的值的類型
容器類型(Container type) 一個索引隨機列/行迭代器(Indexed Random Column/Row Iterator)所指向的容器的類型。

記法(Notation)

I 一個索引隨機列/行迭代器(Indexed Random Column/Row Iterator)模型的類型。
T I的值類型。
C I的容器在類型。
it, itt, it1, it2 I類型的對象。
t T類型的對象。
c C類型的對象。

定義

合法表達式(Valid expressions)

除了為索引雙向列/行迭代器(Indexed Bidirectional Column/Row Iterator) 所定義的表達式之外,下面的表達式也應當是合法的。

名稱(Name) 表達式(Expression) 類型要求(Type requirements) 返回類型(Return type)
向前移動(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) 器中之時才得到定義。

名稱(Name) 表達式(Expression) 先決條件(Precondition) 語義(Semantics) 後置條件(Postcondition)
前向移動(Forward motion) it += n 包括it本身, 在it後面或前面必須有n 個可解引用的(dereferenceable)或past-the-end迭代器 , 依賴於n 是正數或負數。 如果 n > 0, 等價於執行 ++ it n 次。如果 n < 0, 等價於執行 -- it n 次。如果 n == 0, 那麼這是一個空操作(null operation)。 it 是可解引用的(dereferenceable)或past-the-end。
迭代器加法(Iterator addition) it + n 類似於 i += n 等價於
{
 I itt = it;
 return itt += n;
}
結果是可解引用的(dereferenceable)或past-the-end。
向後移動(Backward motion) it -= n 包括 it 本身,在 it本身之前或之後必須有n個 可解引用的(dereferenceable)或past-the-end迭代器, 依賴於 n是正數或是負數 。 等價於it += (-n) it是可解引用的(dereferenceable)或past-the-end。
迭代器減法(Iterator subtraction) it - n 類似於 i -= n 等價於
{
 I itt = it;
 return itt -= n;
}
結果是可解引用的(dereferenceable) 或 past-the-end。
差值(Difference) it1 - it2 it1是從it2可達的(reachable)或 it2 是從it1可達的(reachable), 或者兩者彼此是可達的。 返回一個數值n使得it1 == it2 + n  
元素操作符(Element operator) it [n] it + n 存在且是可解引用的(dereferenceable)。 等價於*(it + n)  
元素賦值(Element assignment) i[n] = t 類似於 it [n] 等價於 *(it + n) = t  

複雜度保證(Complexity guarantees)

索引隨機訪問列/行迭代器操作的複雜度保證為攤還常量時間(amortized constant time)。

不變量(Invariants)

加法和減法的對稱性(Symmetry of addition and subtraction) 如果 it + n 是定義良好的(well-defined), 那麼it += n; it -= n; 以及 (it + n) - n是空操作(null operations)。 類似地,如果 it - n是定義良好的(well-defined), 那麼it -= n; it += n;(it - n) + n是空操作(null operations)。
距離和加法之間的關係(Relation between distance and addition) 如果it1 - it2是定義良好的(well-defined),那麼it1 == it2 + (it1 - it2)
可達性與距離(Reachability and distance) 如果it1是從it2可達的(reachable), 那麼 it1 - it2 >= 0

模型(Models)


Copyright (©) 2000-2002 Joerg Walter, Mathias Koch
Use, modification and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt ).