Checksum using exclusive-or:
#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <boost/lambda/lambda.hpp>
struct xor_functor : public std::binary_function<int,int,int>
{
int
operator()(int a, int b) const { return a^b; }
};
int main()
{
int sum;
int temp[] = {12, 43, 23, 1, 102, 20};
int n = sizeof(temp)/sizeof(temp[0]);
std::vector<int> v(temp, temp+n);
std::copy(v.begin(), v.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// using our own functor
sum = std::accumulate(v.begin(), v.end(), 0, xor_functor());
std::cout << "Checksum is " << sum << std::endl;
// using boost lambda library
using boost::lambda::_1;
using boost::lambda::_2;
sum = std::accumulate(v.begin(), v.end(), 0, _1 ^ _2);
std::cout << "Checksum is " << sum << std::endl;
return 0;
}
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.
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;
}
}
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 <algorithm>
#include <iterator>
#include <iostream>
#include <boost/shared_ptr.hpp>
struct slist {
struct node;
typedef boost::shared_ptr<node> node_ptr;
slist() : head(0, node_ptr()) {}
// implicit destructor
private:
slist (const slist&); // no copy constructor
slist& operator= (const slist&); // no copy assignment
public:
struct node {
int val;
node_ptr next;
node (int i, node_ptr n) : val(i), next(n) {}
~node() { std::cout << "-------- deleting " << val << std::endl; }
// implicit copy constructor, copy assignment
// no default constructor
};
node head; // a dummy node is the list head
struct iterator
: std::iterator<std::forward_iterator_tag, int>
{
node* ptr;
iterator (node* p = 0) : ptr(p) {}
// implicit copy constructor, copy assignment and destructor
reference operator* () { return ptr->val; }
iterator& operator++ () { ptr = ptr->next.get(); return *this; }
iterator operator++ (int) {
iterator tmp = *this; ++*this; return tmp; }
bool operator== (const iterator& other) const {
return ptr == other.ptr;
}
bool operator!= (const iterator& other) const {
return ptr != other.ptr;
}
};
iterator begin() { return iterator(head.next.get()); }
iterator end() { return iterator(); }
// insert a node after iter, or to the beginning if iter==NULL
void insert_after (iterator iter, int val) {
node* p = iter.ptr;
if (p==0) { p = &head; }
p->next.reset(new node(val, p->next));
}
// erase iter+1 or the first node if iter==NULL
// if iter points to last node or list is empty, nothing is erased
void erase_after (iterator iter) {
node* p = iter.ptr;
if (p==0) { p = &head; }
if (p->next.get() != 0) p->next = p->next->next;
}
};
int main() {
slist c;
c.insert_after(0, 2); // [ 2 ]
c.insert_after(c.begin(), 3); // [ 2 3 ]
c.insert_after(0, 1); // [ 1 2 3 ]
std::copy (c.begin(), c.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
c.erase_after(c.begin()); // [ 1 3 ]
c.erase_after(c.begin()); // [ 1 ]
std::copy (c.begin(), c.end(),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}