作为这个问题的延伸Are const_iterators faster?,我在 const_iterators
上有另一个问题 . 如何删除 const_iterator
的常量?虽然迭代器是指针的通用形式,但仍然是两个不同的东西 . 因此,我相信,我也不能使用 const_cast<>
从 const_iterator
转换为 iterator
.
一种方法可能是您定义一个迭代器,该迭代器将移动到 const_iterator
指向的元素 . 但这看起来像是一个线性时间算法 .
对于实现这一目标的最佳方法有什么想法吗?
9 回答
在C 11中有一个具有恒定时间复杂度的解决方案:对于任何序列,关联或无序关联容器(包括所有标准库容器),可以使用空范围调用范围擦除成员函数:
范围擦除成员函数有一对
const_iterator
参数,但它们返回iterator
. 由于提供了空范围,因此对erase的调用不会更改容器的内容 .Hat tip to Howard Hinnant and Jon Kalb for this trick.
不幸的是,线性时间是唯一的方法:
其中iter和constIter是合适的typedef,d是你要迭代的容器 .
在上一篇文章的答案中,有一些人,包括我在内,建议使用const_iterators代替非性能相关的原因 . 可读性,从设计板到代码的可追溯性......使用const_iterators提供对非const元素的变异访问比从不使用const_iterator要糟糕得多 . 您正在将代码转换为只有您才能理解的内容,设计更糟糕且可维护性更差 . 使用const只是为了抛弃它比使用const完全更糟糕 .
如果你确定你想要它,那么C的好/坏部分就是你可以随时获得足够的绳索来吊死自己 . 如果你的意图是使用const_iterator来解决性能问题,你应该重新考虑它,但是如果你仍然想要开始射击......那么C可以提供你选择的武器 .
首先,最简单的:如果你的操作将参数作为const(即使内部应用const_cast),我相信它应该在大多数实现中直接工作(即使它可能是未定义的行为) .
如果你不能改变仿函数,那么你可以从任何一方解决问题:在const迭代器周围提供一个非const迭代器包装器,或者在非const仿函数周围提供一个const仿函数包装器 .
Iteratorfaçade,漫长的道路:
这可能不是你想要的答案,但有些相关 .
我假设您想要更改迭代器指向的内容 . 我做的最简单的方法是const_cast返回引用 .
像这样的东西
const_cast<T&>(*it);
Scott Meyer's article关于优先于const_iterators的迭代器可以解答这个问题 . Visage的答案是唯一安全的前C 11替代方案,但实际上是实现良好的随机访问迭代器的恒定时间,而其他人则是线性时间 .
我相信在精心设计的程序中不需要这种转换 .
如果您需要这样做 - 尝试重新设计代码 .
作为解决方法,您可以做下一步:
但我认为有时这种转换是不可能的,因为你的算法无法访问容器 .
您可以从const_iterator中减去begin()迭代器以获取const_iterator指向的位置,然后将begin()添加回到该位置以获取非const迭代器 . 我不认为这对于非线性容器非常有效,但对于像线性容器这样的线性容器,这将需要恒定的时间 .
EDIT :这似乎只适用于线性(随机访问)容器 .
你可以将你的const迭代器值指针转换为非const值指针,并直接使用它这样的东西
我认为提出一个适用于不在标准库中的容器并且不包含erase()方法的解决方案会很有趣 .
尝试使用此选项会导致Visual Studio 2013在编译时挂起 . 我不包括测试用例,因为将它留给能够快速找出界面的读者似乎是个好主意;我不知道为什么这会挂起编译 . 即使const_iterator等于begin(),也会发生这种情况 .