Custom bidimensional iterator and container

[nick]

Hi,
I need to manage a "layered" collection of objects, where each layer
grows independently, e.g,

o--+--+--+--+--+ 1st layer
|
o 2nd layer (empty)
|
o--+--+--+ 3rd layer
|
o--+--+ 4th layer

This data structure should be a random access container (the goal is to
use it as a custom VertexList in boost.Graph for a graph whose nodes are
partitioned into layers). Besides being able to iterate over all the
elements, (horizontal) iteration over a single layer and (vertical)
iteration over the set of layers are required. Insertion at the end of
each layer must be efficient, so "flattening" the data structure into,
say, a linear vector is not a viable solution.

I haven't found anything that suits my needs, so I came out with the
code below. As this is my first attempt at writing a user defined
container and iterator - and I found the task a bit tricky - I would
appreciate some feedback about how my solution can be improved. In the
worst case, moving the iterator takes time proportional to the number of
layers, so probably this is not a "real" random access container.

Thanks,
Nicola

#include <vector>
#include <iterator>

// Iterator over elements of LayeredContainer<T>
template <typename LayeredCont>
class LayeredIterator :
public std::iterator<std::random_access_iterator_tag, LayeredCont>
{
protected:
typename LayeredCont::InLayerIterator currH; // current pos. in layer
typename LayeredCont::CrossLayersIterator currV; // current layer
typename LayeredCont::CrossLayersIterator firstV; // first layer
typename LayeredCont::CrossLayersIterator lastV; // last layer

public:
typedef LayeredIterator<LayeredCont> iterator;
typedef LayeredIterator<const LayeredCont> const_iterator;

LayeredIterator() : currH(), currV(), firstV(), lastV() { }

// Build an iterator pointing at the first element
explicit LayeredIterator(LayeredCont& c) {
firstV = c.firstLayer();
lastV = c.lastLayer();
currV = firstV;
// Search for the first non-empty layer (if it exists)
while ((*currV).empty() && currV != lastV)
++currV;
currH = (*currV).begin();
}

bool operator==(const LayeredIterator& c) const {
return (this->currH == c.currH);
// '&& this->currV == c.currV' is redundant
}

bool operator!=(const LayeredIterator& c) {
return !(*this == c);
}

typename LayeredCont::reference operator*() const {
return *currH;
}

typename LayeredCont::pointer operator->() const {
return &*currH;
}

// Prefix increment operator
LayeredIterator& operator++() {
++currH;
while (currH == (*currV).end() && currV != lastV) {
++currV;
currH = (*currV).begin();
}
return *this;
}

// Prefix decrement operator
LayeredIterator& operator--() {
while (currH == (*currV).begin()) {
--currV;
currH = (*currV).end();
}
--currH;
return *this;
}

LayeredIterator& operator+=(typename LayeredCont::difference_type n) {
if (n >= 0) { // Move forward
typename LayeredCont::difference_type offset = (*currV).end() -
currH;
while (n >= offset && currV != lastV) {
++currV;
n -= offset;
currH = (*currV).begin();
offset = (*currV).end() - currH;
}
}
else { // Move backwards
typename LayeredCont::difference_type offset = (currH -
(*currV).begin());
while (-n >= offset && currV != firstV) {
--currV;
n += offset;
currH = (*currV).end();
offset = currH - (*currV).begin();
}
}
currH += n;
return *this;
}

LayeredIterator operator+(typename LayeredCont::difference_type n)
const {
LayeredIterator tmp(*this);
return tmp += n;
}

LayeredIterator& operator-=(typename LayeredCont::difference_type n) {
return *this += -n;
}

// Etc.. The rest is more or less easily syntactic sugar.
};
------------------------------------------------------------
#include <vector>
#include <deque>
#include <stdexcept>
#include "LayeredIterator.hpp"

template <typename T, template <typename E, typename ALLOC =
std::allocator<E> > class Layer = std::vector >
class LayeredContainer {
public:
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
typedef T* pointer;
typedef const T* const_pointer;
typedef std::ptrdiff_t difference_type;
typedef size_t size_type;

// Global iterators
typedef LayeredIterator<LayeredContainer> iterator;
typedef LayeredIterator<const LayeredContainer> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef const std::reverse_iterator<iterator> const_reverse_iterator;

typedef std::deque< Layer<T> > LayersContainer;

// Iterators inside a single layer
typedef typename Layer<T>::iterator InLayerIterator;
typedef typename Layer<T>::const_iterator InLayerConstIterator;
// Iterators across the layers
typedef typename LayersContainer::iterator CrossLayersIterator;
typedef typename LayersContainer::const_iterator
CrossLayersConstIterator;

InLayerIterator beginOfLayer(const int i) {return layers[i].begin();}
InLayerConstIterator beginOfLayer(const int i) const
{ return layers[i].begin();}
InLayerIterator endOfLayer(con st int i) { return layers[i].end(); }
InLayerConstIterator endOfLayer(const int i) const
{ return layers[i].end(); }

CrossLayersIterator firstLayer() { return layers.begin(); }
CrossLayersConstIterator firstLayer() const { return layers.begin(); }
CrossLayersIterator lastLayer() { return layers.end() - 1; } // Well
defined, there is always at least one layer
CrossLayersConstIterator lastLayer() const { return layers.end() - 1;
}
CrossLayersIterator beyondLastLayer() { return layers.end(); }
CrossLayersConstIterator beyondLastLayer() const { return
layers.end(); }
iterator begin() { return _start; }
iterator end() { return _start + _size; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _start + _size; }
reverse_iterator rbegin() { return
reverse_iterator(_start + _size); }
reverse_iterator rend() { return
reverse_iterator(_start); }
const_reverse_iterator rbegin() const { return
const_reverse_iterator(_start + _size); }
const_reverse_iterator rend() const { return
const_reverse_iterator(_start); }

// Default constructor
LayeredContainer() : _size(0) {
layers.push_back(Layer<T>()); // One layer
_start = iterator(*this);
}

LayeredContainer(std::size_t numLayers) {
for (std::size_t i = 0; i < numLayers; ++i)
layers.push_back(Layer<T>());
_size = 0;
_start = iterator(*this);
}

std::size_t numberOfLayers() const {
return layers.size();
}

T get(int _layer, int index) const {
return layers[_layer][index];
}

void add(std::size_t _layer, const T& value) {
layers[_layer].push_back(value);
++_size;
_start = iterator(*this); // How may I improve this?
}

reference operator[](std::size_t index) {
return *(_start + index);
}

size_type size() { return _size; }
bool empty() { return (0 == _size); }

protected:
LayersContainer layers;
iterator _start;
size_type _size;
};
-------------------------------------------------------------
// TEST
#include <iostream>
#include <LayeredVector.hpp>

int main (int argc, char* const argv[]) {
typedef LayeredContainer<int> LayeredVector;
LayeredVector lv(4);
// Insert some elements
lv.add(1, 2);
lv.add(1, 3);
lv.add(1, 5);
lv.add(1, 7);
lv.add(3, 10);
lv.add(3, 20);
lv.add(3, 30);
LayeredVector::iterator it;
for (it = lv.begin(); it != lv.end(); ++it)
std::cout << *it << " ";
std::cout << std::endl << "Second layer: ";
LayeredVector::InLayerConstIterator lit;
for (lit = lv.beginOfLayer(1); lit != lv.endOfLayer(1); ++lit)
std::cout << *lit2 << " ";
return 0;
}