6

std::sortを使用して要素を交換します。これによりstd::swap、コピー コンストラクターと代入演算子が使用され、値を交換するときに正しいセマンティクスが得られることが保証されます。

qsortスワップする型に関連付けられたセマンティクスを無視して、要素の基になるビットを単純にスワップすることによって要素をスワップします。

qsortソートしている型のセマンティクスを知らなくても、自明でない型では非常にうまく機能します。私が間違っていなければ、POD タイプではないにもかかわらず、すべての標準コンテナーで動作します。

qsort型で正しく動作するための前提条件Tは、T/自明に可動/であることだと思います。頭のてっぺんから離れて、自明に移動できない唯一の型は、内部ポインターを持つ型です。例えば:

struct NotTriviallyMovable
{
    NotTriviallyMovable() : m_someElement(&m_array[5]) {}

    int m_array[10];
    int* m_someElement;
};

の配列をソートするとNotTriviallyMovablem_someElements は間違った要素を指すことになります。

私の質問は次のとおりです。他の種類のタイプでは機能しませんqsortか?

4

4 に答える 4

5

POD タイプ以外のタイプは、 では使用できませんqsort()PODqsort()の定義が変更されるため、C++0x を考慮すると、使用できる型が増える可能性があります。非 POD タイプを使用する場合は、UB の国にいることになり、デーモンが鼻から飛び出します。qsort()

于 2011-05-30T10:19:21.833 に答える
2

これは、「関連する」オブジェクトへのポインターを持つ型でも機能しません。このようなポインターには、「内部」ポインターに関連する多くの問題がありますが、「関連する」オブジェクトが何であるかを正確に証明することははるかに困難です。

特定の種類の「関連」オブジェクトは、バックポインターを持つオブジェクトです。オブジェクト A と B がビットスワップされ、A と C が互いに指している場合、その後、B は C を指しますが、C は A を指します。

于 2011-05-30T11:11:19.507 に答える
1

「私が間違っていなければ、すべての標準コンテナで動作します」

質問全体は、どの実装で?標準に合わせてコーディングしますか、それとも現在目の前にあるコンパイラの実装の詳細に合わせてコーディングしますか? 後者の場合、すべてのテストに合格すれば、うまくいくと思います。

C++ プログラミング言語について質問している場合はqsort、POD 型に対してのみ機能する必要があります。特定の実装について質問している場合は、どの実装ですか? すべての実装について質問している場合は、チャンスを逃したことになります。その種のストロー投票に最適な場所は C++0x ワーキング グループ ミーティングでした。積極的に維持されている C++ 実装。

std::list価値のあるものとして、リストノードがリストオブジェクト自体に埋め込まれ、ヘッド/テールセンチネルとして使用される実装を非常に簡単に想像できます。nullポインターをヘッド/テールセンチネルとして使用することも一般的であるため、実際にどの実装(ある場合)がそれを行うかはわかりませんが、それぞれにダミーノードを持つ二重リンクリストを実装することには確かにいくつかの利点があります終わり。そのような のインスタンスはstd::list、もちろん自明に移動することはできません。最初と最後の要素のノードがセンチネルを指していないからです。そのswap実装と (C++0x では) その移動コンストラクターは、最初と最後のノードを更新することでこれを説明します。

コンパイラが次のリリースで のこの実装に切り替えるのを止めるものは何もありませんがstd::list、そうするとバイナリ互換性が損なわれるため、ほとんどのコンパイラがどのように管理されているかを考えると、メジャー リリースにする必要があります。

同様に、map/set/multimap/multiset カルテットは、それらの親を指すノードを持つことができます。コンテナーのデバッグ イテレーターには、コンテナーへのポインターが含まれている可能性があります。必要なことを行うには、(少なくとも) 実装のどの部分でもコンテナーへのポインターの存在を除外する必要があります。標準を持つことの要点は、準拠するすべての実装について声明を出すことです。そのため、標準から結論を導き出していなければ、今日の声明が真実であっても、明日は真実でなくなる可能性があります。

于 2011-05-30T11:01:32.877 に答える
1

あなたは完全に間違っています。動作する非 POD タイプqsortは完全であり、完全な運です。神々に処女の血を犠牲にして最初に少し踊った場合、それがたまたまあなたのプラットフォームで青月のコンパイラでうまくいくからといって、それが実際にうまくいくとは限りません。

ああ、これは自明ではない可動型のための別のもので、そのインスタンスは外部から観察されます。移動しますが、スワップまたはコピー構築関数を呼び出していないため、オブザーバーに通知しません。

于 2011-05-30T10:26:45.530 に答える