V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
morefreeze
V2EX  ›  C

递归里操作 list 是不是作死

  •  
  •   morefreeze · 2015-09-08 20:12:19 +08:00 · 1456 次点击
    这是一个创建于 3362 天前的主题,其中的信息可能已经有所发展或是发生改变。

    代码大概像这样:

    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 )

    12 条回复    2015-09-10 11:23:38 +08:00
    noli
        1
    noli  
       2015-09-08 20:55:22 +08:00   ❤️ 1
    @morefreeze 一般来说,奇怪的要求总是来自于奇怪的理解方式…… 请问问什么你希望要保持所谓“下标”的位置?

    要不用 unordered_map 吧,能够满足你的要求。
    morefreeze
        2
    morefreeze  
    OP
       2015-09-08 22:20:47 +08:00
    @noli 其实很容易理解,我需要用一个 list 来维护当前的状态,而这中间有许多插入删除操作。抛开我说的一大堆不看,大家觉得应该怎么搞。另外假设考虑效率。
    cyr1l
        3
    cyr1l  
       2015-09-08 22:28:23 +08:00
    @morefreeze  1楼说的对,应该是业务逻辑问题,应该有更好的解决方式,可能你理解错了。

    如果一定要这样的话, 你可以复制 list 为 newList , 插入删除都操作 newList 。
    noli
        4
    noli  
       2015-09-08 22:42:25 +08:00
    @morefreeze 有很多插入删除,跟维持“下标”位置有什么关系吗……
    如果你希望用一个所谓的下标,而这个下标所对应的内容会不断删除又插入,那么 unordered_map 才是你应该用的。而不是什么鬼 list
    morefreeze
        5
    morefreeze  
    OP
       2015-09-09 10:57:23 +08:00
    @noli 我举个例子,每次的递归都是将一个链表相邻两个元素合并,出递归后要将刚才合并的两个元素再还原回来,你用什么数据结构?
    如果说这问题怎么解决,你说的 unordered_map 确实可行,平均操作时间可以是常数的,可以接受

    我用下标只是为了更好说明问题,要不你说一个链表元素我怎么描述他?
    维持“下标”和插入删除当然有关系啊,因为更深的递归可能把当前下标所指内容删掉了,然后又还原了,但显然上层的已经指不向这个新的了,换句话说这层这个迭代器相当于就是废了。而且我也意识到,想搞定引用下标是最简单的,所以只要带下标的并且插入删除效率高的都可以解决了。因此你要不给我来个不带下标的解决办法?
    yuyang
        6
    yuyang  
       2015-09-09 11:54:49 +08:00
    诡异的需求造就诡异的代码, 诡异的代码造就一大坨 bug, 一大坨 bug 造就了苦逼的程序猿, LZ 你已在这条路上渐行渐远. 请保重
    morefreeze
        7
    morefreeze  
    OP
       2015-09-09 13:41:12 +08:00
    @yuyang 呵呵呵 你说这有蛋用 我就是发贴问下这应该怎么搞 不用 list 就不用 像楼上那样给个方案
    而且需求并不诡异 就是一个场景需要有删除插入,那我自然就想到链表了
    顺便说下这问题我昨天用 vector 也解决 只是想知道更快的方法
    你也保重吧
    kof12345
        8
    kof12345  
       2015-09-09 15:44:32 +08:00
    比如 list 长度是 3 , it 指向下标 1 ,如果两次释放后, it 相当于被释放掉了,之后再申请的话, it 已经找不到新元素的位置了
    ================================================
    改变迭代器位置,所有 insert 操作改为 insert_after 。
    morefreeze
        9
    morefreeze  
    OP
       2015-09-09 15:50:27 +08:00
    @kof12345 没明白什么意思 我重读了我写的句子,应该没说清, it 指向下标 1 ,假如进一层,会释放下标 2 ,再进一层,会释放下标 1 ,所以这时最上层的 it 已经指向一块被释放的空间了,但最下层在往回退的时候,会 insert 新的元素(相当于恢复现场),但 it 仍然没法指向新 insert 的元素。
    这和 insert 是不是插在后面没有关系吧
    kof12345
        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 之后插入也是对的。
    noli
        11
    noli  
       2015-09-09 20:13:14 +08:00   ❤️ 1
    @morefreeze 递归合并链表里面的元素,用下标的方式来关联元素,本身就是不恰当的模型。为什么不直接用树?
    morefreeze
        12
    morefreeze  
    OP
       2015-09-10 11:23:38 +08:00
    @noli 哦哦哦 确实是个树的样子,可以一层一层往上合并,多谢大牛点拨
    我被删除相邻操作限制住了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5343 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 09:04 · PVG 17:04 · LAX 01:04 · JFK 04:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.