(Re)Using std::algorithms with non-standard containers

Question

I have a "column" container type:

struct MyColumnType { 
  // Data: Each row represents a member of an object.
  vector<double> a;   // All vectors are guaranteed to have always
  vector<string> b;   // the same length.
  vector<int> c;

  void copy(int from_pos, int to_pos); // The column type provides an interface
  void swap(int pos_a, int pos_b);     // for copying, swapping, ...

  void push_back();      // And for resizing the container.
  void pop_back();
  void insert(int pos);
  void remove(int pos);
  // The interface can be extended/modified if required
};

Usage:

// If table is a constructed container with elements stored 
// To acces the members of the object stored at the 4th position:
table.a[4] = 4.0;
table.b[4] = "4th";
table.c[4] = 4;

Question: How can I create a standard-compliant random access iterator (and probably a required proxy reference type) for this kind of container?

I want to be able to use std::algorithms for random access iterators with my type, e.g. sort (note: for sorting the comparison would be provided by an user-defined functor, e.g. a lambda).

In particular the iterator should provide an interface similar to

struct {
  double& a;
  string& b;
  int& c;
};

Note 0: C++11/C++14 is allowed.

Note 1: There is an old paper http://hci.iwr.uni-heidelberg.de/vigra/documents/DataAccessors.ps where a similar attempt is undertaken. However, I haven't been able to get their approach working with sort. Requirements like defaultConstructible are hard to satisfy using a proxy type approach (why does std::sort require types to be default constructible instead of swappable is beyond my understanding).

Note 2: I cannot do the following:

struct MyType {
  double a;
  string b;
  int c;
};

std::vector<MyType> v;

and then use std::algorithm.

Motivation: Performance. A cache-line is usually 64bytes, i.e. 8 doubles. In this simple struct if you iterate over the doubles, you are polluting a cache-line with a string an an int. In other cases, you might get only 1 double transfered per cache-line. That is, you end up using 1/8-th of the memory bandwith available. If you need to iterate over a couple of Gb of doubles, this simple decision improves your application performance by a factor of 6-7x. And no, I cannot give that up.

Bonus: the answer should be as generic as possible. Think about adding/removing fields to the container type as adding/removing members to a struct. You don't want to change a lot of code every time you add a new member.

Answer 1

I think something like this could be Standard-compliant. It uses some C++11 features to simplify the syntax, but could as well be changed to comply C++03 AFAIK.

Tested and works with clang++3.2

Prelude:

#include <vector>
#include <string>
#include <utility>  // for std::swap
#include <iterator>

using std::vector;
using std::string;


// didn't want to insert all those types as nested classes of MyColumnType
namespace MyColumnType_iterator
{
    struct all_copy;
    struct all_reference;
    struct all_iterator;
}


// just provided `begin` and `end` member functions
struct MyColumnType {
    // Data: Each row represents a member of an object.
    vector<double> a;   // All vectors are guaranteed to have always
    vector<string> b;   // the same length.
    vector<int> c;

    void copy(int from_pos, int to_pos); // The column type provides an itface
    void swap(int pos_a, int pos_b);     // for copying, swapping, ...

    void push_back();      // And for resizing the container.
    void pop_back();
    void insert(int pos);
    void remove(int pos);
    // The interface can be extended/modified if required


    using iterator = MyColumnType_iterator::all_iterator;
    iterator begin();
    iterator end();
};

The iterator classes: a value_type (all_copy), a reference type (all_reference) and the iterator type (all_iterator). Iterating is done by keeping and updating three iterators (one to each vector). I don't know if that's the most performant option, though.

How it works: std::iterator_traits defines several associated types for an iterator: [iterator.traits]/1

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
be defined as the iterator’s difference type, value type and iterator category, respectively. In addition, the types
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
shall be defined as the iterator’s reference and pointer types, that is, for an iterator object a, the same type as the type of *a and a->, respectively

Therefore, you can introduce a struct (all_reference) keeping three references as reference type. This type is the return value of *a, where a is of the iterator type (possibly const-qualified). There needs to be a different value_type because some Standard Library algorithms such as sort might want to create a local variable temporarily storing the value of *a (by copy or move into the local variable). In this case, all_copy provides this functionality.

You're not required to use it (all_copy) in you own loops, where it could affect performance.

namespace MyColumnType_iterator
{
    struct all_copy;

    struct all_reference
    {
        double& a;
        string& b;
        int& c;

        all_reference() = delete;
        // not required for std::sort, but stream output is simpler to write
        // with this
        all_reference(all_reference const&) = default;
        all_reference(double& pa, string& pb, int& pc)
            : a{pa}
            , b{pb}
            , c{pc}
        {}

        // MoveConstructible required for std::sort
        all_reference(all_reference&& other) = default;
        // MoveAssignable required for std::sort
        all_reference& operator= (all_reference&& other)
        {
            a = std::move(other.a);
            b = std::move(other.b);
            c = std::move(other.c);

            return *this;
        }

        // swappable required for std::sort
        friend void swap(all_reference p0, all_reference p1)
        {
            std::swap(p0.a, p1.a);
            std::swap(p0.b, p1.b);
            std::swap(p0.c, p1.c);
        }

        all_reference& operator= (all_copy const& p) = default;
        all_reference& operator= (all_copy&& p) = default;

        // strict total ordering required for std::sort
        friend bool operator< (all_reference const& lhs,
                               all_reference const& rhs);
        friend bool operator< (all_reference const& lhs, all_copy const& rhs);
        friend bool operator< (all_copy const& lhs, all_reference const& rhs);
    };

    struct all_copy
    {
        double a;
        string b;
        int c;

        all_copy(all_reference const& p)
            : a{p.a}
            , b{p.b}
            , c{p.c}
        {}
        all_copy(all_reference&& p)
            : a{ std::move(p.a) }
            , b{ std::move(p.b) }
            , c{ std::move(p.c) }
        {}
    };

There needs to be a comparison function for std::sort. For some reason we have to provide all three.

    bool operator< (all_reference const& lhs, all_reference const& rhs)
    {
        return lhs.c < rhs.c;
    }
    bool operator< (all_reference const& lhs, all_copy const& rhs)
    {
        return lhs.c < rhs.c;
    }
    bool operator< (all_copy const& lhs, all_reference const& rhs)
    {
        return lhs.c < rhs.c;
    }

Now, the iterator class:

    struct all_iterator
        : public std::iterator < std::random_access_iterator_tag, all_copy >
    {
        //+ specific to implementation
        private:
            using ItA = std::vector<double>::iterator;
            using ItB = std::vector<std::string>::iterator;
            using ItC = std::vector<int>::iterator;
            ItA iA;
            ItB iB;
            ItC iC;

        public:
            all_iterator(ItA a, ItB b, ItC c)
                : iA(a)
                , iB(b)
                , iC(c)
            {}
        //- specific to implementation


        //+ for iterator_traits
            using reference = all_reference;
            using pointer = all_reference;
        //- for iterator_traits


        //+ iterator requirement [iterator.iterators]/1
            all_iterator(all_iterator const&) = default;            // CopyConstructible
            all_iterator& operator=(all_iterator const&) = default; // CopyAssignable
            ~all_iterator() = default;                              // Destructible

            void swap(all_iterator& other)                          // lvalues are swappable
            {
                std::swap(iA, other.iA);
                std::swap(iB, other.iB);
                std::swap(iC, other.iC);
            }
        //- iterator requirements [iterator.iterators]/1
        //+ iterator requirement [iterator.iterators]/2
            all_reference operator*()
            {
                return {*iA, *iB, *iC};
            }
            all_iterator& operator++()
            {
                ++iA;
                ++iB;
                ++iC;
                return *this;
            }
        //- iterator requirement [iterator.iterators]/2

        //+ input iterator requirements [input.iterators]/1
            bool operator==(all_iterator const& other) const        // EqualityComparable
            {
                return iA == other.iA;  // should be sufficient (?)
            }
        //- input iterator requirements [input.iterators]/1
        //+ input iterator requirements [input.iterators]/2
            bool operator!=(all_iterator const& other) const        // "UnEqualityComparable"
            {
                return iA != other.iA;  // should be sufficient (?)
            }

            all_reference const operator*() const                   // *a
            {
                return {*iA, *iB, *iC};
            }

            all_reference operator->()                              // a->m
            {
                return {*iA, *iB, *iC};
            }
            all_reference const operator->() const                  // a->m
            {
                return {*iA, *iB, *iC};
            }

            // ++r already satisfied

            all_iterator operator++(int)                            // *++r
            {
                all_iterator temp(*this);
                ++(*this);
                return temp;
            }
        //- input iterator requirements [input.iterators]/2

        //+ output iterator requirements [output.iterators]/1
            // *r = o already satisfied
            // ++r already satisfied
            // r++ already satisfied
            // *r++ = o already satisfied
        //- output iterator requirements [output.iterators]/1

        //+ forward iterator requirements [forward.iterators]/1
            all_iterator() = default;                               // DefaultConstructible
            // r++ already satisfied
            // *r++ already satisfied
            // multi-pass must be guaranteed
        //- forward iterator requirements [forward.iterators]/1

        //+ bidirectional iterator requirements [bidirectional.iterators]/1
            all_iterator& operator--()                              // --r
            {
                --iA;
                --iB;
                --iC;
                return *this;
            }
            all_iterator operator--(int)                            // r--
            {
                all_iterator temp(*this);
                --(*this);
                return temp;
            }
            // *r-- already satisfied
        //- bidirectional iterator requirements [bidirectional.iterators]/1

        //+ random access iterator requirements [random.access.iterators]/1
            all_iterator& operator+=(difference_type p)             // r += n
            {
                iA += p;
                iB += p;
                iC += p;
                return *this;
            }
            all_iterator operator+(difference_type p) const         // a + n
            {
                all_iterator temp(*this);
                temp += p;
                return temp;
            }
            // doesn't have to be a friend function, but this way,
            // we can define it here
            friend all_iterator operator+(difference_type p,
                                         all_iterator temp)         // n + a
            {
                temp += p;
                return temp;
            }

            all_iterator& operator-=(difference_type p)             // r -= n
            {
                iA -= p;
                iB -= p;
                iC -= p;
                return *this;
            }
            all_iterator operator-(difference_type p) const         // a - n
            {
                all_iterator temp(*this);
                temp -= p;
                return temp;
            }

            difference_type operator-(all_iterator const& p)        // b - a
            {
                return iA - p.iA;   // should be sufficient (?)
            }

            all_reference operator[](difference_type p)             // a[n]
            {
                return *(*this + p);
            }
            all_reference const operator[](difference_type p) const // a[n]
            {
                return *(*this + p);
            }

            bool operator<(all_iterator const& p) const             // a < b
            {
                return iA < p.iA;   // should be sufficient (?)
            }
            bool operator>(all_iterator const& p) const             // a > b
            {
                return iA > p.iA;   // should be sufficient (?)
            }
            bool operator>=(all_iterator const& p) const            // a >= b
            {
                return iA >= p.iA;  // should be sufficient (?)
            }
            bool operator<=(all_iterator const& p) const            // a >= b
            {
                return iA <= p.iA;  // should be sufficient (?)
            }
        //- random access iterator requirements [random.access.iterators]/1
    };
}//- namespace MyColumnType_iterator


MyColumnType::iterator MyColumnType::begin()
{
    return { a.begin(), b.begin(), c.begin() };
}
MyColumnType::iterator MyColumnType::end()
{
    return { a.end(), b.end(), c.end() };
}

Usage example:

#include <iostream>
#include <cstddef>
#include <algorithm>


namespace MyColumnType_iterator
{
    template < typename char_type, typename char_traits >
    std::basic_ostream < char_type, char_traits >&
    operator<< (std::basic_ostream < char_type, char_traits >& o,
                std::iterator_traits<MyColumnType::iterator>::reference p)
    {
        return o << p.a << ";" << p.b << ";" << p.c;
    }
}

int main()
{
    using std::cout;

    MyColumnType mct =
    {
          {1.0, 0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1}
        , {"j", "i", "h", "g", "f", "e", "d", "c", "b", "a"}
        , {10,    9,   8,   7,   6,   5,   4,   3,   2,   1}
    };

    using ref = std::iterator_traits<MyColumnType::iterator>::reference;
    std::copy(mct.begin(), mct.end(), std::ostream_iterator<ref>(cout, ", "));
    std::cout << std::endl;

    std::sort(mct.begin(), mct.end());
    std::copy(mct.begin(), mct.end(), std::ostream_iterator<ref>(cout, ", "));
    std::cout << std::endl;
}

Output:

1;j;10, 0.9;i;9, 0.8;h;8, 0.7;g;7, 0.6;f;6, 0.5;e;5, 0.4;d;4, 0.3;c;3, 0.2;b;2, 0.1;a;1,
0.1;a;1, 0.2;b;2, 0.3;c;3, 0.4;d;4, 0.5;e;5, 0.6;f;6, 0.7;g;7, 0.8;h;8, 0.9;i;9, 1;j;10,

Answer 2

If you're really concerned about performance and you want to sort your container with std::sort, use the overload that allows you to provide a custom comparison object:

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

.. and sort an array of indices into the container. Here's how:

You'll need the following members in your container:

struct MyColumnType { 
    ...

    int size() const;

    // swaps columns
    void swap(int l, int r);

    // returns true if column l is less than column r
    bool less(int l, int r) const;

    ...
};

Then define the following comparison object:

struct MyColumnTypeLess
{
    const MyColumnType* container;
    MyColumnTypeLess(const MyColumnType* container)
        : container(container)
    {
    }
    bool operator()(int l, int r) const
    {
        return container->less(l, r);
    }
};

And use it to sort an array of indices:

void sortMyColumnType(MyColumnType& container)
{
    std::vector<int> indices;
    indices.reserve(container.size());
    // fill with [0, n)
    for(int i = 0; i != container.size(); ++i)
    {
        indices.push_back(i);
    }
    // sort the indices
    std::sort(indices.begin(), indices.end(), MyColumnTypeLess(&container));
}

The 'less' member of the container controls which order to sort in:

bool MyColumnType::less(int l, int r) const
{
    // sort first by a, then b, then c
    return a[l] != a[r] ? a[l] < a[r]
        : b[l] != b[r] ? b[l] < b[r]
        : c[l] < c[r];
}

The sorted array of indices can be used in further algorithms - you can avoid copying the actual data around until you need to.

All std algorithms that work with RandomAccessIterators have overloads that allow you to specify custom comparison objects, so they can also be used with this technique.