C++-STL deque迭代器+=操作符实现

C++-STL deque迭代器+=操作符实现

偏爱自由 发布于 2017-08-09 字数 1026 浏览 1053 回复 1

SGI STL中deque容器迭代器以实现可以实现随机存取,即可以直接跳跃n个距离。由于deque底层是由很多个分段连续空间组成的,因此实现随机存取比vector要复杂不少。

下面是操作符+=实现随机存取的源代码(来自STL源码剖析-侯捷):

 self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
//buffer_size()返回缓冲区能容纳的元素个数
if (offset >= 0 && offset < difference_type(buffer_size()))
// 目标位置在同一个缓冲区内
cur += n;
else {
// 目标位置部在同一个缓冲区内
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;//????????????????
// 切换至正确的节点
set_node(node + node_offset);
// 切换至正确的元素
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

偏爱自由 2017-09-18 1 楼

实现节点位移量向上取整。
当offset的值大于n个缓冲区的大小且小于n+1个缓冲区的大小时,这段代码可以确保节点的位移量向上取整为n+1。
当offset的值刚好为n个缓冲区的大小时,这段代码又可以将节点的位移量调整为n。
当offset的值不足1个缓冲区的大小时,这段代码又可以确保节点位移量最小为1。
你可以待定系数试试看的。