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();
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.
#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;
}
#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;
}
To copy to clipboard, switch view to plain text mode
Have I missed something or is this a real problem?
Bookmarks