Мне любопытно, в первую очередь, почему std::list и std::forward_list включают функции сортировки в качестве функций-членов, в отличие от любого другого контейнера стандартной библиотеки. Но более интересным для меня является то, что CPPReference и CPlusPlus утверждают, что эта сортировка выполняется в O (n log n) времени.
Я даже не могу представить, как можно сортировать контейнер без произвольного доступа к элементам. Поэтому я собрал тест, используя forward_list, чтобы сделать его как можно более трудным.
#include <chrono>
#include <cstdint>
#include <deque>
#include <forward_list>
#include <iostream>
#include <random>
using std::endl;
using namespace std::chrono;
typedef nanoseconds::rep length_of_time;
constexpr int TEST_SIZE = 25000;
class Stopwatch
{
public:
void start_timing();
void end_timing();
length_of_time get_elapsed_time() const;
private:
time_point<high_resolution_clock> start;
time_point<high_resolution_clock> end;
length_of_time elapsed_time = 0;
};
void Stopwatch::start_timing()
{
start = high_resolution_clock::now();
}
void Stopwatch::end_timing()
{
end = high_resolution_clock::now();
auto elapsed = end - start;
auto elapsed_nanoseconds = duration_cast<nanoseconds>(elapsed);
elapsed_time = elapsed_nanoseconds.count();
}
length_of_time Stopwatch::get_elapsed_time() const
{
return elapsed_time;
}
std::mt19937_64 make_random_generator()
{
using namespace std::chrono;
auto random_generator = std::mt19937_64();
auto current_time = high_resolution_clock::now();
auto nanos = duration_cast<nanoseconds>(
current_time.time_since_epoch()).count();
random_generator.seed(nanos);
return random_generator;
}
int main()
{
Stopwatch timer;
std::deque<length_of_time> times;
auto generator = make_random_generator();
for (int i = 1; i <= TEST_SIZE; i++) {
std::forward_list<uint64_t> container;
for (int j = 1; j <= i; j++) {
container.push_front(generator());
}
timer.start_timing();
container.sort();
timer.end_timing();
times.push_back(timer.get_elapsed_time());
container.clear();
}
for (const auto& time: times) {
std::cout << time << endl;
}
}
Цифры этой программы выводят следующий график:
Что действительно похоже на рост O (n log n) (хотя шипы на каждой трети пути интересны). Как библиотека это делает? Возможно, скопируйте в контейнер, который поддерживает сортировку, сортировку и копирование?
