Moving a node from one list to another?

This is a discussion on Moving a node from one list to another? within the C++ Programming forums, part of the General Programming Boards category; I'm implementing a multi-branch tree with such a data structure. Code: typedef struct TreeNodeStruct { DataType m_data; list<TreeNodeStruct*> m_children; } ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74

    Moving a node from one list to another?

    I'm implementing a multi-branch tree with such a data structure.
    Code:
    typedef struct TreeNodeStruct
    {
        DataType m_data;
        list<TreeNodeStruct*> m_children;
    } TreeNode;
    Sometimes I have to merge the children, just like this.
    Code:
    // merge the last child into the first child
    root->m_children.front()->push_back(root->m_children.back());
    root->m_children.pop_back();
    But I soon found that the push_back() and pop_back() operations become too slow when the merging repeats many times. (Maybe these frequent operation is making the memory a mess?) So I'm wondering whether there is a way to "move" a node directly from one list to another so we do not have to call new() and delete() on memory frequently. Is STL providing such a way to do that? Or can we implement it ourselves?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    You want splice:
    splice - C++ Reference
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    Well I found the answer myself. Just using list.splice() to do that...
    Code:
    myOtherList.splice(myOtherList.end(), myList, oldIt);
    from Erasing items from an STL list - Stack Overflow

  4. #4
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    Oh thanks. I didn't see your reply.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. urgent help please...
    By peter_hii in forum C++ Programming
    Replies: 11
    Last Post: 10-30-2006, 05:37 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. question about a working linked list
    By cold_dog in forum C++ Programming
    Replies: 23
    Last Post: 09-13-2006, 01:00 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21