std :: sortがベクトル内の値を交互に表示する理由

Question

以下のコードスニペットは、std :: sortがベクトルの値を交互に表示していることを示しています。

std::vector<int> a; 
std::vector<std::string> b; 
std::vector<std::pair<int&, std::string&>> p; 

a.push_back(1); 
a.push_back(3); 
a.push_back(2); 
b.push_back("hi 1"); 
b.push_back("hi 3"); 
b.push_back("hi 2"); 

p.push_back(std::pair<int&, std::string&>(a[0],b[0])); 
p.push_back(std::pair<int&, std::string&>(a[1],b[1])); 
p.push_back(std::pair<int&, std::string&>(a[2],b[2])); 

std::sort(p.begin(),p.end()); 

std::cout << a[0] << " " << a[1] << " " << a[2] << std::endl; 
std::cout << b[0] << " " << b[1] << " " << b[2] << std::endl; 

私はそれが

1 2 3 
hi 1 hi 2 hi 3 

を印刷するように期待していますが、代わりにそれは

1 3 3 
hi 1 hi 3 hi 3 

なぜを出力しますか？私のコンパイラはgcc 4.9.3です。

私は2つのベクトルを並べ替えようとしており、参照のペアのベクトルを使用することはhttps://stackoverflow.com/a/37929675/3667089で提案されています。

Answer 1

問題は挿入ソートの実装にあります。要素数が少ないので、ソートは挿入ソートを実行することを決定します。

問題のコード：

template<typename _RandomAccessIterator> 
    void 
    __unguarded_linear_insert(_RandomAccessIterator __last) 
    { 
     typename iterator_traits<_RandomAccessIterator>::value_type 
     __val = _GLIBCXX_MOVE(*__last); 
     _RandomAccessIterator __next = __last; 
     --__next; 
     while (__val < *__next) 
     { 
      *__last = _GLIBCXX_MOVE(*__next); <<< PROBLEMATIC Code 
      __last = __next; 
      --__next; 
     } 
     *__last = _GLIBCXX_MOVE(__val); 
    } 

今度はインデックス2とインデックス3の場合について、whileループの内側に進みます。 whileループに入る前に、__valの値は2 and hi 2です。しかし、最初にmoveを実行した後には、も3 and hi 3に変更され、その間にはlastが3 and hi 3に設定されていますが、これは間違っています。

UPDATE：このためのlibC++でのlibC++ コードは非常に簡単ですし、__sort3にちょうど3つの値を比較することに帰着します。 libC++はlibstd++と異なり、moveの代わりにswapを使用しているため、動作します。

moved要素に新しい値が割り当てられていると、データを上書きするため、参照型の移動がうまくいかないようです。 おそらく同じことがlibC++の結果になるでしょう.3つ以上の要素を使用する場合も、汎用の挿入ソートルーチンで moveを使用します。

UPDATE 2： はいつもノートラブルがあり、insertion_sortのために少なくともswapを使用しています++のlibc、それにより確認します。

参照がコンテナに格納するには良いものではありませんなぜ上の標準から引用すると： （セクション23.2）を

コンテナは、他のオブジェクトを格納するオブジェクトです。彼らは、コンストラクタ、 デストラクタ、挿入と削除操作を介して これらのオブジェクトの割り当てと割り当て解除を制御します。

とテーブルそれは、この要件がある下：

X :: VALUE_TYPEを - Tが必要：Tは、私はreference typeが破壊されるかどうかわからないですけど

破壊可能時間タイプをコンパイルしていますか否か。そうでない場合は、STLコンテナに参照を格納するためのコンパイル時エラーが発生するようにしてください。

Answer 2

おそらくlibstdC++のバグです。私は両方のlibstdcのアクションでソート++とのlibC++を参照して、「デバッグ」コンパレータを追加しました：

std::sort(p.begin(), p.end(), [&] (const auto& ap, const auto& bp) 
{ 
    std::cout << "Debug: " << ap.first << " " << bp.first << " | "; 
    for (auto e : a) 
     std::cout << e << " "; 
    std::cout << " | "; 
    for (auto e : b) 
     std::cout << e << " "; 
    std::cout << "\n"; 
    return ap.first < bp.first; 
}); 

をそして、これが出力されます：2要素は3によって上書きされます何らかの理由で

Debug: 1 1 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 3 1 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 3 1 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 2 1 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 2 3 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 3 1 | 1 3 3 | hi 1 hi 3 hi 3 
1 3 3 
hi 1 hi 3 hi 3 
-------------------------- 
Debug: 3 1 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 2 3 | 1 3 2 | hi 1 hi 3 hi 2 
Debug: 2 1 | 1 2 3 | hi 1 hi 2 hi 3 
1 2 3 
hi 1 hi 2 hi 3 

。

std::pair<int&, std::string&>がValueSwappableの定義を満たしていない可能性があります。つまり、ソート機能で要素の実際のスワップが発生すると、未定義の動作が発生しています。

Answer 3

std::pair<int&, std::string&>は交換できません。 std::swapはかかわらず、動作しているようですが、あなたはナイーブスワップで考えるならば、それはその後、pair0がpair1によって上書きされ参照

std::pair<int&, std::string&> pair0(a[0],b[0]); 
std::pair<int&, std::string&> pair1(a[1],b[1]); 

std::pair<int&, std::string&> tmp(pair0); 
pair0 = pair1; 
pair1 = tmp; 

では動作しません。

参考文献は、一般にSTLコンテナでは機能しません。