Boost C++ 库

...世界上最受推崇和专业设计的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu, C++ 编码标准

迭代器概念

迭代器是一个受限的、类似指针的对象，指向向量或矩阵容器。

索引双向迭代器

描述

索引双向迭代器是一个容器的迭代器，它可以被解引用、递增、递减，并携带索引信息。

细化自

可赋值, 可等价比较, 默认可构造。

关联类型

值类型 通过解引用索引双向迭代器获得的值的类型
容器类型 索引双向迭代器指向的容器的类型。

符号

I 作为索引双向迭代器模型的类型
T I 的值类型
C I 的容器类型
it, itt, it1, it2 类型为 I 的对象
t 类型为 T 的对象
c 类型为 C 的对象

定义

索引双向迭代器可能是可变的，意味着可以通过该类型的对象修改引用的值，也可能是常量的，意味着它们不能被修改。如果一个迭代器类型是可变的，这意味着它的值类型是可赋值的模型；然而，反之则不一定成立。

索引双向迭代器可能具有奇异值，意味着大多数操作的结果，包括相等性比较，都是未定义的。唯一保证支持的操作是将非奇异迭代器赋值给奇异迭代器。

索引双向迭代器可能具有可解引用值，意味着解引用它会产生一个良好定义的值。可解引用迭代器总是非奇异的，但反之不成立。

如果索引双向迭代器指向容器的最后一个元素之后，则它是过尾的。过尾值是非奇异的且不可解引用的。

有效表达式

除了为可赋值、可等价比较和默认可构造定义的表达式外，以下表达式必须有效。

名称 表达式 类型要求 返回类型
默认构造函数 I it    
解引用 *it   可转换为 T。
解引用赋值 *it = t I 是可变的。  
成员访问 it->m T 是 t.m 被定义的类型。  
前置递增 ++ it   I &
后置递增 it ++   I
前置递减 -- it   I &
后置递减 it --   I
索引 it.index ()   C::size_type

表达式语义

表达式的语义仅在它与可赋值、可等价比较和默认可构造中的定义不同或未定义时才被定义。

名称 表达式 前置条件 语义 后置条件
默认构造函数 I it     it 是奇异的。
解引用 *it it 是可解引用的。    
解引用赋值 *it = t 与 *it 相同。   *it 是 t 的副本。
成员访问 it->m it 是可解引用的。 等价于 (*it).m  
前置递增 ++ it it 是可解引用的。 it 被修改为指向下一个元素。 it 是可解引用的或过尾的。
&it == &++ it。
如果 it1 == it2,
那么 ++ it1 == ++ it2。
后置递增 it ++ 与 ++ it 相同。 等价于
{
 I itt = it;
 ++ it;
 return itt;
}		 it 是可解引用的或过尾的。
前置递减 -- it it 是可解引用的或过尾的。
存在一个可解引用的迭代器 itt 使得 it == ++ itt。		 it 被修改为指向上一个元素。 it 是可解引用的。
&it = &-- it.
如果 it1 == it2,
那么 -- it1 == -- it2。
如果 it2 是可解引用的并且 it1 == ++it2,
那么 --it1 == it2。
后置递减 it -- 与 -- it 相同。 等价于
{
 I itt = it;
 -- it;
 return itt;
}		 it 是可解引用的。 
索引 it.index () it 是可解引用的。 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 ()。

复杂度保证

索引双向迭代器上操作的复杂度保证为摊销常数时间。

不变式

恒等式 it1 == it2 当且仅当 &*it1 == &*it2。
递增和递减的对称性 如果 it 是可解引用的，那么 ++ it; --it; 是一个空操作。类似地，-- it; ++ it; 是一个空操作。
迭代器索引和容器元素操作符之间的关系 如果 it 是可解引用的， *it == it () (it.index ())。

模型

索引随机访问迭代器

描述

索引随机访问迭代器是一个容器的迭代器，它可以被解引用、向前移动、向后移动，并携带索引信息。

细化自

可小于比较, 索引双向迭代器 。

关联类型

值类型 通过解引用索引随机访问迭代器获得的值的类型
容器类型 索引随机访问迭代器指向的容器的类型。

符号

I 作为索引随机访问迭代器模型的类型
T I 的值类型
C I 的容器类型
it, itt, it1, it2 类型为 I 的对象
t 类型为 T 的对象
n 类型为 C::difference_type 的对象

定义

如果通过对 it2 应用有限次数的 operator ++ 后，it1 == it2，则索引随机访问迭代器 it1 是从索引随机访问迭代器 it2 可达的。

有效表达式

除了为 索引双向迭代器 定义的表达式外，以下表达式必须有效。

名称 表达式 类型要求 返回类型
向前移动 it += n   I &
迭代器加法 it + n   I
向后移动 i -= n   I &
迭代器减法 it - n   I 
差值 it1 - it2   C::difference_type
元素操作符 it [n]   可转换为 T。
元素赋值 it [n] = t I 是可变的 可转换为 T。

表达式语义

表达式的语义仅在它与 索引双向迭代器 中的定义不同或未定义时才被定义。

名称 表达式 前置条件 语义 后置条件
向前移动 it += n 包括 it 本身，必须有 n 个可解引用的或过尾的迭代器在 it 之后或之前，取决于 n 是正数还是负数。 如果 n > 0，等价于执行 ++ it n 次。如果 n < 0，等价于执行 -- it n 次。如果 n == 0，这是一个空操作。 it 是可解引用的或过尾的。
迭代器加法 it + n 与 i += n 相同。 等价于
{
 I itt = it;
 return itt += n;
}		 结果是可解引用的或过尾的。
向后移动 it -= n 包括 it 本身，必须有 n 个可解引用的或过尾的迭代器在 it 之前或之后，取决于 n 是正数还是负数。 等价于 it += (-n)。 it 是可解引用的或过尾的。
迭代器减法 it - n 与 i -= n 相同。 等价于
{
 I itt = it;
 return itt -= n;
}		 结果是可解引用的或过尾的。
差值 it1 - it2 it1 可从 it2 到达，或 it2 可从 it1 到达，或两者都可。 返回一个数字 n，使得 it1 == it2 + n  
元素操作符 it [n] it + n 存在且是可解引用的。 等价于 *(it + n)  
元素赋值 i[n] = t 与 it [n] 相同。 等价于 *(it + n) = t  

复杂度保证

索引随机访问迭代器上操作的复杂度保证为摊销常数时间。

不变式

加法和减法的对称性 如果 it + n 是良好定义的，那么 it += n; it -= n; 和 (it + n) - n 是空操作。类似地，如果 it - n 是良好定义的，那么 it -= n; it += n; 和 (it - n) + n 是空操作。
距离和加法之间的关系 如果 it1 - it2 是良好定义的，那么 it1 == it2 + (it1 - it2)。
可达性和距离 如果 it1 可从 it2 到达，那么 it1 - it2 >= 0。

模型

索引双向列/行迭代器

描述

索引双向列/行迭代器是一个容器的迭代器，它可以被解引用、递增、递减，并携带索引信息。

细化自

可赋值, 可等价比较, 默认可构造。

关联类型

值类型 通过解引用索引双向列/行迭代器获得的值的类型
容器类型 索引双向列/行迭代器指向的容器的类型。

符号

I1 作为索引双向列/行迭代器模型的类型
I2 作为索引双向行/列迭代器模型的类型
T I1 和 I2 的值类型
C I1 和 I2 的容器类型
it1, it1t, it11, it12 类型为 I1 的对象
it2, it2t 类型为 I2 的对象
t 类型为 T 的对象
c 类型为 C 的对象

定义

有效表达式

除了为可赋值、可等价比较和默认可构造定义的表达式外，以下表达式必须有效。

名称 表达式 类型要求 返回类型
默认构造函数 I1 it    
解引用 *it   可转换为 T。
解引用赋值 *it = t I1 是可变的。  
成员访问 it->m T 是 t.m 被定义的类型。  
前置递增 ++ it   I1 &
后置递增 it ++   I1
前置递减 -- it   I1 &
后置递减 it --   I1
行索引 it.index1 ()   C::size_type
列索引 it.index2 ()   C::size_type
行/列开始 it.begin ()   I2
行/列结束 it.end ()   I2
反向行/列开始 it.rbegin ()   reverse_iterator<I2>
反向行/列结束 it.rend ()   reverse_iterator<I2>

表达式语义

表达式的语义仅在它与可赋值、可等价比较和默认可构造中的定义不同或未定义时才被定义。

名称 表达式 前置条件 语义 后置条件
默认构造函数 I1 it     it 是奇异的。
解引用 *it it 是可解引用的。    
解引用赋值 *it = t 与 *it 相同。   *it 是 t 的副本。
成员访问 it->m it 是可解引用的。 等价于 (*it).m  
前置递增 ++ it it 是可解引用的。 it 被修改为指向列/行的下一个元素，即对于列迭代器成立
it.index1 () < (++ it).index1 () 和
it.index2 () == (++ it).index2 (),
对于行迭代器成立
it.index1 () == (++ it).index1 () 和
it.index2 () < (++ it).index2 ().
 it 是可解引用的或过尾的。
&it == &++ it。
如果 it1 == it2,
那么 ++ it1 == ++ it2。
后置递增 it ++ 与 ++ it 相同。 等价于
{
 I1 itt = it;
 ++ it;
 return itt;
}		 it 是可解引用的或过尾的。
前置递减 -- it it 是可解引用的或过尾的。
存在一个可解引用的迭代器 itt 使得 it == ++ itt。		 it 被修改为指向列/行的上一个元素，即对于列迭代器成立
it.index1 () > (-- it).index1 () 和
it.index2 () == (-- it).index2 (),
对于行迭代器成立
it.index1 () == (-- it).index1 () 和
it.index2 () > (-- it).index2 ().		 it 是可解引用的。
&it = &-- it.
如果 it1 == it2,
那么 -- it1 == -- it2。
后置递减 it -- 与 -- it 相同。 等价于
{
 I1 itt = it;
 -- it;
 return itt;
}		 it 是可解引用的。 
行索引 it.index1 () 如果 it 是行迭代器，则 it 必须是可解引用的。 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 ()。
列索引 it.index2 () 如果 it 是列迭代器，则 it 必须是可解引用的。 it.index2 () >= 0 和
it.index2 () < it () .size2 ()		 如果 it1 == it2,
那么 it1.index2 () == it2.index2 () 。
如果 it1, it2 是列迭代器且 it1 == i12,
那么 it1.index2 () < (++ it2).index2 ()。
end it1.index2 () > (-- it2).index2 ()。
行/列开始 it.begin () it 是可解引用的。 如果 it 是列迭代器,
那么 it2 = it.begin () 是行迭代器
且 it2.index1 () == it.index1 ()。

如果 it 是行迭代器,
那么 it2 = it.begin () 是列迭代器
且 it2.index2 () == it.index2 ()。

  
行/列结束 it.end () it 是可解引用的。 如果 it 是列迭代器,
那么 it2 = it.end () 是行迭代器
且 it2.index1 () == it.index1 ()。

如果 it 是行迭代器,
那么 it2 = it.end () 是列迭代器
且 it2.index2 () == it.index2 ()。

  
反向行/列开始 it.rbegin () it 是可解引用的。 等价于 reverse_iterator<I2> (it.end ())。  
反向行/列结束 it.rend () it 是可解引用的。 等价于 reverse_iterator<I2> (it.begin ())。  

复杂度保证

索引双向列/行迭代器上操作的复杂度保证为对数时间，取决于容器的大小。一个迭代器（取决于存储布局）的复杂度可以提升为摊销常数时间。另一个迭代器（取决于存储布局和容器）的复杂度可以对于第一行/第一列分别提升为摊销常数时间。

不变式

恒等式 it1 == it2 当且仅当 &*it1 == &*it2。
递增和递减的对称性 如果 it 是可解引用的，那么 ++ it; --it; 是一个空操作。类似地，-- it; ++ it; 是一个空操作。
迭代器索引和容器元素操作符之间的关系 如果 it 是可解引用的， *it == it () (it.index1 (), it.index2 ())
迭代器列/行开始和迭代器索引之间的关系 如果 it 是列迭代器且 it2 = it.begin ()，那么对于所有满足 it2t () == it2 () 且 it2t ().index1 () == it2 ().index1 () 的 it2t， it2.index2 () < it2t.index2 ()。

如果 it 是行迭代器且 it2 = it.begin ()，那么对于所有满足 it2t () == it2 () 且 it2t ().index2 () == it2 ().index2 () 的 it2t， it2.index1 () < it2t.index1 ()。
迭代器列/行结束和迭代器索引之间的关系 如果 it 是列迭代器且 it2 = it.end ()，那么对于所有满足 it2t () == it2 () 且 it2t ().index1 () == it2 ().index1 () 的 it2t， it2.index2 () > it2t.index2 ()。

如果 it 是行迭代器且 it2 = it.end ()，那么对于所有满足 it2t () == it2 () 且 it2t ().index2 () == it2 ().index2 () 的 it2t， it2.index1 () > it2t.index1 ()。

模型

索引随机访问列/行迭代器

描述

索引随机访问列/行迭代器是一个容器的迭代器，它可以被解引用、递增、递减，并携带索引信息。

细化自

索引双向列/行迭代器 .

关联类型

值类型 通过解引用索引随机访问列/行迭代器获得的值的类型
容器类型 索引随机访问列/行迭代器指向的容器的类型。

符号

I 作为索引随机访问列/行迭代器模型的类型
T I 的值类型
C I 的容器类型
it, itt, it1, it2 类型为 I 的对象
t 类型为 T 的对象
c 类型为 C 的对象

定义

有效表达式

除了为 索引双向列/行迭代器 定义的表达式外，以下表达式必须有效。

名称 表达式 类型要求 返回类型
向前移动 it += n   I &
迭代器加法 it + n   I
向后移动 i -= n   I &
迭代器减法 it - n   I 
差值 it1 - it2   C::difference_type
元素操作符 it [n]   可转换为 T。
元素赋值 it [n] = t I 是可变的 可转换为 T。

表达式语义

表达式的语义仅在它与 索引双向列/行迭代器 中的定义不同或未定义时才被定义。

名称 表达式 前置条件 语义 后置条件
向前移动 it += n 包括 it 本身，必须有 n 个可解引用的或过尾的迭代器在 it 之后或之前，取决于 n 是正数还是负数。 如果 n > 0，等价于执行 ++ it n 次。如果 n < 0，等价于执行 -- it n 次。如果 n == 0，这是一个空操作。 it 是可解引用的或过尾的。
迭代器加法 it + n 与 i += n 相同。 等价于
{
 I itt = it;
 return itt += n;
}		 结果是可解引用的或过尾的。
向后移动 it -= n 包括 it 本身，必须有 n 个可解引用的或过尾的迭代器在 it 之前或之后，取决于 n 是正数还是负数。 等价于 it += (-n)。 it 是可解引用的或过尾的。
迭代器减法 it - n 与 i -= n 相同。 等价于
{
 I itt = it;
 return itt -= n;
}		 结果是可解引用的或过尾的。
差值 it1 - it2 it1 可从 it2 到达，或 it2 可从 it1 到达，或两者都可。 返回一个数字 n，使得 it1 == it2 + n  
元素操作符 it [n] it + n 存在且是可解引用的。 等价于 *(it + n)  
元素赋值 i[n] = t 与 it [n] 相同。 等价于 *(it + n) = t  

复杂度保证

索引随机访问列/行迭代器上操作的复杂度保证为摊销常数时间。

不变式

加法和减法的对称性 如果 it + n 是良好定义的，那么 it += n; it -= n; 和 (it + n) - n 是空操作。类似地，如果 it - n 是良好定义的，那么 it -= n; it += n; 和 (it - n) + n 是空操作。
距离和加法之间的关系 如果 it1 - it2 是良好定义的，那么 it1 == it2 + (it1 - it2)。
可达性和距离 如果 it1 可从 it2 到达，那么 it1 - it2 >= 0。

模型

版权 (©) 2000-2002 Joerg Walter, Mathias Koch
使用、修改和分发受 Boost 软件许可协议 1.0 版的约束。（请参阅随附文件 LICENSE_1_0.txt 或在 https://boost.ac.cn/LICENSE_1_0.txt 复制）。