Комментарии 24
Если насчет log2p1 полностью согласен про неочевидность, то вот partial_sort_copy мне кажется довольно просто и понятно, понятнее прочих названий. Но это конечно только мое мнение.
А почему не тот же partial_sort(...), но с дополнительным аргументом, куда копировать результат. Там конечно уже совсем страшный список аргументов получается, хотелось бы (мне) видеть что-то типа:
partial_sort(src_begin, src_end, copy_to(dest_begin, dest_end));Ваш вариант тоже вполне хороший, как по мне. Мне не понравились предложенные варианты автора: recycle_storage() — как-то не так очевидно, а top_n_sorted() — исключительный узкий случай, у partial_sort() или partial_sort_copy() — больше вариантов применения, кроме нескольких наибольших элементов. Как минимум, еще варианты наименьшие элементы, или вообще где-то из середины по какому-то своему хитрому условию.
т.е. сначала что-то где-то отсортировать, а потом применить копирование? боюсь, это будет уже нет так рационально…
copy_to() это же не сама функция копирования. Двух аргументов (first, last) ей было бы явно недостаточно, разве что если вот так как-нибудь (как по мне красивее, но для оптимизации с ходу не вижу вариантов):
partial_sort(src_begin, src_end).copy_to(dest_begin, dest_end);
уже не переименуют — под этим названием она вошла в стандарт ещё в 1998
можно добавить название, не обязательно переименовывать
> Небольшое отступление: в С++ арифметика указателей работает только с указателями на элементы массива.
Серьёзно? С какого момента это появилось в С++ и зачем?
Consider the following natural C program:
struct X { int a, b; };
X *make_x() {
X *p = (X*)malloc(sizeof(struct X));
p->a = 1;
p->b = 2;
return p;
}
When compiled with a C++ compiler, this code has undefined behavior, because p->a attempts to write to an int subobject of an X object, and this program never created either an X object nor an int subobject.
Серьёзно? С какого момента это появилось в С++ и зачем?
Что именно "это"? Создание объектов типа struct подразумевает вызов конструкторов (которые есть, даже если их "не видно"), чего malloc не делает, поэтому в C++ коде нужно пользоваться new. Можно вызывать и malloc, но тогда нужно будет все равно создать в этом месте объект через placement new. Для многих это является сюрпризом, но C и C++ — разные языки, хотя и с похожим синтаксисом и высокой степенью совместимости.
Создание объектов типа struct подразумевает вызов конструкторов
На сколько я помню это только для неPOD типов.
в С++ арифметика указателей работает только с указателями на элементы массива.это, как и пример из статьи, вообще как-то дико звучит. С какой стати?
PS.
Что именно «это»?Давайте тон попроще а? В моем сообщении вполне выделены два пункта, не надо тут делать недовольное лицо.
На сколько я помню это только для неPOD типов.
en.cppreference.com/w/cpp/language/object
Objects are created by definitions, new-expressions, throw-expressions, when changing the active member of a union, and where temporary objects are required.
malloc не делает ничего из этого, а никакого исключения для POD типов не предусмотрено.
это, как и пример из статьи, вообще как-то дико звучит. С какой стати?
С какой стати что именно? Что конкретно вы хотите делать с помощью арифметики указателей?
P.S. На тему арифметических операций с указателями, выдержка из стандарта C++11, параграф 5.7:
When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.
То же самое потом дальше идет про вычитание. То есть других валидных арифметических операций с указателями, кроме операций с указателями на элементы массива, по сути не предусмотрено, притом требуется, чтобы результат такой операции смотрел либо на какой-либо элемент массива, либо на (несуществующий) элемент, следующий за последним элементом массива.
PS. В общем повода дле беспокойства нет как я понял.
Смотря что вы пишете и как.
Давайте тон попроще а?
А давайте без давайте. Я и так по сути роюсь в референсах и стандартах за вас, а вы только задаете вопросы в стиле «что это за фигня, с какой стати». Недовольное лицо тут пока только у вас.
А давайте без давайте. Я и так по сути роюсь в референсах и стандартах за вас, а вы только задаете вопросы в стиле «что это за фигня, с какой стати». Недовольное лицо тут пока только у вас.
Могли бы себя и не утруждать.
От ваших референсов если честно вообще толку ноль, больше похоже на «на утрись, в стандарте так написано». Сами же вы похоже не понимаете зачем это там написано. Так что пожалуйста оставьте свой аггресивный тон себе, и возможно вашим коллегам, нет никакого сымысла делать это в публичном месте.
А я уже и без вашей помощи нашел, что существует en.cppreference.com/w/cpp/numeric/bit_cast предназначенный для решения задач, которые раньше решались через reinterpret_cast.
Недовольное лицо тут пока только у вас.
Не надо приписывать свои эмоции мне, я лишь выражал удивление и восторг.
Я как раз понимаю. Кстати, если вы раньше использовали для решения таких задач reinterpret_cast вместо memcpy, то вы плодили UB. Впрочем, ладно.
Если рабраться, gist.github.com/shafik/848ae25ee209f698763cffee272a58f8, то UB возникает в некоторых случаях, когда оптимизатор делает лишнии оптимизации.
Слишком уж много кода зависит от reinterpret_cast, и тут дело не в том что мы используем, а все так писали достаточно долго.
А вот пример из статьи несколько преувеличен, адресная арифметика работает в С++ как и положено, и даже в примере автора не будет UB, потому что у него лишь указатель на
Если бы всё было так плохо как он описал, то как он предлагает реализовавать аллокаторы для стандартных контейнеров? Там на сколько я знаю всё ещё такой интерфейс
Слишком уж много кода зависит от reinterpret_cast, и тут дело не в том что мы используем, а все так писали достаточно долго.
А вот пример из статьи несколько преувеличен, адресная арифметика работает в С++ как и положено, и даже в примере автора не будет UB, потому что у него лишь указатель на
expression (P)+1 points one past the last element of the array object,
Если бы всё было так плохо как он описал, то как он предлагает реализовавать аллокаторы для стандартных контейнеров? Там на сколько я знаю всё ещё такой интерфейс
T* allocate(std::size_t n)
Ну что значит «лишние оптимизации». Эти оптимизации компилятор как раз и имеет право делать благодаря правилам алиасинга, которым программист должен следовать, для этого эти правила и придуманы — чтобы у компилятора было как раз больше простора для оптимизаций. Если даже сейчас компилятор сохраняет код работоспособным, то это не значит, что в следующей версии не добавятся какие-то оптимизации, которые поломают код с некорректными reinterpret_cast (а варианты его корректного использования можно буквально пересчитать по пальцам). Для сохранения работоспособности кода, который «так писали достаточно долго», сделали костыли типа -fno-strict-aliasing, но это именно что костыли. Что касается аллокаторов, то они AFAIK реализованы как раз через placement new, который имеет интерфейс типа new(ptr) T, то есть может конструировать объект по «готовому» адресу — сначала делается ptr на буфер нужного размера через тот же malloc, а потом по этому ptr создаётся объект.
P.S. Я помню в linux kernel была забавная история, когда там memcpy был реализован через макрос(!), который «для ускорения процесса» приводил буферы к long* и копировал в цикле «аж по 4 байта (а то и по 8)», что приводило к реордерингам вызова этого так называемого «memcpy», он начинал вызываться до кода, который следовал по тексту ранее его и должен был по идее что-то менять в копируемых структурах, и начинался адок. Почти #define true false :)
P.S. Я помню в linux kernel была забавная история, когда там memcpy был реализован через макрос(!), который «для ускорения процесса» приводил буферы к long* и копировал в цикле «аж по 4 байта (а то и по 8)», что приводило к реордерингам вызова этого так называемого «memcpy», он начинал вызываться до кода, который следовал по тексту ранее его и должен был по идее что-то менять в копируемых структурах, и начинался адок. Почти #define true false :)
НЛО прилетело и опубликовало эту надпись здесь
является ли union-style cast с одним из полей, являющимся char*, UB или таки нет
В C++ — однозначно является (а почему нет-то?), в C — нет.
слишком много мин на каждом шагу
Чем больше свободы — тем больше ответственности. И наоборот, соответственно, хехе.
НЛО прилетело и опубликовало эту надпись здесь
Я так понимаю что там пытаются доказать что если одним из элементов union является char, то к нему можно получат доступ всегда, но ИМХО это не так — в стандарте четко сказано, что «at most one of the non-static data members can be active at any time, that is, the value of at most one of the non-static data members can be stored in a union at any time». То есть в какое поле ты последним туда пишешь, только из такого поля ты и имеешь право читать, пока не запишешь в другое (хотя компиляторы обычно все-таки генерируют «дружественный» в этом смысле код). Натягивать сюда алиасинг я бы не стал, он тут ИМХО не при чем, так как для случая union написано, так сказать, более специализированное правило.
UB — это не то, что может возникать из-за оптимизаций. UB — это свойство кода и от уровня оптимизаций не зависит.
В данном случае код вполне корректный, единственная проблема — это отсутствие проверки выравнивания. Но мы захотели сделать наш код ещё быстрее, в итоге комитет выдал перлы уровня «вызывайте мемкопи, который оптимизатором будет отбрасываться и заменятся на прямое обращение к памяти»
НЛО прилетело и опубликовало эту надпись здесь
Справедливости ради, хотелось бы сказать, что по поводу log2p1(), popcount() и прочих функций из этой группы была большущая дискуссия на последнем собрании C++ комитета в Белфасте. Внутри коитета аудитория существенно разделилась. В силу отсутствия консенсуса было принято волевое решение. И если мне не изменяет память, log2p1 таки переименовали в bit_width.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Название имплементации и название результата