2 вопроса по С++, из вопросов Lamo17

zrab

неавеяно этой темой
  Собственно, там говорится про qsort. Судя по вопросу, а также по тому, что qsort — это скорее всего quick sort, подразумевают ответ "для отсортированного массива время работы наибольшее". А раз подразумевается такой ответ, то вопрос вот в чем: почему не используют randomized_qsort в библиотеке С++? Зачем лишний гемор с qsort?
  И второй вопрос: в студии проверил: действительно new int[0], к моему удивлению, выделяет память и возвращает указатель.
  чтозанах? Зачем это сделали в реализации? Не было бы логично сделать все так, чтобы возвращался 0?
   Ах, да, мне тоже в CBoss :grin:
   Я его бот. Если что — пишите приваты по поводу подработки :grin: тема в job'e
   

Dasar

чтозанах? Зачем это сделали в реализации? Не было бы логично сделать все так, чтобы возвращался 0?
нарушится аж два имеющихся инварианта:
1. если что-то создали, то оно не NULL
2. если создали две разные штуки, то ссылки у них не совпадают

Andbar

И второй вопрос: в студии проверил: действительно new int[0], к моему удивлению, выделяет память и возвращает указатель.
чтозанах? Зачем это сделали в реализации? Не было бы логично сделать все так, чтобы возвращался 0?
Логично чтобы NULL возвращался при невозможности выделить память.

123anna

1. На выбор случайного элемента тратится какое-то время. Приходится выбирать, либо гарантировать сложность NlogN для любых входных данных, либо работать чуть быстрее на 99.9% обычных данных. Совершенно нормально выбрать второй вариант, при этом программист должен помнить, когда именно можно наступить на этот 0.1%
2. Пусть есть функция с аргументом n, которая выделяет память и что-то в этой памяти мутит в цикле от 0 до n. Тот факт, что new[0] срабатывает, позволит этой функции успешно выполниться. Программисту не придется разбирать частный случай n == 0.
А если вернуть NULL, то функция решит, что это ошибка выделения памяти. Зачем ошибка, если можно по-тихому все разрулить?
И, кстати, это не реализация, это требование стандарта

Serab

подразумевают ответ "для отсортированного массива время работы наибольшее"
Прочтение той же темы должно было тебе навеять, что это неверно.

zrab

Почему? разве не quick sort там используется?

Serab

Там было написано конкретно что используется, было написано конкретно, что для этого упорядоченный массив — не худший случай и был дан намек на то, как искать худший случай.

zrab

Там было написано конкретно что используется, было написано конкретно, что для этого упорядоченный массив — не худший случай и был дан намек на то, как искать худший случай.
ссылку можешь дать? что используется в библиотечной ф-и qsort?

Serab

Как реализовано у MS:
Немного про худший случай:

Anturag

И второй вопрос: в студии проверил: действительно new int[0], к моему удивлению, выделяет память и возвращает указатель.
Вероятно это сделано для удовлетворения C гиков в желании получать структуры динамического размера.


#include <stdio.h>

#include <stdlib.h>

#include <string.h>



typedef struct {

    int anything;

    char c[0];

} char_t;



int main(int argc, char** argv)

{

    char_t *a;

    char msg[] = "Hello";

    

    a = (char_t *)malloc(sizeof(char_t) + sizeof(msg;

    memcpy(&a->c[0], msg, sizeof(msg;

    

    printf("struct size: %d, message size: %d, message: %s\n",

        sizeof(char_t sizeof(msg a->c);

    

    return 0;

}

P.S. Говорят, что все программисты умирают мистиками :)

erotic

char c[0];
Странно, что-то у Александреску видел, что нельзя объявлять массивы нулевого размера, ошибка компиляции типа, и что на этом можно построить статический ассерт. А оказывается, что это вполне компилируется.

Dasar

Странно, что-то у Александреску видел, что нельзя объявлять массивы нулевого размера
может меньше нулевого?

procenkotanya

Расширение GCC. В режиме строго соответствия стандарту не разрешает.

Anturag

Расширение GCC. В режиме строго соответствия стандарту не разрешает.
В стандарте не нашёл явного запрета на использования массивов менее или равных нулю.
Приведённый пример хорошо дружит с -std=c99, более того, по стандарту (C99, 6.5.3.4, example 7) реален даже такой крэп:


void some(int n) {

    char b[n];

    printf("Nice to meet you, negative array of size %d\n", sizeof(b;

}

Maurog

6.7.5.2 Array declarators
Constraints
1 In addition to optional type qualifiers and the keyword static, the [ and ] may delimit
an expression or *. If they delimit an expression (which specifies the size of an array the
expression shall have an integer type. If the expression is a constant expression, it shall
have a value greater than zero. The element type shall not be an incomplete or function
type. The optional type qualifiers and the keyword static shall appear only in a
declaration of a function parameter with an array type, and then only in the outermost
array type derivation.

Anturag

Спасибо за цитату, буду знать. Жаль, что для случая delimited expression применяется тип int со всеми вытекающими последствиями.
Ну, не будем стрелять себе в ногу :)
Оставить комментарий
Имя или ник:
Комментарий: