(重新)在非标准容器中使用 std::algorithms [英] (Re)Using std::algorithms with non-standard containers
问题描述
我有一个列"容器类型:
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
};
用法:
// 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::algorithms 用于我的类型的随机访问迭代器，例如sort(注意:排序比较将由用户定义的函子提供，例如 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 进行了类似的尝试.但是，我无法让他们的方法与 sort 一起工作.使用代理类型方法很难满足像 defaultConstructible 这样的要求(为什么 std::sort 要求类型是默认可构造的而不是可交换的，这超出了我的理解).
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:我不能执行以下操作:
struct MyType {
double a;
string b;
int c;
};
std::vector<MyType> v;
然后使用std::algorithm.
动机:表现.一个缓存行通常是 64 字节，即 8 个双精度.在这个简单的结构中，如果您对双精度进行迭代，则会污染带有一个 int 字符串的缓存行.在其他情况下，每个缓存行可能只传输 1 次.也就是说，您最终使用了可用内存带宽的 1/8.如果您需要迭代几个 Gb 的双精度数，这个简单的决定可以将您的应用程序性能提高 6-7 倍.不，我不能放弃.
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.
推荐答案
我认为这样的事情可能符合标准.它使用了一些 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.
经过测试并与 clang++3.2 配合使用
Tested and works with 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();
};
迭代器类:value_type (all_copy)、reference 类型 (all_reference) 和迭代器类型 (all_iterator).迭代是通过保持和更新三个迭代器(每个 vector 一个)来完成的.不过，我不知道这是否是性能最高的选项.
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.traits]/1
How it works: std::iterator_traits defines several associated types for an iterator:
[iterator.traits]/1
iterator_traitsiterator_traitsiterator_traits
分别定义为迭代器的差异类型、值类型和迭代器类别.此外，类型iterator_traitsiterator_traits
应定义为迭代器的引用和指针类型，即对于迭代器对象a，分别与*a和a->的类型相同
因此，您可以引入一个结构(all_reference)，将三个引用保留为 reference 类型.此类型是 *a 的返回值，其中 a 是迭代器类型(可能是 const 限定的).需要有一个不同的 value_type 因为一些标准库算法比如 sort 可能想要创建一个局部变量临时存储 *a 的值(通过复制或移动到局部变量中).在这种情况下，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::sort 需要一个比较函数.出于某种原因，我们必须提供所有三个.
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;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,
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,
这篇关于(重新)在非标准容器中使用 std::algorithms的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
