===================================================== 582484 Algorithm Libraries ===================================================== -------------------- Exercise 5 solutions -------------------- 1. Checksum using exclusive-or: .. include:: teht1.cpp :literal: 2. You can use valgrind_ to test whether your program leaks memory or not. The program is installed on department's linux machines. Typical usage looks like: ``valgrind --tool=memcheck --leak-check=yes a.out`` Try it before and after changing the list example. a. Releasing allocated memory after nodes are no longer used, can be done, for instance, using a recursive destructor. When the head of the list is deleted, the node pointed to by the ``next`` pointer will be deleted recursively. This process stops when the end of the list is reached (next == 0). :: ~node() { std::cout << "-------- deleting " << val << std::endl; delete next; } When deleting single elements using ``erase_after``, we have to be careful not to delete the whole end part of the list. Therefore, the next field of the node to be deleted is first set to zero:: void erase_after (iterator iter) { node* p = iter.ptr; if (p==0) { p = &head; } if (p->next != 0) { node* tmp = p->next; p->next = p->next->next; tmp->next = 0; delete tmp; } } b. When using the boost smart pointers, we don't explictly need to delete the nodes. We just have to use smart pointers instead of raw pointers. But note that in iterator, we still use raw pointers. This is because we don't want iterators to own the elements they point to. If we have an iterator pointing to an element, and when we delete the element, the iterator gets invalidated and should not be used. ``boost::shared_ptr`` is very strict about making implicit conversions between raw and smart pointers. That's why we need to add a few explicit calls to the constructor and the ``get()`` member function, which returns the raw pointer. .. include:: teht2b.cpp :literal: .. _valgrind: http://www.valgrind.org