Results 1 to 3 of 3

Thread: qDeleteAll() and linked list iterators

  1. #1
    Join Date
    May 2010
    Posts
    14
    Thanked 2 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    MacOS X Unix/X11 Windows

    Default qDeleteAll() and linked list iterators

    I have a custom container class with STL iterators. It's based on a linked list. I was getting bad memory access errors with qAlgorithms::qDeleteAll(...). That was when I noticed that qDeleteAll deletes the iterators dereferenced object before incrementing the iterator.

    In a linked list, the item object itself provides the next reference in the chain. e.g.

    Qt Code:
    1. Node* next = previous_node->next();
    To copy to clipboard, switch view to plain text mode 

    This pattern will not work with qDeleteAll(..). I've put together a basic example using boost::iterator_facade template for creating STL iterators. It's commented out an example of the original qDeleteAll() method and included a loop that would work for any stl container.

    Qt Code:
    1. #include <iostream>
    2. #include <boost/type_traits/is_convertible.hpp>
    3. #include <boost/utility/enable_if.hpp>
    4. #include <boost/iterator/iterator_facade.hpp>
    5.  
    6. using namespace std;
    7.  
    8. struct node
    9. {
    10. node() : m_next(0) {}
    11.  
    12. node(int *x)
    13. : m_value(x)
    14. {}
    15.  
    16. // Each node manages all of its values
    17. ~node()
    18. {
    19. delete m_value;
    20. }
    21.  
    22. // Access the rest of the list
    23. node* next() const { return m_next; }
    24.  
    25. void append(node* p)
    26. {
    27. if (m_next)
    28. m_next->append(p);
    29. else
    30. m_next = p;
    31. }
    32.  
    33.  
    34. int value() const { return *m_value;}
    35.  
    36. private:
    37. int *m_value;
    38. node *m_next;
    39.  
    40. };
    41.  
    42. template <class Value>
    43. class node_iter
    44. : public boost::iterator_facade<
    45. node_iter<Value>
    46. , Value
    47. , boost::forward_traversal_tag
    48. , Value*
    49. >
    50. {
    51. private:
    52. struct enabler {};
    53.  
    54. public:
    55. node_iter()
    56. : m_node(0) {}
    57.  
    58. explicit node_iter(Value* p)
    59. : m_node(p) {}
    60.  
    61. template <class OtherValue>
    62. node_iter(node_iter<OtherValue> const& other,
    63. typename boost::enable_if<
    64. boost::is_convertible<OtherValue*,Value*>,
    65. enabler>::type = enabler() )
    66. : m_node(other.m_node) {}
    67.  
    68. private:
    69. friend class boost::iterator_core_access;
    70. template <class> friend class node_iter;
    71.  
    72. template <class OtherValue>
    73. bool equal(node_iter<OtherValue> const& other) const
    74. {
    75. return this->m_node == other.m_node;
    76. }
    77.  
    78. void increment()
    79. {
    80. m_node = m_node->next();
    81. }
    82.  
    83. Value* dereference() const
    84. {
    85. return m_node;
    86. }
    87.  
    88. Value* m_node;
    89. };
    90. typedef node_iter< node > node_iterator;
    91. typedef node_iter< node const > node_const_iterator;
    92.  
    93.  
    94. int main ()
    95. {
    96. node *n1 = new node(new int(5));
    97. node *n2 = new node(new int(10));
    98. node *n3 = new node(new int(15));
    99.  
    100. n1->append(n2);
    101. n2->append(n3);
    102.  
    103. node_iterator begin(n1);
    104. node_iterator end(0);
    105.  
    106.  
    107. // qDeleteAll() algorithm
    108. // while(begin != end) {
    109. // delete *begin;
    110. // can't increment! node required to iterate
    111. // ++begin;
    112. // }
    113.  
    114. // works for all STL iterators independent of internal implementaiton
    115. node *temp;
    116. while(begin != end) {
    117. temp = *begin;
    118. ++begin;
    119. delete temp;
    120. }
    121.  
    122. return 0;
    123. }
    To copy to clipboard, switch view to plain text mode 

    Have I missed something or is this a real problem?

  2. #2
    Join Date
    Apr 2010
    Posts
    34
    Thanks
    1
    Thanked 5 Times in 5 Posts
    Qt products
    Qt4
    Platforms
    Unix/X11 Windows

    Default Re: qDeleteAll() and linked list iterators

    What are you trying to do exactly?
    Do you want to make it use qDeleteAll, or what?

    By the way, the implementation of the "node" struct is very confusing. The item given to be stored is copied in the ctor using shallow copy, but then you delete it in the dtor like it were a deep copy. This will lead to troubles.

  3. #3
    Join Date
    May 2010
    Posts
    14
    Thanked 2 Times in 2 Posts
    Qt products
    Qt4
    Platforms
    MacOS X Unix/X11 Windows

    Default Re: qDeleteAll() and linked list iterators

    I just threw that together real quick. That should be a pointer to the stored value, rather than a shallow copy (looking for edit button).

    What it's supposed to demonstrate is a valid STL iterator that requires the dereferenced value of the iterator to increment. qDeleteAll(...) deletes the dereferenced value before iterating. Resulting in a memory access error on iteration.

Similar Threads

  1. Trouble implementing a linked list.
    By Bonafide in forum Qt Programming
    Replies: 3
    Last Post: 21st February 2010, 22:13
  2. corrupted double-linked list
    By reuabreliz in forum Installation and Deployment
    Replies: 2
    Last Post: 6th January 2010, 14:15
  3. Replies: 26
    Last Post: 21st July 2007, 22:34
  4. QLinkedList and iterators
    By eu.x in forum Newbie
    Replies: 1
    Last Post: 19th April 2007, 20:38
  5. Linked List
    By merry in forum Qt Programming
    Replies: 10
    Last Post: 14th March 2007, 08:07

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.