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.
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 typesiterator_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
anda->
, 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,
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With