(重新)在非标准容器中使用 std::algorithms-C/C++问题

(Re)Using std::algorithms with non-standard containers((重新)在非标准容器中使用 std::algorithms)

本文介绍了(重新)在非标准容器中使用 std::algorithms的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有一个列"容器类型:

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_traits::difference_type
iterator_traits::value_type
iterator_traits::iterator_category
分别定义为迭代器的差异类型、值类型和迭代器类别.此外，类型
iterator_traits::reference
iterator_traits::pointer
应定义为迭代器的引用和指针类型，即对于迭代器对象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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！