PDA

View Full Version : qDeleteAll() and linked list iterators



jkyle
27th June 2010, 17:40
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.


Node* next = previous_node->next();

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.


#include <iostream>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
#include <boost/iterator/iterator_facade.hpp>

using namespace std;

struct node
{
node() : m_next(0) {}

node(int *x)
: m_value(x)
{}

// Each node manages all of its values
~node()
{
delete m_value;
}

// Access the rest of the list
node* next() const { return m_next; }

void append(node* p)
{
if (m_next)
m_next->append(p);
else
m_next = p;
}


int value() const { return *m_value;}

private:
int *m_value;
node *m_next;

};

template <class Value>
class node_iter
: public boost::iterator_facade<
node_iter<Value>
, Value
, boost::forward_traversal_tag
, Value*
>
{
private:
struct enabler {};

public:
node_iter()
: m_node(0) {}

explicit node_iter(Value* p)
: m_node(p) {}

template <class OtherValue>
node_iter(node_iter<OtherValue> const& other,
typename boost::enable_if<
boost::is_convertible<OtherValue*,Value*>,
enabler>::type = enabler() )
: m_node(other.m_node) {}

private:
friend class boost::iterator_core_access;
template <class> friend class node_iter;

template <class OtherValue>
bool equal(node_iter<OtherValue> const& other) const
{
return this->m_node == other.m_node;
}

void increment()
{
m_node = m_node->next();
}

Value* dereference() const
{
return m_node;
}

Value* m_node;
};
typedef node_iter< node > node_iterator;
typedef node_iter< node const > node_const_iterator;


int main ()
{
node *n1 = new node(new int(5));
node *n2 = new node(new int(10));
node *n3 = new node(new int(15));

n1->append(n2);
n2->append(n3);

node_iterator begin(n1);
node_iterator end(0);


// qDeleteAll() algorithm
// while(begin != end) {
// delete *begin;
// can't increment! node required to iterate
// ++begin;
// }

// works for all STL iterators independent of internal implementaiton
node *temp;
while(begin != end) {
temp = *begin;
++begin;
delete temp;
}

return 0;
}

Have I missed something or is this a real problem?

Vit Stepanek
29th June 2010, 11:58
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.

jkyle
29th June 2010, 23:18
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.