Я там сейчас работаю

Да, я и сказал, это для людей, которые могут.

...

как реализовать stl::vector с доступом к элементу за O(1)?

Хэштаблица

Хэштаблица

Зачем? Массива ж достаточно.

Зачем? Массива ж достаточно.

Хочу сделать массив, короче. Такой, чтобы длина была равна кол-ву эл-тов в нём. И был произвольный доступ.

В случае с двусвязкой, доступ дорогой

Нужен произвольный за 0(1)

Эээ... ну массив же!

Ну дык нужна динамичность

Я ж не могу его взять и рандомно удлинить...

Ну так динамический массив!

Дык он сразу длину приобретает... как это обойти?

malloc, realloc?

Изначально она должна быть нулевой

Кхэммм. ..

А реаллок не потрёт всё что было?

При необходимости перевыделяй память, увеличивая капасити в 2 раза.

Реаллок не потрёт.

А каков аналог реаллоку в С++?

Но тут надо определиться, нужна ли работа только с простыми типами, или ещё и с объектами

Или #include <cstdlib> ??

суть вектора в том, что при добоавлении он выделяет новую память и переносит данные

Слу, а как насчёт посмотреть реализацию std::vector?

Но тут надо определиться, нужна ли работа только с простыми типами, или ещё и с объектами

Я умею в маллок под объекты... как правило добавляю объектам свой sizeof

суть вектора в том, что при добоавлении он выделяет новую память и переносит данные

При этом вызывается батарея copy или move конструкторов.

При этом вызывается батарея copy или move конструкторов.

Долго. Надо быстро

Лан, спасибо

Чегойта "долго"?

Нулол, быстрей по двусвязке бегать

Удваивать размер массива надо log (n) раз

Удваивать размер массива надо log (n) раз

Хорошо сказал

вот ведь авторы Stl глупцы

Я всю жизнь удваиваю в два раза

Наверное что-то со мной не так?

вот ведь авторы Stl глупцы

Не, ну они, конечно, умудрились налажать с автопоинтером, но вообще да.

Я всю жизнь удваиваю в два раза

Наверное тебе стоит ещё раз прочитать тот коммент.

Блин, нипанятна

Вроде понятно, а вроде и нет

Кстати, как пишут set?

Чего непанятна-то? Если выделено памяти на 64 элемента, а нам нужен 65-ый, то выделяем память на 128, копируем 64 в новое место, и не чешемся, пока не будет нужно 129 элементов.

А потом 257. И 513. И 1025.

Чего непанятна-то? Если выделено памяти на 64 элемента, а нам нужен 65-ый, то выделяем память на 128, копируем 64 в новое место, и не чешемся, пока не будет нужно 129 элементов.

А нах копировать?

Почти как хешмеп, только одни keys, без values.

А нах копировать?

У обьектов могут быть нетривиальные кишки.

Указатели на свои члены, и т.д.

Тык зачем их тогда трогать?

Лежат же на месте

На старом месте. А на старом месте может не оказаться блока памяти подходящего размера.

И ваще

http://codereview.stackexchange.com/questions/60484/stl-vector-implementation

http://stackoverflow.com/questions/2096571/how-is-c-stdvector-implemented

И т.д.

Чего непанятна-то? Если выделено памяти на 64 элемента, а нам нужен 65-ый, то выделяем память на 128, копируем 64 в новое место, и не чешемся, пока не будет нужно 129 элементов.

Это плохая логика. Переиспользовать амять не получится.

Не получится. И? Твой вариант?

Не получится. И? Твой вариант?

Выделять не в 2 раза больше памяти, а в 1,5. Например.

Это не важно. Тупо performance/memory tradeoff.

Вот почему 1.5, а не 1.267?

ERROR: S client not available

Вот почему 1.5, а не 1.267?

Константа от балды выбрана.

"Это не важно" (с) я

На логику это не влияет, но переиспользование памяти всё-таки надо делать.

Идеальным порогом будет 1/2 + sqrt(5) / 2

Хотя нет, вру.

А, нет. Не вру.

Идеальным? Какую функцию должен минимизировать сей икс?

Чуть не забыл: в самом начале надо выделять не 1-2-4 элемента, а, скажем, сразу 8-16

Идеальным? Какую функцию должен минимизировать сей икс?

Это порог, когда переиспользование памяти возможено.

Лолшто?

Переиспользование возможно всегда.

Переиспользование возможно всегда.

С константой 2 ты не сможешь переиспользовать память.

С чегойта? Я хоть с константой 100 смогу.

Если мы будем рассматривать только массив внутри памяти.

+ память фрагментироваться не будет.

Тоже в рамках одного массива.

Если мы будем рассматривать только массив внутри памяти.

А где ж ещё, в космосе что ли?

А где ж ещё, в космосе что ли?

Ок, как ты будешь переиспользовать память с константой 100?

Так же как и с 2.

Новую память выделил, скопировал данные, старую освободил. Подходи, бери кому сколько надо.

1+2+...(2n - 2) < 2n

Что это?

Херню написал.

Да я вижу. Зачем ты её написал?

1 + 2 + 4 + 2^(n - 1) < 2^n

Так верно.

Теперь верно. И?

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

С константой > 1/2 + sqrt(5) / 2, конечно же.