我有一个塔容器类型:
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;
问:如何创建一个符合标准的随机访问迭代器(也可能是必需的代理引用类型)这类容器
Question: How can I create a standard-compliant random access iterator (and probably a required proxy reference type) for this kind of container?
我希望能够使用的std ::算法
与我喜欢的类型,如随机访问迭代器排序
(注:排序的比较将通过用户自定义的仿函数来提供,比如一个lambda)。
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;
};
注意0: C ++ 11 / C ++ 14允许
Note 0: C++11/C++14 is allowed.
注意1:有一个古老的纸http://hci.iwr.uni-heidelberg.de/vigra/documents/DataAccessors.ps其中,类似的尝试进行。不过,我一直没能得到他们的做法与排序工作。象缺省构造的要求是很难使用的是代理型的方法来满足(为什么的std ::排序
要求类型为可缺省构造的,而不是交换超出了我的理解)。
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).
注意2:我不能做到以下几点:
Note 2: I cannot do the following:
struct MyType {
double a;
string b;
int c;
};
std::vector<MyType> v;
然后用的std ::算法
。
激励:效果。高速缓存行通常为64字节,即8双打。如果您遍历双打这个简单的结构,你污染了字符串的一个int高速缓存行。在其他情况下,你可能只得到1%的高速缓存行双转移。也就是说,你最终以1/8-日的可用内存带宽的。如果您需要遍历双打的一对夫妇GB的,这个简单的决定提高通过6-7x一个因素应用程序的性能。不,我不能放弃这件事。
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.
奖励:答案应该是尽可能地通用。想想添加/删除字段容器类型的添加/删除成员一个结构。你不希望发生很大的变化$ C $了C每次添加一个新成员。
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.
我觉得这样的事情可能是符合标准的。它使用了一些C ++ 11的特性来简化语法,但可能也被更改为符合C ++ 03 AFAIK。
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.
测试和工程铿锵++ 3.2
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();
};
的迭代器类:一的value_type
( all_copy
),一个引用
型( all_reference
)和迭代器类型( all_iterator )。迭代通过保持和更新3迭代器完成(一至每个向量
)。我不知道这是最高效的选择,虽然。
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.
它是如何工作的:的std :: iterator_traits实现
定义了一个iterator几个相关类型:
[iterator.traits] / 1
How it works: std::iterator_traits
defines several associated types for an iterator:
[iterator.traits]/1
iterator_traits实现&LT;迭代器&GT; :: difference_type
iterator_traits实现&LT;迭代器&GT; :: value_type的
iterator_traits实现&LT;迭代器&GT; ::的iterator_category
分别定义为迭代器的差异型,价值型和迭代器类别。此外,该类型
iterator_traits实现&LT;迭代器&GT; ::引用
iterator_traits实现&LT;迭代器&GT; ::指针
应定义为迭代器的引用和指针类型,那就是,对于一个迭代器对象,类型相同的 *一个
和 A型 - &GT;
,分别为
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
因此,可以引入一个结构( all_reference
)保持为引用三个引用
键入。这种类型是 *一个
,其中 A
的迭代器类型(可能常量 -qualified)。需要有一个不同的的value_type
,因为一些标准库算法,如排序
可能要临时创建一个局部变量存储的值*一个
(通过复制或移动到本地变量)。在这种情况下, all_copy
提供了此功能。
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.
你不使用它需要的( all_copy )在你自己的循环,它可能会影响性能。
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) }
{}
};
需要有一个比较函数的std ::排序
。出于某种原因,我们必须提供所有三个。
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;
}
现在,迭代器类:
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; D]; 10,0.9;我; 9,0.8; H; 8,0.7克; 7,0.6; F; 6,0.5,E,5,0.4,D,4,0.3; C:3 ,0.2; B; 2,0.1;一个; 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克; 7,0.8; H; 8,0.9;我; 9,1; D]; 10,
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,