Array: Storing Objects or References

Question

As a Java developer I have the following C++ question.

If I have objects of type A and I want to store a collection of them in an array, then should I just store pointers to the objects or is it better to store the object itself?

In my opinion it is better to store pointers because: 1) One can easily remove an object, by setting its pointer to null 2) One saves space.

Answer 1

Pointers or just the objects?

You can't put references in an array in C++. You can make an array of pointers, but I'd still prefer a container and of actual objects rather than pointers because:

1. No chance to leak, exception safety is easier to deal with.
2. It isn't less space - if you store an array of pointers you need the memory for the object plus the memory for a pointer.

The only times I'd advocate putting pointers (or smart pointers would be better) in a container (or array if you must) is when your object isn't copy construable and assignable (a requirement for containers, pointers always meet this) or you need them to be polymorphic. E.g.

#include <vector>

struct foo {
  virtual void it() {}
};

struct bar : public foo {
  int a;
  virtual void it() {}
}; 

int main() {
  std::vector<foo> v;
  v.push_back(bar()); // not doing what you expected! (the temporary bar gets "made into" a foo before storing as a foo and your vector doesn't get a bar added)
  std::vector<foo*> v2;
  v2.push_back(new bar()); // Fine
}

If you want to go down this road boost pointer containers might be of interest because they do all of the hard work for you.

Removing from arrays or containers.

Assigning NULL doesn't cause there to be any less pointers in your container/array, (it doesn't handle the delete either), the size remains the same but there are now pointers you can't legally dereference. This makes the rest of your code more complex in the form of extra if statements and prohibits things like:

// need to go out of our way to make sure there's no NULL here
std::for_each(v2.begin(),v2.end(), std::mem_fun(&foo::it));

I really dislike the idea of allowing NULLs in sequences of pointers in general because you quickly end up burying all the real work in a sequence of conditional statements. The alternative is that std::vector provides an erase method that takes an iterator so you can write:

v2.erase(v2.begin());

to remove the first or v2.begin()+1 for the second. There's no easy "erase the nth element" method though on std::vector because of the time complexity - if you're doing lots of erasing then there are other containers which might be more appropriate.

For an array you can simulate erasing with:

#include <utility>
#include <iterator>
#include <algorithm>
#include <iostream>

int main() {
  int arr[] = {1,2,3,4};
  int len = sizeof(arr)/sizeof(*arr);
  std::copy(arr, arr+len, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  // remove 2nd element, without preserving order:
  std::swap(arr[1], arr[len-1]);
  len -= 1;
  std::copy(arr, arr+len, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;

  // and again, first element:
  std::swap(arr[0], arr[len-1]);
  len -= 1;
  std::copy(arr, arr+len, std::ostream_iterator<int>(std::cout, " "));
  std::cout << std::endl;
}

preserving the order requires a series of shuffles instead of a single swap, which nicely illustrates the complexity of erasing that std::vector faces. Of course by doing this you've just reinvented a pretty big wheel a whole lot less usefully and flexibly than a standard library container would do for you for free!