这是一个创建于 3355 天前的主题，其中的信息可能已经有所发展或是发生改变。
代码大概像这样:
list<int> foo;
void dfs (){
foo.erase (it );
dfs ();
foo.insert (it, last_value );
}
如果调用更深一些后， it 就变成野指针了，比如 list 长度是 3 ， it 指向下标 1 ，如果两次释放后， it 相当于被释放掉了，之后再申请的话， it 已经找不到新元素的位置了，但因为递归是有还原操作的，所以我想 it 在这层递归完后，还能指向下标 1 ，请问这种怎么操作？
简单点做的话用 vector 并记录下标是可以的，只是删除操作不是 O (1 )
 |
1
noli 2015-09-08 20:55:22 +08:00  1
|
 |
2
morefreeze OP @noli 其实很容易理解，我需要用一个 list 来维护当前的状态，而这中间有许多插入删除操作。抛开我说的一大堆不看，大家觉得应该怎么搞。另外假设考虑效率。
|
 |
3
cyr1l 2015-09-08 22:28:23 +08:00
|
|
4
noli 2015-09-08 22:42:25 +08:00
@morefreeze 有很多插入删除，跟维持“下标”位置有什么关系吗……
如果你希望用一个所谓的下标，而这个下标所对应的内容会不断删除又插入，那么 unordered_map 才是你应该用的。而不是什么鬼 list |
|
5
morefreeze OP @noli 我举个例子，每次的递归都是将一个链表相邻两个元素合并，出递归后要将刚才合并的两个元素再还原回来，你用什么数据结构？
如果说这问题怎么解决，你说的 unordered_map 确实可行，平均操作时间可以是常数的，可以接受 我用下标只是为了更好说明问题，要不你说一个链表元素我怎么描述他？ 维持“下标”和插入删除当然有关系啊，因为更深的递归可能把当前下标所指内容删掉了，然后又还原了，但显然上层的已经指不向这个新的了，换句话说这层这个迭代器相当于就是废了。而且我也意识到，想搞定引用下标是最简单的，所以只要带下标的并且插入删除效率高的都可以解决了。因此你要不给我来个不带下标的解决办法？ |
 |
6
yuyang 2015-09-09 11:54:49 +08:00
诡异的需求造就诡异的代码, 诡异的代码造就一大坨 bug, 一大坨 bug 造就了苦逼的程序猿, LZ 你已在这条路上渐行渐远. 请保重
|
|
7
morefreeze OP @yuyang 呵呵呵 你说这有蛋用 我就是发贴问下这应该怎么搞 不用 list 就不用 像楼上那样给个方案
而且需求并不诡异 就是一个场景需要有删除插入，那我自然就想到链表了 顺便说下这问题我昨天用 vector 也解决 只是想知道更快的方法 你也保重吧 |
 |
8
kof12345 2015-09-09 15:44:32 +08:00
比如 list 长度是 3 ， it 指向下标 1 ，如果两次释放后， it 相当于被释放掉了，之后再申请的话， it 已经找不到新元素的位置了
================================================ 改变迭代器位置，所有 insert 操作改为 insert_after 。 |
|
9
morefreeze OP @kof12345 没明白什么意思 我重读了我写的句子，应该没说清， it 指向下标 1 ，假如进一层，会释放下标 2 ，再进一层，会释放下标 1 ，所以这时最上层的 it 已经指向一块被释放的空间了，但最下层在往回退的时候，会 insert 新的元素（相当于恢复现场），但 it 仍然没法指向新 insert 的元素。
这和 insert 是不是插在后面没有关系吧 |
|
10
kof12345 2015-09-09 19:32:42 +08:00
@morefreeze
好吧，我承认写得太简单了。 前提是，你的递归流程不可以删除比 it 更前的元素，但可以删除 it 指向的元素。 例如 it 指向 [0, 1, 2, 3] 的 1 ，后面的递归流程可以删除 1 / 2 / 3 。 如果我理解错了，请无视我的回答。 如果确实是这样理解，还没有留意到 insert_after 比 insert_before 好吗？ 继续上面的例子，如果递归流程真的删掉 1 / 2 / 3 ，那下一个元素在 0 之后插入也是对的。 |
|
11
noli 2015-09-09 20:13:14 +08:00 1
@morefreeze 递归合并链表里面的元素，用下标的方式来关联元素，本身就是不恰当的模型。为什么不直接用树？
|
|
12
morefreeze OP @noli 哦哦哦 确实是个树的样子，可以一层一层往上合并，多谢大牛点拨
我被删除相邻操作限制住了 |
Select Language