Using templates to conditionally generate data members of a C++ class

Question

I have a class that works as a set of integers in some fixed range 0 ... n and can easily deal with adding a new element, removing an element, emptying the set and checking if an integer is part of the set. The code of the class is followed.

Also, as can be seen in the code, if option COMPUTE_SET_SIZE is present, the class computes the size of the set and, if option COMPUTE_LINKED_LIST is present, one can use the class to efficiently enumerate set elements.

Now, the problem is that enumerating set elements is a heavy operation in terms of memory usage and, lots of the time, it's not needed. Therefore, I want to somehow be able to generate those parts of the code only when they are needed without having to maintain two different classes (one with this functionality and one without).

I understand that templates (such as std::enable_if) can be used to achieve similar goals but I fail to understand how I can use them to conditionally generate data members such as prev and next in the following code.

#ifndef _FIXED_SIZE_INT_SET_H_
#define _FIXED_SIZE_INT_SET_H_

#include <cstring>

#include <assert.h>

#define COMPUTE_SET_SIZE
#define COMPUTE_LINKED_LIST

class FixedSizeIntSet
{
    private:
        const int MAX_TAG = 1000000000;
        int capacity;
        int currentTag;
        int *tags;

#ifdef COMPUTE_SET_SIZE
        int size;
#endif

#ifdef COMPUTE_LINKED_LIST
        int start;
        int *next;
        int *prev;
#endif

        void initialize() { memset(tags, 0, capacity * sizeof(int)); }
    public:
        FixedSizeIntSet(int capacity)
        {
            this->capacity = capacity;
            this->currentTag = 1;
            tags = new int[capacity];

#ifdef COMPUTE_SET_SIZE
            size = 0;
#endif

#ifdef COMPUTE_LINKED_LIST
            start = -1;
            next = new int[capacity];
            prev = new int[capacity];
#endif

            initialize();
        }

        void insert(int n)
        {
            assert((n >= 0) && (n < capacity));
#ifdef COMPUTE_SET_SIZE
            if (tags[n] != currentTag) size++;
#endif
#ifdef COMPUTE_LINKED_LIST
            if (tags[n] != currentTag)
            {
                next[n] = start;
                prev[n] = -1;
                if (start >= 0)
                    prev[start] = n;
                start = n;
            }
#endif
            tags[n] = currentTag;
        }
        void remove(int n)
        {
            if ((n >= 0) && (n < capacity))
            {
#ifdef COMPUTE_SET_SIZE
                if (tags[n] == currentTag) size--;
#endif
#ifdef COMPUTE_LINKED_LIST
                if (tags[n] == currentTag)
                {
                    if (next[n] >= 0)
                        prev[next[n]] = prev[n];
                    if (prev[n] >= 0)
                        next[prev[n]] = next[n];
                    else
                        start = next[n];
                }
#endif
                tags[n] = 0;
            }
        }
        void clear()
        {
            if (currentTag < MAX_TAG)
                currentTag++;
            else { initialize(); currentTag = 1; }
#ifdef COMPUTE_SET_SIZE
            size = 0;
#endif
#ifdef COMPUTE_LINKED_LIST
            start = -1;
#endif
        }

        bool hasMember(int n) { return ((n >= 0) && (n < capacity)) ? (currentTag == tags[n]) : false; }

#ifdef COMPUTE_LINKED_LIST
        int begin() { return start; }
        int end() { return -1; }
        int nextNumber(int curNumber) { assert((curNumber >= 0) && (curNumber < capacity)); return next[curNumber]; }
#endif
};

#endif

Ideally, I would like a code like this:

template <bool enableEnumeration>
class FixedSizeIntSet {
  ....
}

So that FixedSizeIntSet<false> does not compute linked list (and does not have associated data members) while FixedSizeIntSet<true> computes linked lists.

Answer 1

Here's one way to address your design problem.

Definition of the class.

#ifndef _FIXED_SIZE_INT_SET_H_
#define _FIXED_SIZE_INT_SET_H_

#include <cstring>

#include <assert.h>

template <typename Trait>
class FixedSizeIntSet : public Trait
{
    private:
        const int MAX_TAG = 1000000000;
        int capacity;
        int currentTag;
        int *tags;

        void initialize() { memset(tags, 0, capacity * sizeof(int)); }
    public:
        FixedSizeIntSet(int capacity) : Trait(capacity)
        {
            this->capacity = capacity;
            this->currentTag = 1;
            tags = new int[capacity];
            initialize();
        }

        void insert(int n)
        {
            assert((n >= 0) && (n < capacity));
            if (tags[n] != currentTag)
            {
               Trait::insert();
            }
            tags[n] = currentTag;
        }
        void remove(int n)
        {
            if ((n >= 0) && (n < capacity))
            {
                if (tags[n] == currentTag) 
                {
                   Trait::remove(n);
                }
                tags[n] = 0;
            }
        }
        void clear()
        {
            if (currentTag < MAX_TAG)
                currentTag++;
            else { initialize(); currentTag = 1; }
            Trait::clear();
        }

        bool hasMember(int n) { return ((n >= 0) && (n < capacity)) ? (currentTag == tags[n]) : false; }
};

#endif

Usage:

struct ComputeSetSize
{
   ComputeSetSize(int ) : size(0) {}
   void insert(int ) { ++size; }
   void remove(int ) { --size; }
   void clear() { size = 0; }
   int size;
};

struct ComputeLinkedList
{
   ComputeLinkedList(int capacity)
   {
      start = -1;
      next = new int[capacity];
      prev = new int[capacity];
   }

   void insert(int n)
   {
      next[n] = start;
      prev[n] = -1;
      if (start >= 0)
         prev[start] = n;
      start = n;
   }

   void remove(int n)
   {
      if (next[n] >= 0)
         prev[next[n]] = prev[n];
      if (prev[n] >= 0)
         next[prev[n]] = next[n];
      else
         start = next[n];
   }

   void clear()
   {
      start = -1;
   }

   int begin() { return start; }
   int end() { return -1; }
   int nextNumber(int curNumber) { assert((curNumber >= 0) && (curNumber < capacity)); return next[curNumber]; }

   int capacity;
   int size;
   int start;
   int *next;
   int *prev;
};


int main()
{
   FixedSizeIntSet<ComputeSetSize> set1(10);
   FixedSizeIntSet<ComputeLinkedList> set2(20);
}