Posts tagged pointers

The STL is a very well designed library, and iterators is a powerful concept. Unfortunately you can not fully utilize the power of iterators unless you write generic code:

template<typename Iterator>
myfunc(Iterator begin, Iterator end) {
  // Do stuff
}

Now the function does not depend on the type of the iterator being used in the call. However C++, being a multi-paradigm language means you might be writing OO code and not generic code. E.g. you might have defined an interface on one of your classes:

class MyInterface {
  virtual void GetStuff(int count, vector<int>::iterator out) const = 0;
};

I can’t define interface methods to be template based. The problem with the interface above is that I force the receiver to use a particular kind of iterator. E.g. I have to write code like this:

vector<int> buffer(count);
myvar->GetStuff(count, buffer.begin());

But what if I need buffer to be of any of these alternative types?

 int * 
 QVector<int> 
 vector<int, myallocator>  

Then I would be screwed, because they all have a different concrete iterator type. However if we change the interface to:

class MyInterface {
  virtual void GetStuff(int count, int *out) const = 0;
};

Then we can use any kind of vector type:

vector<int> buffer(count);
myvar->GetStuff(count, &buffer[0]);

This code does not care which type buffer is as long as it represents an array of data in contiguous memory.

These observations give a few rules of thumb for when to use iterators and when to use pointers. * Never use iterators to receive data. Use pointers. * Let your internal data be accessed only through STL style iterators, but only ever use these iterators with generic functions. This will allow you to change internal container type without breaking code. If you use non-template functions you will break code.
* Never return pointers to your internal data. Instead push or pull data to/from external buffers through pointers. Non-generic functions should interface with pointer based methods.

So say I have a polygon class I should be able to do stuff like:

// generic function so use iterators
std::sort(poly.beginVertices(), poly.endVertices());
std::vector<Vertex> buffer(10);

// setting and getting values, so use pointers
poly.getVertices(&buffer[0], poly.size());
poly.setVertices(&buffer[0], poly.size());

// Non-template based class, so use pointers
vertexProcessor->doStuff(&buffer[0], poly.size());

// If class was template based, then we could to it like this
vertexProcessor.doStuff(poly.beginVertices(), poly.endVertices());

I know the first objection you probably have is that the pointer solution leads to a lot of unnecessary copying of data. That is potentially a performance bottleneck, right? Not necessarily. Typically you don’t need to try to optimize this. If it proves to be a problem the solution is fairly simple. Copy out only small chunks at a time. E.g. fetch 10 elements, do some processing, fetch the next 10 elements. Rinse repeat.

If you have a small fixed size buffer you keep pull data into, it will most likely stay in cache and it will be very fast to copy the data into it.