Over the pass few weeks, I was reading the a lot of articles about the intrusive list, its benefits of using it, and its use case example on game development. This brings me a strong message that there are so many peoples on Earth promoting this container. What was so special about this container? Due to the limitation on the container provided by STL and intrusive container's low memory footprint which could benefit to the application's performance.
Does Boost provide this container. Yes! During this great moment with a sudden impulse, I begin my journey to develop a demo program using the
Boost Intrusive container. Tadaa~
So far the journey was up and down, a lot of road pump, and feel tired to continue. When trying to remove an item from the list using following method will not work. Before that, let's presume I have the following declaration in the header file:
typedef boost::intrusive::list<FileNode, base_hook<list_base_hook<link_mode<auto_unlink> > >, constant_time_size<false> > FileNodeListType;
class FileBot
{
private:
FileNodeListType fileList;
...
...
};
Then I begin to insert something into the list, assume the object type is a FileNode, do take note that I do this purely in one method:
void FileBot::addFileNode()
{
FileNode *f1 = new FileNode();
f1->setName("ASD");
fileList.push_back(*f1);
cout << "addFileNode(): memory address of insert object: " << f1 << endl;
}
Then I have another method to remove an object from the list:
void FileBot::clearMemoryByName(string filename)
{
cout << "before delete: " << fileList.size() << endl;
FileNode *p = new FileNode();
p->setName("ASD");
fileList.erase(FileNodeListType::s_iterator_to(*p));
delete p;
cout << "clearMemoryByName(): memory address of remove object: " << p << endl;
cout << "after delete: " << fileList.size() << endl;
}
But somehow this method will cause a memory leak due to the following assertion failed in
boost/intrusive/list.hpp, line 1270:
Assertion failed: !node_algorithms::inited(value_traits::to_node_ptr(value)), file D:\tool\boost_1_61_0\msvc\boost/intrusive/list.hpp, line 1270
Detected memory leaks!
Dumping objects ->
...
...
...
Object dump complete.
Press <return> to close this window...
A million hours were spent on studying the weak spot of this creature has finally found a solution. The clue was lying on the memory address of the object. The memory address of the object inserted into the list in
addFileNode() was different from the memory object created in the
clearMemoryByName().
...
addFileNode(): memory address of insert object: 001180C8
clearMemoryByName(): memory address of remove object: 00111DE0
...
In the revise's version, the object was retrieved from the list and then perform some filtering (e.g. match the property field's value), then only perform the deletion.
void FileBot::clearMemoryByName(string filename)
{
FileNode *p = NULL;
FileNodeListType::iterator it(fileList.begin());
for(; it != fileList.end(); it++)
{
cout << &*it << endl;
// look for particular node
string curName = (*it).getName().c_str();
if( filename == curName) {
p = &*it;
break;
}
}
cout << "claerMemoryByName(): memory address of remove object: " << p << endl;
fileList.erase(FileNodeListType::s_iterator_to(*p));
delete p;
The result was stunning! The object was removed from the list. And here is the output of the memory address:
...
addFileNode(): memory address of insert object: 00E2DAF0
claerMemoryByName(): memory address of remove object: 00E2DAF0
...
To conclude this, in order to remove an object from the list, O(n) algorithm is the only way to filter the object, then only come to deletion.
