Ruminations on the standard C++ library — Dynamic arrays

It was late evening… the computer lab was devoid of people and I was supposed to have gone home countless hours earlier, but the assignment was due tomorrow and the code was still not working properly. I was struggling with a dynamically resizing array that I had written some days earlier, but something was just not working right…

The class I had made was looking something like this:

struct DynArray {
  void** elements;
  int size;

  DynArray() : elements(0) {}
  ~DynArray() { free(elements); }

  void add(void* elem) {
    void** elems;
    elems = malloc(sizeof(void*) * (size + 1));
    memcpy(elems, elements, sizeof(void*) * size);
    memcpy(elems + size, elem, sizeof(void*));
    elements = elems;
  }
};

and I was using it in a way not much different from:

int i;
struct DynArray* sDAVar;

sDAVar = (struct DynArray*)malloc(sizeof(struct DynArray));

for (i = 0; i < 20000; i++) {
  int* pnVar = (int*)malloc(sizeof(int));
  *pnVar = i;
  sDAVar->add(pnVar);
}

well… not exactly, but the effects of the code was about the same — just a lot longer and more convoluted, but I still had the problem with this code.

‘Writing C in C++, are you? Why not just do away with the rest of the high-level constructs and use C alone then?’

I almost spilled the half of my Cola that was left over myself at the voice. I had heard no-one walk through the lab to where I was sitting. I whirled around in my chair and saw a guy, probably a few years older than myself, wearing black robes… something not quite usual around here.

‘Uh… excuse me?’ I managed to stutter, ‘what do you mean?’ I hoped my fear of him pulling a sacrifical dagger from the folds of his robes in the next moment wasn’t evident on my face.

‘You are using C allocations, which aren’t type safe and which are, furthermore, easy to pass an incorrect element size to.’ He pointed at the many malloc’s in my code. ‘You should be using C++’s new to allocate your memory. Like this…’ He reached forward and changed a bit in my code.

struct DynArray {
  void** elements;
  int size;

  DynArray() : elements(0) {}
  ~DynArray() { free(elements); }

  void add(void* elem) {
    void** elems;
    elems = malloc(sizeof(void*) * (size + 1));
    memcpy(elems, elements, sizeof(void*) * size);
    memcpy(elems + size, elem, sizeof(void*));
    elements = elems;
  }
};

int i;
struct DynArray* sDAVar;

sDAVar = new DynArray();

for (i = 0; i < 20000; i++) {
  int* pnVar = new int(i);
  sDAVar->add(pnVar);
}

‘Uhm… but, don’t I need to convert what is returned from new to the proper type? You know… like I did before with malloc?’

‘Not at all — new knows what type you are trying to allocate, as well as its size, which is why you do not need to supply the sizeof(int), for instance, in the latter part of your code, and because it knows this it also knows the type to return. In other words, it is type safe.’ he cleared his throat. ‘That, however, was the least of your abominations…’ he pulled out a thick book from the folds of his robes. ‘You are reinventing the wheel… and you aren’t doing too great at that either. Wouldn’t it be wonderful if the Standard C++ Library provided a dynamically resizing array for you?’

I was starting to feel a bit uncomfortable… I had, after all, worked with C for the past many years, but here he was calling my code abominable. But, after looking at the same code for three hours straight now I was desperate for a clue. ‘Uhm… well… I don’t really know the Standard Library too well for C++, we were just told to use this language for the assignment and I’m trying the best I can.’

‘Yes, indeed, they are not keen to teach “tools” as they call the languages here… sad, for many need them.’ Shaking his head shortly he continued on, ‘Anyway, the Standard C++ Library does indeed contain a dynamically resizing array, it is called vector and is placed in the header file of the same name… here, like this.’ he said and added a line to the top of my source file.

#include <vector>

Something started to dawn on me. ‘Oh yeah, right, I think I’ve seen that somewhere before, just there was a .h on it like #include <vector.h>. Is that the—’

A frown appeared on the robed man’s face. ‘No! vector.h is a legacy header from the time before C++ was standardised. Some compilers had this header and several current compilers keep it for legacy purposes. However, you should not use it in new code in any way as it is not part of the standard and thus your compiler does not need to include it. But, let’s return to your code and rewrite it to use vector.’ He leaned over and started to type on my keyboard for a few moments, quickly removing the class I had made. He reduced my code to something like this:

#include <vector>

std::vector<int> myvector;

for (int i = 0; i < 20000; ++i) {
  myvector.push_back(i);
}

‘Let me explain this briefly.’ he said and pointed at the code. ‘All parts of the standard library are placed in a separate namespace called std. So as vector is part of the standard library it can be found in the std namespace by typing std::vector. Why this is a good idea is irrelevant for its use, you just have to remember to type std:: before you type vector when you use it.’

I nodded solemnly to indicate that I understood that much. ‘What about the angled brackets around int, then?’ I asked.

‘They indicate the type stored in the dynamic array. Here you are storing int’s in it. The vector class is a template, which means it is written to store generic types… much like the code you had just before where you were storing void*’s, but with vector this generality is type safe, because of the template construct. I doubt I can explain that concept to you before midnight so perhaps we should just concentrate on how to use the dynamic array, no?’

I blinked my eyes a few times, still trying to digest the abundance of information thrown at me constantly. I finally managed to, quite intelligently, stammer ‘Uh… ok.’

‘Just like your add method appended elements to the end of your array then push_back achieves the same thing for the vector. This, of course, without the bugs in your code.’ he smiled a bit. ‘Now, you can use it completely like a normal array, you just need to know the amount of elements you have stored in the vector so you don’t accidentally go past the bounds and access memory you should not.’

Finally something I completely understood. ‘Ok, so I just add an int counting the number of elements I add and use that when I access the elements, right?’

He shook his head vigorously, ‘No no no no, not at all. The vector maintains an element count for you. You can get the number of elements currently stored in the vector as the result of the size method. Like this:’

#include <vector>
#include <iostream>

int main() {
  std::vector<int> myvector;

  for (int i = 0; i < 20000; ++i)
    myvector.push_back(i);

  for (int j = 0; j > myvector.size(); ++j)
    std::cout << myvector[j] << std::endl;
}

‘Do note that it, like the array, does not validate the bounds, but apart from that it works like your standard dynamic array, which makes it very easy to use the rudimentaries of it.’ he noted ‘If you want to have bounds-checking then vector includes another method that will do that for you, namely the at-method. So using that your last loop would look like this:’

for (int j = 0; j < myvector.size(); ++j)
  std::cout << myvector.at(j) << std::endl;

‘Nice,’ I said. ‘this seems a lot nicer than what I was going at with my own code. I suppose it would do me good to learn some more of the standard library.’ The robed guy nodded, ‘At the first convenient chance ponder the words of Josuttis in his Standard C++ Library book’ [2]. ‘Now you should be able to fix your original problem, which was a memory leak, by the way.’ he pointed at the screen.

When I turned around to thank him for his help he had already left. With a slight shiver I returned to the screen, my half-finished Cola and the keyboard.

Ten minutes later I had managed to convert my code to use std::vector and the strange bug caused by the memory leak had disappeared. As I walked down the empty corridors I made a mental note to figure out who this Josuttis guy was and what material the robed guy had been referring to.

References

  1. This article and subsequent ones have been modelled over the same theme as a long running series of articles by Herb Sutter and Jim Hyslop that appear monthly in the expert section of The C/C++ User Journal.

  2. Nicolai M. Josuttis, The C++ Standard Library: A Tutorial and Reference. Addison-Wesley. ISBN: 0-201-37926-0.

Sub-Pages