A class with virtual functions must have virtual destructor

It is as simple as that:

A class with at least one virtual function must have virtual destructor.

Virtual functions are a part of the basic object-oriented mechanisms — polymorphism. And since you introduced a virtual function, sooner or later you will allocate an object of derived class, holding it with a pointer to base class, eventually deleting that pointer — and that’s when virtual destructor comes into action!

As you should know, when a pointer to base class, pointing to an object of derived class, is deleted, the destructor of the derived class — the actual (run time) type of the object, — is called only if the base class declares the destructor virtual. Otherwise, if the base class does not declare a virtual destructor, the worst thing that may happen will happen for sure, including leak of memory and other resources, and application crash.

For that matter, the destructor should have been declared virtual automatically when a virtual function is introduced in the class. At the very least, it is lesser evil than not having it declared virtual automatically. But, for good tradition to be able to shoot oneself in the foot, it isn’t.

Let’s recap: introduction of virtual functions in the class leads to polymorphic usage of one, polimorphic class must have virtual destructor.

So for the bottom line: you don’t want to hurt yourself, always declare destructor virtual if you introduce a virtual function in the class.

Because we can!

The title is the answer to a common question: Why do something? So once in a while we do something worthiness of which is questionable. This is that very case.

In the manner that a code snippet is worth a thousand words let’s get straight: we use CRTP like this:

template<typename type, typename tag>
struct Base
{};

template<typename type, typename tag>
void f(const Base<type, ta>&)
{}

struct Foo : Base<Foo, void>
{};

int main()
{
  Foo foo;
  f(foo); 
}

Here f() in fact doesn’t care about the tag and accepts any object derived from Base. But would it be more convenient if we just omit the tag we are not interested in? Check it out:

template<typename t>
struct base_tag { typedef decltype(get_tag((t*)42)) type; };

template<typename type,
         typename tag = typename base_tag<type>::type>
struct Base
{
  friend tag get_tag(type*);  //never defined
};

template<typename type>
void f(const Base<type>&)
{}

struct Foo : Base<Foo, void>
{};

int main()
{
  Foo foo;
  f(foo);
}

Continue reading

Put implementation details in an anonymous namespace

It is common to declare an entity in a header file and define it in a source file (.cpp). For example:

unsigned foo(unsigned, unsigned);  //declaration
#include <cassert>
unsigned helper(unsigned a, unsigned b)  //helper function
{
  assert(a<=b);
  return b - a;
}
unsigned foo(unsigned a, unsigned b)  //definition
{
  return a<=b ? helper(a, b) : helper(b, a);
}

In non-trivial cases one often uses helpers to ease the implementation or to reuse the code in several places.

Once in a while it happens that another module uses the same names for implementation detail entities. And you are lucky if the linker breaks down loud in this case! Otherwise it silently discards one of the entities with coinciding names and uses the other in all places, which is likely to crash your app. This is hard to debug even if you know about such an issue beforehand because everything compiles ok and every module passes individual tests, but it breaks when you build the application as a whole. (I encountered just that in a some-30000-lines project. That is: it turns out to be hard to keep all the names unique. And in fact you don’t need to.)

The remedy for this issue is anonymous namespaces.
Continue reading

Just delete pointers

Delete pointers like this:

delete p;

Although there is a common idiom, don’t do this:

if (p)  //<--this is redundant
  delete p;

In fact the condition checking is redundant since the section 5.3.5 [expr.delete] of the C++ Standard says:

[…] if the value of the operand of delete is the null pointer the operation has no effect.

The same applies to the free() C library function, i.e. if the value of the provided pointer is null the call to the function does nothing.

Distance from a point to a polyline

This is a simple routine for finding the shortest squared Euclidean distance from a query point to a polyline in 2D. It implements a somewhat trivial algorithm, but reinventing it each time is tedious. Also I tried to find such an algorithm online but failed, perhaps because it is way too trivial. Those are basically the reasons for the snippet being here. It goes as follows:

struct point
{
  double x, y;
};

inline double sqr(double a) { return a*a; }
inline double sqrlen(const point &a)
{ return sqr(a.x) + sqr(a.y); }
inline point operator-(const point &a, const point &b)
{
  const point c = {a.x - b.x, a.y - b.y};
  return c;
}

double sqr_distance(const std::vector<point> &points,
                    const point &q)
{
  const size_t count = points.size();
  assert(count>0);
  point
    b = points[0],
    dbq = b - q;
  double dist = sqrlen(dbq);
  for (size_t i = 1; i<count; ++i)
  {
    const point
      a = b,
      daq = dbq;
    b = points[i];
    dbq = b - q;
    const point dab = a - b;
    const double
      inv_sqrlen = 1./sqrlen(dab),
      t = (dab.x*daq.x + dab.y*daq.y)*inv_sqrlen;
    if (t<0.)
      continue;
    double current_dist;
    if (t<=1.)
      current_dist = sqr(dab.x*dbq.y - dab.y*dbq.x)*inv_sqrlen;
    else//t>1.
      current_dist = sqrlen(dbq);
    if (current_dist<dist)
        dist = current_dist;
  }
  return dist;
}

Here is a codepad snippet.
Continue reading

100 points partitioned in a KD tree

Nearest neighbor search using KD trees

Possibly the most widely known application of KD trees is searching: given a set of points find one that is, in some sense, the nearest to the given query point. KD tree allows one to do such queries in O(log(n)) time each. So obviously KD trees are used when one need to do many searches in the same data set, otherwise the “naïve” linear search is faster. What’s more is that for very small number of points (say, tens) linear search is always faster than KD tree approach. But when to start using KD trees? 4, 8, 15, 16, 23, 42 points? 108 points? We’ll find it out!
Continue reading

100 points partitioned in a KD tree

A practical implementation of KD trees

Once I needed a data structure for caching of relatively large sets of 2D points. I looked for many of the variants of binary space partitioning trees, quad tree, navigation net, and even cover tree (as well as those I can’t remember). I struggled for a couple of days until I realized that the good old KD tree perfectly satisfies all my requirements. And its implementation is really easy.

A KD tree is a data structure for storing k-dimensional points. It has some interesting properties, for example, as for almost any tree structure, it can be traversed in O(log(n)) time, where n is the number of points in that tree.

To build a tree one continuously splits the space cyclically alternating the orientation of the split plane so each time it is aligned to one of the dimensions. Given the bounding box each split divides the box into two sub boxes, which in turn are further divided by the following splits. Finally we end up with a tree of boxes, leaving points in the smallest ones (leaf boxes at the last level of the tree).
Continue reading

Find integer log base 2 of an integer

Here you can read about an algorithm for finding integer log2 of an 8 bit integer. There is a description of such an algorithm for 32 bit integers in the Bit Twiddling Hacks collection. Further investigation showed that a similar algorithm may be derived for arbitrary number of bits of an integer. So in short here are the general procedures (codepad snippet). Look-up table initialization:

uint_type b[bits];

void init_log2()
{
  for (int i = 0; i<bits; ++i)
    b[uint_type(c*((2<<i) - 1))>>s] = i;
  return;
}

The log2 function:

uint_type log2(uint_type v)
{//first round down to one less than a power of 2
  for (int i = 1; i<bits; i <<= 1) //unroll for speed
    v |= v>>i;
  return b[uint_type(v*c)>>s];
}

Here uint_type is the unsigned integer type, bits is the length of uint_type, s defined as
s = bits - log2(bits)
and c is the “magic constant”.
Continue reading

Expressing “concept refinement” relationship using CRTP

Curiously Recurring Template Pattern (CRTP)

As defined by Wikipedia: “The curiously recurring template pattern is a C++ idiom in which a class X derives from a class template instantiation using X itself as template argument”. An example of implementation of CRTP looks like this:

template<typename derived>
class base
{};

class some_class : public base<some_class>
{
  //useful members
};

Then we can write a function like

template<typename type>
void foo(base<type> &expr)
{
  type &a = static_cast<type&>(expr);
  //working with 'a'
  return;
}

which takes as its argument only objects of types derived from base in a specific way. This is one of possible ways to express concepts, that is, we state that a type which derive from our base (the concept) must model specific behavior and satisfy specific requirements, otherwise the code will not work.

A Straightforward Approach

Suppose we are developing a generic geometry library and want to express the conceptual relationships of polygons. Then we have (for instance) a polygon with arbitrary number of vertexes. It is refined by quadrangle (or tetragon) which has 4 vertexes, which in turn is refined by parallelogram (has parallel sides), it is refined by rectangle (all right angles), and finally a square – regular quadrangle (which is an important figure too). Every level of refinement adds new properties to the general definition. In particular we can say that a square is a rectangle. This is so because these concepts are connected with an “is‑a” relationship.
Continue reading