从数组里删除一个元素
去年介绍过我在项目中实现的一个动态数组模块的接口。
实际上，我为它提供的接口要更多一些，比如删除一个元素。
void array_erase(struct array *, seqi iter);
原来的语义就是删除 iter 引用的元素。但这里引出一个问题：删除后，iter 是否应该保持有效？
从语义上说，iter 应该在调用完毕后变成一个无效引用。但实际应用中，往往需要在迭代 array 的过程中，删除符合条件的元素。让迭代器失效的做法，用起来很不方便。
因为 array 其实是以一个双向队列的形式实现。以前我取了一个巧，删除这个操作实际上是把当前位置的元素和 array 头部的元素交换，然后将 array 头 pop 出去。
这样，iter 还是指向原地，只是指向的值是已经遍历过的元素。这样，循环则可以继续下去。
今天发现一个问题，如果 iter 一开始就指向头部。那么，在 pop 操作后，iter 还是被设置成无效了。这不是一个 bug ，但是实际效果非常讨厌。思考了一下，决定修改 array_erase 的定义。
array_erase 新的行为被定义成：删除 iter 引用的元素，并将 iter 向后移动。（如果已经到尾部，则变成空引用）
btw, C++ 在处理这个问题时， remove 算法不会做删除操作，而是把符合条件的元素交换到容器尾部，再调用 erase 方法真正删除。也是为了回避类似问题。不过我不太喜欢 remove/remove_if 那种用法。在函数式语言中，那很自然；但对函数式编程支持不足的 C++ 中，使用蹩脚的 template 方法，就不太讨人喜爱了。
Comments
http://code.google.com/p/libcstl/
这个！！！
Posted by: Mattress | (10) September 3, 2010 02:16 PM
用纯C写代码，动态容器还是习惯优先使用list类容器。
Posted by: zwinger | (9) September 2, 2010 11:45 PM
http://code.google.com/p/libcstl/, 嗯，这东西值得考察一下?
Posted by: lichking | (8) September 2, 2010 12:07 PM
如果是遍历需求的删除，开发者而是要封装遍历的接口。比如linux链表中的安全遍历。非常的豪爽
Posted by: lin_style | (7) September 1, 2010 01:18 PM
@feng 用 C 做 STL 这事好像已经是个轮子了
http://code.google.com/p/libcstl/
Posted by: xinghang | (6) August 31, 2010 06:21 PM
迭代和选择性删除的混合操作，stl的实现我觉得还是很值得学习的。光光map在删除之后，要求剩余的迭代访问能够不重不漏顺序不变后续迭代器通通不失效，想了很多数据结构还真只有红黑树旋转有这个效果。
Posted by: zhudage | (5) August 31, 2010 06:20 PM
返回下一个有效的迭代器；vc的std::map的erase就是不遵循标准，给返回值的。时间开销可能要提升一下。不过使用数组表明主要的性能考核指标应该在遍历和随机访问上，而非删除..。
Posted by: zhudage | (4) August 31, 2010 06:10 PM
我会喜欢通过返回值来返回下一个 iter 的值
Posted by: BenBear | (3) August 31, 2010 06:03 PM
楼主有正在做 c 语言版本 stl 的嫌疑.
Posted by: feng | (2) August 31, 2010 05:39 PM
不过一般做法都是失效。C#中foreach语句处理集合，如果集合发生变化会抛出异常。确实蛮不方便
Posted by: rexzhou | (1) August 31, 2010 05:11 PM