c++ - 非標準コンテナで std::algorithms を (再) 使用する

Question

「列」コンテナタイプがあります：

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(注: 並べ替えの場合、ラムダなどのユーザー定義ファンクタによって比較が提供されます)。

特に、反復子は次のようなインターフェースを提供する必要があります

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がスワップ可能ではなくデフォルトで構築可能である必要がある理由は、私の理解を超えています)。

注 2:次のことはできません。

struct MyType {
  double a;
  string b;
  int c;
};

std::vector<MyType> v;

を使用しますstd::algorithm。

動機:パフォーマンス。キャッシュラインは通常 64 バイト、つまり 8 つの double です。この単純な構造体で double を反復処理すると、キャッシュラインが文字列と int で汚染されます。それ以外の場合は、キャッシュ ラインごとに 1 つの二重転送しか取得できない場合があります。つまり、使用可能なメモリ帯域幅の 1/8 を使用することになります。数 Gb の double を反復処理する必要がある場合、この単純な決定により、アプリケーションのパフォーマンスが 6 ～ 7 倍向上します。いいえ、私はそれをあきらめることはできません。

おまけ:答えはできるだけ一般的なものにする必要があります。構造体にメンバーを追加/削除するように、コンテナ型にフィールドを追加/削除することを考えてください。新しいメンバーを追加するたびに多くのコードを変更する必要はありません。

Answer 1

このようなものが標準に準拠している可能性があると思います。いくつかの 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)。反復は、3 つの反復子 (各 に 1 つvector) を維持および更新することによって行われます。ただし、それが最もパフォーマンスの高いオプションかどうかはわかりません。

仕組み:std::iterator_traitsイテレータに関連付けられたいくつかの型を定義します: [iterator.traits]/1

iterator_traits<Iterator>::difference_type
iterator_traits<Iterator>::value_type
iterator_traits<Iterator>::iterator_category
それぞれ、反復子の差分型、値型、および反復子カテゴリとして定義されます。さらに、型は反復子の参照型およびポインター型として定義されます。つまり、反復子オブジェクト a の場合、それぞれおよび
iterator_traits<Iterator>::reference
iterator_traits<Iterator>::pointer
の型と同じ型です。*aa->

all_referenceしたがって、 3 つの参照をreference型として保持する struct ( ) を導入できます。この型は の戻り値で*a、aはイテレータ型です (修飾されている可能性がありconstます)。value_typeなどの一部の標準ライブラリ アルゴリズムでは、 (ローカル変数にコピーまたは移動することによって)sortの値を一時的に格納するローカル変数を作成する必要があるため、異なる必要があります。*aこの場合、all_copyこの機能を提供します。

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。何らかの理由で、3 つすべてを提供する必要があります。

    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,

Answer 2

パフォーマンスが本当に心配で、コンテナーを で並べ替えたい場合std::sortは、カスタム比較オブジェクトを提供できるオーバーロードを使用します。

template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

.. インデックスの配列をコンテナーに並べ替えます。方法は次のとおりです。

コンテナーには次のメンバーが必要です。

struct MyColumnType { 
    ...

    int size() const;

    // swaps columns
    void swap(int l, int r);

    // returns true if column l is less than column r
    bool less(int l, int r) const;

    ...
};

次に、次の比較オブジェクトを定義します。

struct MyColumnTypeLess
{
    const MyColumnType* container;
    MyColumnTypeLess(const MyColumnType* container)
        : container(container)
    {
    }
    bool operator()(int l, int r) const
    {
        return container->less(l, r);
    }
};

それを使用して、インデックスの配列をソートします。

void sortMyColumnType(MyColumnType& container)
{
    std::vector<int> indices;
    indices.reserve(container.size());
    // fill with [0, n)
    for(int i = 0; i != container.size(); ++i)
    {
        indices.push_back(i);
    }
    // sort the indices
    std::sort(indices.begin(), indices.end(), MyColumnTypeLess(&container));
}

コンテナーの 'less' メンバーは、並べ替える順序を制御します。

bool MyColumnType::less(int l, int r) const
{
    // sort first by a, then b, then c
    return a[l] != a[r] ? a[l] < a[r]
        : b[l] != b[r] ? b[l] < b[r]
        : c[l] < c[r];
}

ソートされたインデックスの配列は、さらなるアルゴリズムで使用できます。必要になるまで、実際のデータをコピーすることを避けることができます。

RandomAccessIterator で動作するすべてのstdアルゴリズムには、カスタム比較オブジェクトを指定できるオーバーロードがあるため、この手法でも使用できます。