1

SGI、cplusplus.com、および私が入手した他のすべてのソースによると、std :: listのsort（）メンバー関数はイテレーターを無効にすべきではありません。ただし、このコード（c ++ 11）を実行すると、そうではないようです。

#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include "print.hpp"
unsigned int seed = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine generator(seed);
std::uniform_int_distribution<unsigned int> distribution(1, 1000000000);
auto rng = std::bind(distribution, generator);
// C++11 RNG stuff. Basically, rng() now gives some unsigned int [1, 1000000000]

int main() {
    unsigned int values(0);
    std::cin >> values;           // Determine the size of the list
    std::list<unsigned int> c;
    for (unsigned int n(0); n < values; ++n) {
        c.push_front(rng());
    }
    auto c0(c);
    auto it(c.begin()), it0(c0.begin());
    for (unsigned int n(0); n < 7; ++n) {
        ++it;     // Offset these iterators so I can print 7 values
        ++it0;
    }
    std::cout << "With seed: " << seed << "\n";
    std::cout << "Unsorted list: \n";
    print(c.begin(), c.end()) << "\n";
    print(c.begin(), it) << "\n\n";
    auto t0 = std::chrono::steady_clock::now();
    c0.sort();
    auto d0 = std::chrono::steady_clock::now() - t0;
    std::cout << "Sorted list: \n";
    print(c0.begin(), c0.end()) << "\n";
    print(c0.begin(), it0) << "\n";  // My own print function, given further below
    std::cout << "Seconds: " << std::chrono::duration<double>(d0).count() << std::endl;
    return 0;
}

print.hpp：

#include <iostream>

template<class InputIterator>
std::ostream& print(InputIterator begin, const InputIterator& end, 
                    std::ostream& out = std::cout) {
    bool first(true);
    out << "{";
    for (; begin != end; ++begin) {
        if (first) {
            out << (*begin);
            first = false;
        } else {
            out << ", " << (*begin);
        }
    }
    out << "}";
    return out;
}

サンプル入力/出力：

11
With seed: 3454921017
Unsorted list: 
{625860546, 672762972, 319409064, 8707580, 317964049, 762505303, 756270868, 249266563, 224065083, 843444019, 523600743}
{625860546, 672762972, 319409064, 8707580, 317964049, 762505303, 756270868}

Sorted list: 
{8707580, 224065083, 249266563, 317964049, 319409064, 523600743, 625860546, 672762972, 756270868, 762505303, 843444019}
{8707580, 224065083}
Seconds: 2.7e-05

印刷を除いて、すべてが期待どおりに機能します。7つの要素を表示することになっていますが、「値」が7を超える場合、実際の数はかなり無計画です。何も表示されない場合もあれば、1が表示される場合もあれば、10が表示される場合もあります。私のコードに明らかに何か問題がありますか、それともg++のstd:: list（およびstd :: forward_list）が標準に準拠していないことを示していますか？

前もって感謝します！

4

1 に答える 1

11

イテレータは引き続き有効であり、並べ替えられたリストの同じ要素を参照します。

だから私はあなたのコードがあなたが思っていることをしていないと思います。リストを最初から、リストがソートされた後の7番目の要素の最後まで印刷します。したがって、出力される要素の数は、もちろんリスト内の値によって異なります。

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

#include <list>
#include <iostream>

int main() {
    std::list<int> l;
    l.push_back(1);
    l.push_back(0);
    std::cout << (void*)(&*l.begin()) << "\n";
    l.sort();
    std::cout << (void*)(&*l.begin()) << "\n";
}

印刷された2つのアドレスは異なり、（とは異なりstd::sort）std::list::sortが、要素に新しい値を割り当てるのではなく、要素間のリンクを変更することによってソートされたことを示しています。

私はいつもこれが義務付けられていると思っていました（同様にreverse()）。私は実際にそう言う明示的なテキストを見つけることができませんが、の説明を見て、マージソートがリストとうまく機能するために存在するmerge理由を考えると、それは「明らかに」意図されていると思います。「xの移動された要素へのポインタと参照は、これらの同じ要素を参照しますが、* thisのメンバーとして参照されます」（23.3.5.5./23）、および「リストは高速であるため、リストの途中から挿入および消去するために、特定の操作がそれらのために特別に提供されています」（23.3.5.5/1）。list::sortmergemergesort

于 2012-11-12T17:10:26.843 に答える