我有一个“列”容器类型：
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 };
用法：
// 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;
问题： 如何为这种容器创建符合标准的随机访问迭代器（可能是必需的代理引用类型）？
我希望能够std::algorithms用于具有我的类型的随机访问迭代器，例如sort（注意：对于排序比较，将由用户定义的函子（例如lambda）提供）。
std::algorithms
sort
特别是，迭代器应提供类似于以下内容的接口
struct { double& a; string& b; int& c; };
注意0： 允许C 11 / C 14。
注1： 有一篇旧论文http://hci.iwr.uni- heidelberg.de/vigra/documents/DataAccessors.ps进行了类似尝试。但是，我无法使其排序有效。使用代理类型方法很难满足诸如defaultConstructible之类的std::sort要求（为什么我不要求将类型设置为默认可构造性而不是可交换性）。
std::sort
注意2： 我无法执行以下操作：
struct MyType { double a; string b; int c; }; std::vector<MyType> v;
然后使用std::algorithm。
std::algorithm
动机： 绩效。高速缓存行通常为64字节，即8倍。在这个简单的结构中，如果您遍历双精度数，则会用字符串an int污染高速缓存行。在其他情况下，每个高速缓存行可能只会传输1次双。也就是说，您最终会使用可用存储带宽的1/8。如果您需要迭代两倍的Gb，那么这个简单的决定将您的应用程序性能提高6-7倍。不，我不能放弃。
奖励： 答案应该尽可能通用。考虑将字段添加/删除到容器类型作为结构的成员添加/删除成员。您不想每次添加新成员时都更改很多代码。
我认为类似这样的东西可能符合标准。它使用一些C 11功能来简化语法，但也可以更改为符合C 03 AFAIK。
经过测试并与clang ++ 3.2配合使用
序幕：
#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(); };
迭代器类：a value_type（all_copy），reference类型（all_reference）和迭代器类型（all_iterator）。迭代是通过保留和更新三个迭代器（每个迭代器一个vector）来完成的。不过，我不知道这是否是性能最高的选项。
value_type
all_copy
reference
all_reference
all_iterator
vector
工作原理：std::iterator_traits为迭代器定义几种关联的类型：[iterator.traits] / 1
std::iterator_traits
iterator_traits<Iterator>::difference_type iterator_traits<Iterator>::value_type iterator_traits<Iterator>::iterator_category 分别定义为迭代器的差异类型，值类型和迭代器类别。另外，类型 iterator_traits<Iterator>::reference iterator_traits<Iterator>::pointer 应定义为迭代器的引用和指针类型，即对于迭代器对象a，其类型分别与*a和的类型相同。a->
iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
*a
a->
因此，您可以引入一个struct（all_reference），将三个引用作为reference类型。此类型是的返回值*a，其中a是迭代器类型（可能是const-qualified）。这需要有所不同，value_type因为某些标准库算法（例如）sort可能想要创建一个临时变量*a（通过复制或移入局部变量）来存储其值的局部变量。在这种情况下，all_copy提供此功能。
a
const
您不需要all_copy在自己的循环中使用它（），因为它可能会影响性能。
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) } {} };
必须具有的比较功能std::sort。由于某些原因，我们必须提供所有这三个。
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; }
现在，迭代器类：
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() }; }
用法示例：
#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; }
输出：
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，
