Comparing Data Structures in C and C++

You may have already seen C++ classes and you think of data structures in terms of a class structure. C does not use classes; however, very often it is very useful to implement some of the philosophies of object-oriented programming, including abstraction, encapsulation, message passing, and modularity.

Here, we will compare similar implementations of the queue data structure, one in C++ using classes and another in C.

Definition

In C++, a data structure would be encapsulated in a class: member variables are private while the interface is implemented through public member functions. In C, all fields in a structure are public and there is no programmatic link between the functions acting on the data structure.

struct Queue {
   void **array;
   int head;
   int tail;
   int array_capacity;
   int initial_capacity;
   int queue_size;
};

void init( struct Queue *, int );
void copy( struct Queue *, struct Queue * );
void deinit( struct Queue * );
// Requires #include <stdbool.h>
bool empty( struct Queue * );
int size( struct Queue * );
void *front( struct Queue * );
void push( struct Queue *, void * );
void pop( struct Queue * );

template <typename T>
class Queue {
   private:
      void **array;
      int head;
      int tail;
      int array_capacity;
      int initial_capacity;
      int queue_size;

   public:
      Queue( int );
      Queue( Queue const & );
      ~Queue();

      bool empty() const;
      int size() const;
      T front() const;

      void push( T const & );
      void pop();
};

Creating Generic Data Structures

In C++, it is possible to create a generic data structure using templates. In the above example, we could declare a queue of integers, or a queue of doubles, a queue of a particular class, or a queue of pointers:

     struct Queue<int> q1( 10 );
     struct Queue<double> q2( 10 );
     struct Queue<Class> q3( 10 );
     struct Queue<Class *> q4( 10 );

In C, this is more difficult: there is a mechanism by which this can be done using #define and macros; however, this is generally difficult. Instead, it is useful to note that in many cases where one wants to store useful information, that data is already stored elsewhere; consequently, it is easiest to define a data structure that stores pointers to what wants to store; hence, void *. Suppose, for example, one has a thread control block data structure and we need a queue to store threads waiting on a particular resource. This could be implemented as follows:

int main() {
    ...
    //
    tcb thread[N];
    ...

    queue waiting;

    ...
    printf( "%d\n", priority( &(thread[i]) ) );
    push( &queue, &(thread[i]) );
    ...
    printf( "%d\n", priority( &(thread[j]) ) );
    push( &queue, &(thread[j]) );
    ...

    // Recast the returned value of 'front()' as a pointer to a thread id
    tcb *ptr = front( &queue );

    printf( "%d\n", priority( ptr ) );
    pop( &queue );
    ...
}

Initialization

In C++, the constructor is called whenever an instance of a class is created. In C, it is necessary to explicitly call the initialization function.

int main() {
   struct Queue q;
   init( &q, 10 );

   struct Queue *pq
      = malloc( sizeof( struct Queue ) );
   init( pq, 10 );

   ...
}

int main() {
   Queue q( 10 );

   Queue *pq = new Queue( 10 );

   ...
}

Calling Interface Functions

In C++, calling a member function uses the same modality as accessing fields in C. What is not so obvious is that the address of the object is implicitly passed as an argument to the function; consequently, the implementation of member function calling is not very different from the explicit passing of the address of the structure in C.

int main() {
   ...

   push( &q, ... );
   printf( "%p\n", front( &q ) );
   pop( &q );

   push( pq, ... );
   printf( "%p\n", front( pq ) );
   pop( pq );

   ...
}

int main() {
   ...

   q.push( ... );
   cout << q.front() << endl;
   q.pop();

   pq->push( ... );
   cout << pq->front() << endl;
   pq->pop();

   ...
}

If you would like evidence that C++ passes the address of the object on which it is being called as a first hidden argument, you can explicitly look for it:

#include <iostream>
using namespace std;

class Example {
   private:

   public:
      void f( void * ) const;
};

void Example::f( void *ptr ) const {
   // Print the address assigned to 'this'
   cout << this << endl;
   // Look at what is implicitly passed immediately
   // prior to the address of the first argument 'ptr'.
   // Recall that the call stack starts at a high
   // value and goes down.
   cout << *(&ptr + 1) << endl;
}

int main() {
   int n;
   Example x;

   // Print the address of 'x'
   cout << &x << endl;

   x.f( &n );

   return 0;
};

When this is compiled, all three addresses are identical:

% g++ Example.cpp 
% ./a.out 
0x7fff8136308b
0x7fff8136308b
0x7fff8136308b

Freeing/Deleting

Like initialization, de-allocating memory assigned for an instance must be done explicitly in C.

int main() {
   ...

   deinit( &q );




   deinit( pq );
   free( pq );
   pq = NULL;

   return 0;
}

int main() {
   ...

   // The compiler automatically calls the
   // destructor on 'q' when the variable
   // goes out of scope.

   // Calling 'delete' also automatically
   // calls the destructor.

   delete pq;
   pq = 0;

   return 0;
}

Helper Functions

In C++, helper functions used internally would be declared to be private. In C, the function would be declared static meaning that it can only be called from another function in the same source file. Suppose we had a function that doubled the memory allocated to the data structure:

struct Queue {
   ...
};

...
// Can only be called by a function
// defined in this .c source file.
static void double_cap( struct Queue * );

template <typename T>
class Queue {
   private:
      ...

      // Can only be called by
      // another member function.
      void double_cap();

   public:
      ...
};

Introduction to Computer Structures and Real-time Systems