4

次の2つのコードスニペットの違いは何ですか。

vector<int> a;
// initialization code
sort( a.rbegin(), a.rend() );

と

vector<int> a;
// same initialization as above
sort(a.begin(), a.end(), comp);

ここで、compは以下に示すブール関数です。

bool comp( int i, int j)
{
    return i>j;
}

説明のために、次のコードはWAを提供し、このコードはSPOJ問題XMAXのACを提供します。ACとWAの唯一の違いは、使用されるsort（）のバージョンです。

4

6 に答える 6

7

は安定したアルゴリズムではないため、 2つの関数呼び出しは同じ答えを返しません。つまり、相対的な順序で同一の要素を保持しません。の要素が最初の要素でソートされている例を以下に示します。逆比較機能を使用して逆順で並べ替えたり並べ替えたりしても、同じシーケンスは生成されません。で同じことを行うと、同じ結果が得られます。std::sortstd::pair<int, int>std::stable_sort

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

int main()
{
    typedef std::pair<int, int> Element;
    std::vector<Element> v;

    v.push_back( Element(1,1) );
    v.push_back( Element(-1,1) );
    v.push_back( Element(1,2) );
    v.push_back( Element(-1,2) );
    v.push_back( Element(1,3) );
    v.push_back( Element(-1,3) );
    v.push_back( Element(1,4) );
    v.push_back( Element(-1,4) );
    v.push_back( Element(1,5) );
    v.push_back( Element(-1,5) );
    v.push_back( Element(1,6) );
    v.push_back( Element(-1,6) );
    v.push_back( Element(1,16) );
    v.push_back( Element(-1,16) );
    v.push_back( Element(1,22) );
    v.push_back( Element(-1,22) );
    v.push_back( Element(1,33) );
    v.push_back( Element(-1,33) );
    v.push_back( Element(1,44) );
    v.push_back( Element(-1,44) );
    v.push_back( Element(1,55) );
    v.push_back( Element(-1,55) );
    v.push_back( Element(1,66) );
    v.push_back( Element(-1,66) );

    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << "(" << it->first << "," << it->second << ")" << " ";
    }
    std::cout << "\n";

    auto w1 = v;
    std::sort(w1.begin(), w1.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w2 = v;
    std::sort(w2.rbegin(), w2.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w1.begin(), w1.end(), w2.begin()) << "\n";

    auto w3 = v;
    std::stable_sort(w3.begin(), w3.end(), [](Element const& e1, Element const& e2){ 
       return e1.first < e2. first;
    });
    auto w4 = v;
    std::stable_sort(w4.rbegin(), w4.rend(), [](Element const& e1, Element const& e2) {
       return e1.first > e2.first;
    });
    std::cout << std::boolalpha << std::equal(w3.begin(), w3.end(), w4.begin()) << "\n";

}

LiveWorkSpaceでの出力

于 2013-01-18T19:31:23.873 に答える
3

逆イテレータは、通常のイテレータの逆方向に単純に反復します。

したがって、両方のスニペットは、[最初、最後]の範囲内のすべてを昇順で並べ替えます。違いは、最初は比較に<演算子を使用し、2番目は指​​定された関数を使用することです。

詳細には、最初は実際には昇順ではない順序で並べ替えていますが、比較も逆にするため、再び逆になり、効果が無効になります。

注：互いに同等に比較される要素は、元の相対的な順序を維持することが保証されていません。

有用な参考文献 ： std::sort、、、、、std::vector::beginstd::vector::endstd::vector::rbeginstd::vector::rend

于 2013-01-18T19:17:22.373 に答える
1

名前が示すように、逆イテレータは逆の順序でコレクションにアクセスします。STLsort()アルゴリズムにからまでの範囲をソートするa.begin()ように要求するa.end()と、結果の値は、それらのイテレーターによって定義された順序で、からa.begin()までの範囲に配置されます。a.end()

a.rbegin()では、からまでの範囲を並べ替えるように依頼するとどうなりますa.rend()か？結果は、これらのイテレータによって定義された順序で、a.rbegin()からの範囲に配置されます。a.rend()

于 2013-01-18T19:07:00.750 に答える
1

イテレータは最初から最後まで実行され、逆イテレータは最後から最初まで実行されます。したがってsort(a.begin(), a.end())、要素を[first、last）の範囲に順番に配置します。sort(a.rbegin(), a.rend())[last、first）の範囲の要素を順番に配置し、最初のバージョンとは逆の順序を生成します。

于 2013-01-18T19:08:24.853 に答える
0

rbeginリストの最後を指すイテレータを提供し、前方に移動するように要求すると後方に移動します。同様に、 rendリストの先頭へのイテレータを提供します。

sort(a.begin(), a.end(), comp);

ここでの3番目のパラメーターは、独自のソート順を定義するために使用されます。指定しない場合は、そのオブジェクトのデフォルトが使用されます。

于 2013-01-18T19:07:04.727 に答える
0

それらは両方とも同じことを達成します。最初のバージョンでは、イテレータの順序を逆にして、高から低にソートします。2番目のバージョンでは、比較の意味を逆にして、高から低への並べ替えも行います。

于 2013-01-18T19:07:31.603 に答える