3
\$\begingroup\$

I'm in the process of writing a matrix like container to store objects. Despite many existing matrix implementations, I won't do numerics. Instead I want to replace a std::vector<std::vector>> variable to increase performance (memory allocation and cache misses are an issue with this double-vector implementation). I want the replacement to behave similar to the double-vector approach. Especially meaning that I can do nested range based for loops. I'm not finished with my class yet but I like to get an early feedback and tips to avoid future problems.

In this class I use boost.facade to create iterators that make a vector like behaviour possible. Note, I'm not finished now and look more for design advice. I'll unit test my code later.

#include <iterator>
#include <vector>
#include <iostream>
#include <initializer_list>
# include <boost/iterator/iterator_facade.hpp>

/// Iterator that points to an element within a collection, which is part of a CollectionVector
template<typename ElementType>
class ElementIterator : public boost::iterator_facade<
        ElementIterator<ElementType>,
        ElementType,
        boost::random_access_traversal_tag >
{
public:
    ElementIterator(ElementType* where) : m_data(where) { }
    ElementIterator(const ElementIterator<ElementType>& other) : m_data(other.m_data) { }
private:
    friend class boost::iterator_core_access;
    bool equal(const ElementIterator& other) const { return m_data==other.m_data; }
    ElementType& dereference() const { return *m_data; }
    void increment() { m_data = ++m_data; }
    void decrement() { m_data = --m_data; }
    void advance(size_t i) { m_data = m_data+i; }
    auto distance_to(const ElementIterator& other) { return other.m_data - m_data; }

    ElementType* m_data;
};

/// Class emulating a vector, i.e. impelementing a vector like interface for accessing collections.
template<typename ElementType>
class Collection
{
public:
    Collection() : m_data(nullptr), m_length(0) { }
    Collection(ElementType* where, size_t length) : m_data(where), m_length(length) { }
    Collection(const Collection& other) : m_data(other.m_data), m_length(other.m_length) { }

    auto begin() { return m_data; }
    auto end() { return m_data+m_length; }
    auto operator[](size_t i) { return *(m_data+i); }
    auto operator+(size_t i) { return Collection<ElementType>(m_data+i*m_length, m_length); }
    auto operator-(size_t i) { return Collection<ElementType>(m_data-i*m_length, m_length); }
    auto& operator++() { m_data = m_data+m_length; return *this; }
    auto& operator--() { m_data = m_data-m_length; return *this; }

private:
    ElementIterator<ElementType> m_data;
    size_t m_length;
};

/// Iterator that points to a Collection within a CollectionVector. Returned when e.g. doing this: collectionvector.at(3).
template<typename ElementType>
class CollectionIterator : public boost::iterator_facade<
        CollectionIterator<ElementType>,
        Collection<ElementType>,
        boost::random_access_traversal_tag,
        Collection<ElementType> >
{
public:
    CollectionIterator() { }
    CollectionIterator(ElementType* where, size_t length) : m_data(where), m_length(length) { }
    CollectionIterator(const CollectionIterator<ElementType>& other) : m_data(other.m_data) { }
private:
    friend class boost::iterator_core_access;
    bool equal(const CollectionIterator& other) const { return m_data==other.m_data; }
    Collection<ElementType> dereference() const { return {m_data, m_length}; }
    void increment() { m_data = m_data+m_length; }
    void decrement() { m_data = m_data-m_length; }
    void advance(size_t i) { m_data = m_data+i*m_length; }
    auto distance_to(const CollectionIterator<ElementType>& other) { return (other.m_data - m_data)/m_length; }

    ElementType* m_data;
    size_t m_length;
};


template<typename ElementType>
class CollectionVector
{
public:
    CollectionVector(size_t size) : m_collectionSize(size)
    {
        if(m_collectionSize<1)
            throw std::invalid_argument( "collection size can not be lower than 1" );
    }

    size_t collectionSize() const {
        return m_collectionSize;
    }

    size_t size() const {
        return m_storage.size()/m_collectionSize;
    }

    bool empty() const {
        m_storage.empty();
    }

    void push_back(std::initializer_list<ElementType> list) {
        if(list.size()!=m_collectionSize)
            throw std::invalid_argument( "wrong number of items" );
        m_storage.insert( std::end(m_storage), std::begin(list), std::end(list) );
    }

    void resize(size_t n) {
        m_storage.resize(n*m_collectionSize);
    }

    void reserve(size_t n) {
        m_storage.reserve(n*m_collectionSize);
    }

    size_t capacity() const {
        return m_storage.capacity()/m_collectionSize;
    }

    void shrink_to_fit() {
        m_storage.shrink_to_fit();
    }

    auto operator[](size_t i) {
        auto it = begin()+i;
        return *it;
    }

    auto at(size_t i) {
        if(size() <= i)
            throw std::out_of_range("index out of bound");
        return operator[](i);
    }

    CollectionIterator<ElementType> begin() {
        return CollectionIterator<ElementType>( &m_storage.front(), m_collectionSize );
    }

    auto end() { // note: past-the-end element of m_data is the same as past-the-end of the collections
        return CollectionIterator<ElementType>( &*(std::end(m_storage)), m_collectionSize );
    }

    auto rawBegin() {
        return std::begin(m_storage);
    }

    auto rawEnd() {
        return std::end(m_storage);
    }

private:
    std::vector<ElementType> m_storage;
    size_t m_collectionSize{1};
};

This can be tested with something like:

int main()
{
    auto a = CollectionVector<int>(3);
    a.push_back({1,2,3});
    a.push_back({4,5,6});
    a.push_back({7,8,9});
    a.push_back({10,11,12});

    for(auto i : a)
        for(auto j : i)
            std::cout<<j<<" ";
}

Edit: Renamed emplace_back() to push_back(), since it does not do an in-place construction.

\$\endgroup\$
  • \$\begingroup\$ "Note, I'm not finished now and look more for design advice." I'd strongly advice you to come back when you're finished. On Code Review, code should work as intended. We can work with half-finished code, but only if you tell us what does work and what doesn't (and if the part that does work can be run on its own). Otherwise you'll get lists of bug reports in the answers which will be countered with you saying 'Oh, yea, that isn't finished yet, don't bother doing anything with it'. \$\endgroup\$ – Mast Feb 4 '17 at 8:14
  • \$\begingroup\$ @Mast I said that because I want to make sure that the way I handle the iterators and the way a vector-like object is returned is a good design. Frankly, I'm not sure what isn't working. This because I do not have a complete test yet since the design might change, based on feedback I get. My question really is, if you guys think this design is solid and what can be done to make it more rigid. \$\endgroup\$ – dani Feb 4 '17 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.