Ned
Ну дык нужна динамичность
Ned
Я ж не могу его взять и рандомно удлинить...
Anatoly
Ну так динамический массив!
Ned
Дык он сразу длину приобретает... как это обойти?
Anatoly
malloc, realloc?
Ned
Изначально она должна быть нулевой
Ned
Кхэммм. ..
Ned
А реаллок не потрёт всё что было?
Anatoly
При необходимости перевыделяй память, увеличивая капасити в 2 раза.
Anatoly
Реаллок не потрёт.
Ned
А каков аналог реаллоку в С++?
Anatoly
Но тут надо определиться, нужна ли работа только с простыми типами, или ещё и с объектами
Ned
Или #include <cstdlib> ??
Sergey
суть вектора в том, что при добоавлении он выделяет новую память и переносит данные
Anatoly
Слу, а как насчёт посмотреть реализацию std::vector?
Ned
Но тут надо определиться, нужна ли работа только с простыми типами, или ещё и с объектами
Я умею в маллок под объекты... как правило добавляю объектам свой sizeof
Anatoly
суть вектора в том, что при добоавлении он выделяет новую память и переносит данные
При этом вызывается батарея copy или move конструкторов.
Ned
Лан, спасибо
Anatoly
Чегойта "долго"?
Ned
Нулол, быстрей по двусвязке бегать
Anatoly
Удваивать размер массива надо log (n) раз
Sergey
вот ведь авторы Stl глупцы
Ned
Я всю жизнь удваиваю в два раза
Ned
Наверное что-то со мной не так😂
Anatoly
вот ведь авторы Stl глупцы
Не, ну они, конечно, умудрились налажать с автопоинтером, но вообще да.
Ned
Блин, нипанятна
Ned
Вроде понятно, а вроде и нет
Ned
Кстати, как пишут set?
Anatoly
Чего непанятна-то? Если выделено памяти на 64 элемента, а нам нужен 65-ый, то выделяем память на 128, копируем 64 в новое место, и не чешемся, пока не будет нужно 129 элементов.
Anatoly
А потом 257. И 513. И 1025.
Ned
Anatoly
Почти как хешмеп, только одни keys, без values.
Anatoly
Указатели на свои члены, и т.д.
Ned
Тык зачем их тогда трогать?
Ned
Лежат же на месте
Anatoly
На старом месте. А на старом месте может не оказаться блока памяти подходящего размера.
Anatoly
И ваще
Anatoly
http://codereview.stackexchange.com/questions/60484/stl-vector-implementation
Anatoly
http://stackoverflow.com/questions/2096571/how-is-c-stdvector-implemented
Anatoly
И т.д.
Андрей
Чего непанятна-то? Если выделено памяти на 64 элемента, а нам нужен 65-ый, то выделяем память на 128, копируем 64 в новое место, и не чешемся, пока не будет нужно 129 элементов.
Это плохая логика. Переиспользовать амять не получится.
Anatoly
Не получится. И? Твой вариант?
Anatoly
Это не важно. Тупо performance/memory tradeoff.
Anatoly
Вот почему 1.5, а не 1.267?
Anatoly
"Это не важно" (с) я
Андрей
На логику это не влияет, но переиспользование памяти всё-таки надо делать.
Андрей
Идеальным порогом будет 1/2 + sqrt(5) / 2
Андрей
Хотя нет, вру.
Андрей
А, нет. Не вру.
Anatoly
Идеальным? Какую функцию должен минимизировать сей икс?
Anatoly
Чуть не забыл: в самом начале надо выделять не 1-2-4 элемента, а, скажем, сразу 8-16
Андрей
Идеальным? Какую функцию должен минимизировать сей икс?
Это порог, когда переиспользование памяти возможено.
Anatoly
Лолшто?
Anatoly
Переиспользование возможно всегда.
Anatoly
С чегойта? Я хоть с константой 100 смогу.
Андрей
Если мы будем рассматривать только массив внутри памяти.
Андрей
+ память фрагментироваться не будет.
Андрей
Тоже в рамках одного массива.
Anatoly
Так же как и с 2.
Anatoly
Новую память выделил, скопировал данные, старую освободил. Подходи, бери кому сколько надо.
Андрей
1+2+...(2n - 2) < 2n
Anatoly
Что это?
Андрей
Херню написал.
Anatoly
Да я вижу. Зачем ты её написал?
Андрей
1 + 2 + 4 + 2^(n - 1) < 2^n
Андрей
Так верно.
Anatoly
Теперь верно. И?
Андрей
У тебя на каждом шаге уже использованная память будет больше, чем тебе надо. Поэтому не сможешь переиспользовать.
Андрей
С константой > 1/2 + sqrt(5) / 2, конечно же.
Anatoly
С чегой-та я не смогу её использовать???
Anatoly
И где эта твоя константа в той формуле, что ты написал?