23

次のコードを検討してください。

#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double  a;
    double* b;
    bool operator<(const A& rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& rhs)
{
    std::cerr << "My swap.\n";
    std::swap(lhs.a, rhs.a);
    std::swap(lhs.b, rhs.b);
}

}

int main()
{
    const int n = 20;
    std::vector<my_space::A> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[i].a = -i;
    }

    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";
    std::sort(vec.begin(), vec.end());
    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";
}

を使用するn=20と、カスタム スワップ関数が呼び出され、配列がソートされます。しかし、 を使用するn=4と、配列は正しくソートされますが、カスタム スワップ関数は呼び出されません。何故ですか？オブジェクトをコピーするのに非常にコストがかかる場合はどうすればよいですか?

このテストでは、gcc 4.5.3 を使用しました。

4

3 に答える 3

25

小さい範囲の場合std::sort、GCC の stdlibc++ (およびその他の標準ライブラリの実装) の実装は、パフォーマンス上の理由から挿入ソートを繰り返します (小さい範囲でのクイックソート / イントロソートよりも高速です)。

GCC の挿入並べ替えの実装は、順番にスワップしませんstd::swap 。代わりに、個別にスワップするのではなく、値の範囲全体を一度に移動するため、パフォーマンスが節約される可能性があります。関連する部分はここにあります（bits/stl_algo.h:2187、GCC 4.7.2）：

typename iterator_traits<_RandomAccessIterator>::value_type
  __val = _GLIBCXX_MOVE(*__i);
_GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
*__first = _GLIBCXX_MOVE(__val);

_GLIBCXX_MOVEstd::moveはC++11 からのものと同じであり、_GLIBCXX_MOVE_BACKWARD3です– ただし、これはが定義されstd::move_backwardている場合にのみ当てはまります。__GXX_EXPERIMENTAL_CXX0X__そうでない場合、これらの操作は移動ではなくコピーに頼ります。

これが行うことは、現在の位置 ( __i) の値を一時ストレージに移動し、以前のすべての値を__firstから__i1 つ上に移動してから、一時的な値を に再挿入すること__firstです。したがって、これはn個の値を一時的な場所に移動する代わりに、1 回の操作で n 個のスワップを実行します。

  first           i
+---+---+---+---+---+---+
| b | c | d | e | a | f |
+---+---+---+---+---+---+
                  |
  <---------------+


  first           i
+---+---+---+---+---+---+
| --> b-> c-> d-> e-> f |
+---+---+---+---+---+---+


  first           i
+---+---+---+---+---+---+
| a | b | c | d | e | f |
+---+---+---+---+---+---+
  ^
于 2013-01-08T10:54:10.397 に答える
4

型によっては、スワッピングは移動代入よりもコストがかかる場合があります (C++98 では単純な代入)。標準ライブラリには、これらのケースを検出する方法がありません。少なくとも C++11 では解決策は明らかです。スワップを実装するすべてのクラスに移動代入演算子を実装します。

于 2013-01-08T10:58:13.837 に答える
1

コードをより冗長になるように変更しました。20個の要素の並べ替えには多くのスワップが使用され、割り当ての終了コピーが使用されます。4つの要素の並べ替えでは、割り当てとコピーのみが使用されます。スペックはわかりませんが、何か続くかもしれません。

#include <algorithm>
#include <iostream>
#include <vector>

namespace my_space
{

struct A
{
    double  a;
    double* b;
    A()
        : a(0)
        , b(NULL)
    { }
    A(const A &rhs)
        : a(rhs.a)
        , b(rhs.b)
    {
        std::cerr << "copy" << std::endl;
    }
    A& operator=(A const &rhs)
    {
        if(this==&rhs)
                return *this;
        a = rhs.a;
        b = rhs.b;
        std::cerr << "=" << std::endl;
        return *this;
    }
    bool operator<(const A& rhs) const
    {
        return this->a < rhs.a;
    }
};

void swap(A& lhs, A& rhs)
{
    std::cerr << "My swap.\n";
    std::swap(lhs.a, rhs.a);
    std::swap(lhs.b, rhs.b);
}

} // namespace my_space

int main()
{
    const int n = 20;

        std::cerr << "=== TEST CASE: n = " << n << std::endl;
    std::cerr << "=== FILL ===" << std::endl;
    std::vector<my_space::A> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[i].a = -i;
    }

    std::cerr << "=== PRINT ===" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";

    std::cerr << "=== SORT ===" << std::endl;
    std::sort(vec.begin(), vec.end());

    std::cerr << "=== PRINT ===" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cerr << vec[i].a << " ";
    }
    std::cerr << "\n";
}

出力

=== TEST CASE: n = 4
=== FILL ===
copy
copy
copy
copy
=== PRINT ===
0 -1 -2 -3
=== SORT ===
copy
=
=
copy
=
=
=
copy
=
=
=
=
=== PRINT ===
-3 -2 -1 0

と

=== TEST CASE: n = 20
=== FILL ===
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
copy
=== PRINT ===
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19
=== SORT ===
copy
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
My swap.
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
copy
=
copy
=
copy
=
copy
=
copy
=
=== PRINT ===
-19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0
于 2013-01-08T10:35:26.393 に答える