Согласно стандарту такой код запрещен: «The function main shall not be used within a program.» (3.6.1p3)
А программа, содержащая не-void функцию без единого return внутри, все равно обязана компилироваться (опять же согласно стандарту), но если в процессе выполнения программа доходит до конца тела такой функции (и эта функция не ::main), то это ведет к неопределенному поведению со всеми вытекающими.
то вы передаете в качестве аргумента указатель на функцию, поэтому вызовы этой функции не будут заинлайнены внутри std::sort(), в отличии от вашей функции сортировки. Лучше сделайте вот так:
std::sort(arr,arr+len,[](int i, int j){ return (i^5)<(j^5); });
Но даже несмотря на передачу по указателю, на gcc 4.9.0 и 10 миллионах (100 на онлайн-компиляторе не выполняется, чуть попозже дома погляжу) std::sort() чуть быстрее, а с заменой на функциональный объект становится быстрее почти в два раза coliru.stacked-crooked.com/a/9dbe1c48ab675c7a. Это так, первый взгляд, нету много времени разбираться пока.
Ваша упрощение не отражает того факта, что это лишь оценка сверху, причем с точностью до константы, а не точное значение числа операций. Например, функция 4n принадлежит как к классу (множеству функций) O(n), так и к классам O(n log n), O(n2) и так далее. Не обижайтесь, но по вашим постам складывается ощущение, что вы сами не понимаете (или понимаете очень поверхности), что это понятие значит.
Да, qsort без стека, реализованный по принципу описанному в начале статьи (или сходному с ним), но без всяких там выборов медианного элемента, выбираем случайный элемент в качестве разделителя. Метод разделения, когда идем не с двух сторон указателями, а только с начала в конец довольно известный, называется Lomuto partition. Оверхеда у такого qsort по сравнению с классическим по сути только дополнительный лишний проход по каждому сортируемому отрезку (чтобы определить его длину + на нем же сразу будем выбирать разделитель). Это должно давать неплохую скорость на практике, во всяком случае гораздо быстрее и inplace merge sort, и конечного алгоритма в статье.
Это потому что std::array является аггрегатом, у него вообще нету пользовательских конструкторов (в том числе и конструктора, принимающего std::initializer_list). Этот код аналогичен такому (кстати, в вышеприведенном коде не указана длина массивов, так что второй ok на самом деле не ok):
Раз std::array является аггрегатом, то при инициализации с помощью фигурных скобочек происходит aggregate initialization. А она смотрит, что внутри две пары фигурных скобок, а член данных у аггрегата только один (массив data), и поэтому выдает ошибку компиляции.
Если я верно вас понял, то да, но ничего особо сложного. Если не сильно заморачиваться по поводу эффективности, то можно для обоих случаев использовать одну версию процедуры слияния, которая принимает итераторы начала сливаемых кусков и их длины, а также итератор по которому писать ответ, а как они там между собой расположены это не её дело. Или всегда использовать первый вариант, а перед слиянием двух соседних кусков в merge sort вначале обменивать второй кусок с буфером местами, как при слиянии с N/2 дополнительной памяти (но опять же не самый эффективный код).
К слову, мне кажется, в качестве первого шага выгоднее сортировать N/2, а не 2N/3 элементов, потому что сортировка слиянием, когда у нас есть N дополнительной памяти, а не N/2, более эффективна за счет того, что мы можем использовать один кусок в качестве источника, а во второй писать ответ, а на следующем шаге просто делать наоборот.
Не очень вас понял, вы точно верно прочитали, что я написал? Я имел ввиду, что если бы требовалась производительность O(n log n) лишь в среднем, а не в худшем случае, то можно было бы написать специальную версию qsort, которая показывала бы неплохое время на практике.
Вообще, из всех STL-контейнеров помимо вектора указатели на элементы инвалидирует только std::deque, и то лишь при добавлении не в начало или конец, все остальные контейнеры их сохраняют.
Не компилируется, потому что std::sort() хочет случайный доступ к элементам сортируемой структуры (более строго: итератор должен удовлетворять требованиям random access iterator).
Плохое требование тут имхо — это O(n log n) в худшем случае, без него вполне реально написать qsort за O(1) дополнительной памяти с выбором рандомного элемента в качестве pivot'а, который будет неплохое время на практике показывать. Можно впрочем сделать как в introsort и запускать предложенный алгоритм или тот же inplace merge sort (любой алгоритм, работающий за O(n log n) в худшем случае), если у qsort дела плохо идут.
Это извращенное ограничение, если честно, т. к. инвалидируются указатели на элементы списка + требуется использовать потенциально дорогой обмен элементов вместо гарантированно дешевых манипуляций с указателями. Тогда, как выше написали, помогает inplace merge sort (нестабильная версия).
Да вроде нету там никаких проблем. Пусть наш массив-список выглядит так: вначале 2К неотсортированных элементов, затем отсортированный кусок. Тогда сортируем первые К элементов слиянием, используя вторые К как буфер, а потом сливаем с отсортированным куском в конце, начиная записывать результат с К+1 элемента. Тогда неотсортированная часть сама собой переедет на место первых К элементов, и тем самым мы свели задачу к исходной, только с К вместо 2К. Со случаем, когда длина неотсортированной части нечетна, надо просто аккуратно побороться, можно, например, банально вставить один элемент в отсортированный кусок и свести её к четной.
Возможно я не до конца понял условия, но сортировать списки за O(n log n) времени и O(1) памяти умеет обычная сортировка слиянием. Для слияния двух упорядоченных списков в один в отличии от массивов дополнительная память не нужна.
Есть синтаксис захвата по ссылке, но только по lvalue:
[&ref = ...]
Невозможность захвата по rvalue ссылке, на мой взгляд, сделана специально, потому что я практически уверен, что такая ссылка не продляет время жизни временного объекта (по аналогии с ссылкой-членом класса). По крайней мере результат выполнения такого кода на clang (у gcc 4.9.0 какой-то баг с захватом по константной ссылке, он не хочет даже const lvalue по ней захватить):
int main()
{
struct T {
T() { cout << "Begin lifetime\n"; }
~T() { cout << "End lifetime\n"; };
};
using CT = const T;
auto f = [&x = CT{}, y = CT{}](){};
cout << "----\n";
}
показывает, что временный объект даже до конца выражения не доживает.
Возможно стоило захватывать элемент по универсальной ссылке и использовать emplace_back, чтобы избежать лишнего вызова конструктора копирования, но не уверен, т.к. немножко изменится семантика.
mainshall not be used within a program.» (3.6.1p3)А программа, содержащая не-void функцию без единого
returnвнутри, все равно обязана компилироваться (опять же согласно стандарту), но если в процессе выполнения программа доходит до конца тела такой функции (и эта функция не::main), то это ведет к неопределенному поведению со всеми вытекающими.то вы передаете в качестве аргумента указатель на функцию, поэтому вызовы этой функции не будут заинлайнены внутри
std::sort(), в отличии от вашей функции сортировки. Лучше сделайте вот так:Но даже несмотря на передачу по указателю, на gcc 4.9.0 и 10 миллионах (100 на онлайн-компиляторе не выполняется, чуть попозже дома погляжу)
std::sort()чуть быстрее, а с заменой на функциональный объект становится быстрее почти в два раза coliru.stacked-crooked.com/a/9dbe1c48ab675c7a. Это так, первый взгляд, нету много времени разбираться пока.std::arrayявляется аггрегатом, у него вообще нету пользовательских конструкторов (в том числе и конструктора, принимающегоstd::initializer_list). Этот код аналогичен такому (кстати, в вышеприведенном коде не указана длина массивов, так что второй ok на самом деле не ok):Раз
std::arrayявляется аггрегатом, то при инициализации с помощью фигурных скобочек происходит aggregate initialization. А она смотрит, что внутри две пары фигурных скобок, а член данных у аггрегата только один (массивdata), и поэтому выдает ошибку компиляции.К слову, мне кажется, в качестве первого шага выгоднее сортировать N/2, а не 2N/3 элементов, потому что сортировка слиянием, когда у нас есть N дополнительной памяти, а не N/2, более эффективна за счет того, что мы можем использовать один кусок в качестве источника, а во второй писать ответ, а на следующем шаге просто делать наоборот.
std::deque, и то лишь при добавлении не в начало или конец, все остальные контейнеры их сохраняют.std::sort()хочет случайный доступ к элементам сортируемой структуры (более строго: итератор должен удовлетворять требованиям random access iterator).А ответ куда писать тогда?
Невозможность захвата по rvalue ссылке, на мой взгляд, сделана специально, потому что я практически уверен, что такая ссылка не продляет время жизни временного объекта (по аналогии с ссылкой-членом класса). По крайней мере результат выполнения такого кода на clang (у gcc 4.9.0 какой-то баг с захватом по константной ссылке, он не хочет даже const lvalue по ней захватить):
показывает, что временный объект даже до конца выражения не доживает.
emplace_back, чтобы избежать лишнего вызова конструктора копирования, но не уверен, т.к. немножко изменится семантика.