Как правильнее изменять размер массива в С++?

Судя по всему, от тебя требуют взять list и vector и превратить их в стек\очередь.

Стек и очередь - интерфейсы, vector и list - структуры данных. В STL stack и queue являются контейнерами-адаптерами, т.е. внутри себя содержат один из стандартных контейнеров (list/vector/deque), т.к. тебе надо реализовать обёртку над структурой данных, которая реализует требуемый порядок доступа к элементам данных. Другими словами навелосипедить stack и queue из STL.

А еще я не понимаю, anahua это на прикладной математике? Лучше бы научили подключать научные либы. Или хотя бы какое-то gmp.

Для реализации очереди и стэка массив не нужен.

А что нужно? Будешь рассказывать про указатели? Я в курсе, но суть применения реаллока не меняется.

Связный список для обоих. И именно потому что стоимость операций добавления/удаления O(1). Вот потому это и надо на прикладной математике, наверное :)

В массиве добавление в начало/конец тоже O(1). А в списке доступ к случайному элементу за O(N) против O(1) массива.

в СТЛ есть къюха, больше ничего не нужно выдумывать

Добавление в начало массива O(1)?! В очереди и стэке random access не нужен.

Читай выше - задание в вузе написать велосипед.

ты хочешь сказать что нельзя написать этот велосипед если засабкласиться от къюшки?

Добавление в начало массива O(1)?!

Вот тебе домашнее задание: как сделать так, чтобы было O(1).

В очереди и стэке random access не нужен.

А в очереди и стеке очень часто надо добавлять в середину? А ведь это — O(1) добавление в середину (если не учитывать время на поиск этой середины) — и есть главным преимуществом связного списка перед массивом.

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

П.С. юзкейс примерно такой - нужно написать свою либу для работы с какими-либо моделями и т.п. сложной фигнёй связаной с математикой. Поверь, когда такие задачи встают, вагонов времени тебе никто не даст на то, чтобы почитать книжки и потренироваться.

П.С.С. и да, можно уже было написать всю эту фигню, пока ты флудил тут)

Вот тебе домашнее задание: как сделать так, чтобы было O(1).

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

А в очереди и стеке очень часто надо добавлять в середину? А ведь это — O(1) добавление в середину (если не учитывать время на поиск этой середины) — и есть главным преимуществом связного списка перед массивом.

Добавление в любое место связного списка O(1), в вектор произвольной длины в общем случае - O(n) и никак иначе.

домашнее задание

Спойлер: http://goo.gl/VWVH8 Откроешь через 8 часов, если не додумаешься. А я спать пошёл.

Вовремя отправил.

Циклический буффер - это уже другая структура данных с другими свойствами.

И чем же циклический буфер так драматически отличается от массива, кроме небольшой поправки индексации (которую можно скрыть абстракцией)?

Добавление в любое место связного списка O(1), в вектор произвольной длины в общем случае - O(n) и никак иначе.

Я в курсе. (Вот только до этого любого места надо ещё дойти за O(N), но, естественно, множитель в этом случае меньше, чем при сдвиге вектора.)

В любом случае, какие уникальные востребованные возможности даёт связный список для стека и очереди? Массив/буфер, например, может быть стековой переменной наконец.

Дельный совет от trex6. Я себе тоже представляю требование, как реализовать тем, что доступно и в C. С отличием: вместо сишного массива брать вектор и не использовать никаких жёстко вкодированных typedef, а вместо этого шаблонные classname.

Таким образом почувствовать преимущество С++ при проверке типов в отличие от универсального сишного void*. А заодно, увидя сообщения об ошибках из-за шаблонов, почувствовать цену этому.

Не бывает стандартной библиотеки шаблонов — бывает стандартная библиотека с++. То, что она включает в себя стандартную библиотеку с, ещё не значит, что ей можно и разрешено пользоваться для сущностей из с++.

Удали то что ты написал, а то тебя сейчас жиром зальют и ты захлебнешся.

Либо realloc (нижнеуровневый сишный интерфейс), либо С++ с философией.

Не бывает стандартной библиотеки шаблонов

<жир>Степанов уже в курсе?</жир>

Хотя я тут подумал... Ведь при изменении размера вектора этот вектор должен оставаться тем же самым. То есть никаких операторов присваивания и конструкторов копирования вообще не должно вызываться. Если побайтово скопировать память, что и делает realloc, то это будут в итоге те же самые объекты, только по другим адресам.

Единственное что инвалидируются все указатели-итераторы на бывшее расположение вектора, но это естественно. Фиксится это разве что специальным методом T::moveTo(T*), который перемещает объект по новому адресу и обновляет все указатели на этот объект, хранимые во других объектах. По-моему, такая двойная зависимость пахнет говнокодом.

То есть по идее realloc — правильное и эффективное решение.

после прочитаного он бы вскрыл себе вены

Наверно, да — думаю, ему сказали, когда STL стал частью стандартной библиотеки с++.

Объект может внутри себя хранить указатель на себя или иметь члены, которым для функционирования нужен указатетель на родительский объект. Его нельзя перемещать через realloc.

думаю, ему сказали, когда STL стал частью стандартной библиотеки с++.

стандартная библиотека С тоже, как и многое из буста, это не отменяет их самостоятельное существование, у STL есть отдельные реализации

Логично, согласен.

Однако, с точки зрения данного топика, эти два понятия мне кажутся эквивалетными, так как в стандарте с++ нет никакого разделения на stl и не-stl часть, а мне, видимо, пытались намекнуть, что new/delete — это часть STL.

Объект может внутри себя хранить указатель на себя

Внутри себя указатель на себя называется this. Если кто-то решил (для омг-оптимизации) хранить указатель на какой-то объект массива внутри самого себя прямиком — его проблемы.

которым для функционирования нужен указатетель на родительский объект

А вот это да. Но, стоп, его же тогда вообще никуда нельзя перемещать!

Присваивание и конструктор копирования не покатят: они создают два клона объекта. И они оба не знают, что за присваиванием будет следовать деструктор, который прибьёт старую копию. И деструктор по идее не знает, где живёт новая копия, чтобы рассказать дочерним объектам о новом расположении. Чтобы его можно было нормально перемещать, надо именно этот moveTo() или что-то в этом роде, который ведёт список всех дочерних объектов.

И, применительно к вектору, проблема неперемещаемого объекта решается просто: хранить указатели на такие объекты, а не сами объекты. Указатели можно перемещать как и куда угодно, сами объекты остаются на месте, дочерние объекты не теряют родителя, в вектор можно спокойно добавлять новые объекты.

Правда, усложняется deep-delete объектов из этого вектора.

Внутри себя указатель на себя называется this. Если кто-то решил (для омг-оптимизации) хранить указатель на какой-то объект массива внутри самого себя прямиком — его проблемы.

Указатель может быть не только на себя, но и внутрь себя. Например, если у объекта есть член-массив и мы всегда хотим работать с его последним элементом, то вместо индекса последнего элемента нам удобнее хранить указатель на него.

Присваивание и конструктор копирования не покатят: они создают два клона объекта. И они оба не знают, что за присваиванием будет следовать деструктор, который прибьёт старую копию.

deep-copy?

Тем не менее, если объект имеет семантику значения, то ничто не мешает правильно реализовать сложный оператор присваивания и конструктор копирования, каким бы сложным объект не был внутри.

хранить указатели на такие объекты

И получить кучу сложностей с ручным управлением памятью.

Указатель может быть не только на себя, но и внутрь себя. Например, если у объекта есть член-массив и мы всегда хотим работать с его последним элементом, то вместо индекса последнего элемента нам удобнее хранить указатель на него.

Вот именно это я и назвал омг-оптимизацией. Вместо получения адреса этого элемента с помощью относительной адресации: [[this + array_offset + ([[this + array_size_offset]] - 2)*sizeof(element)]], мы сделали абсолютную косвенную адресацию: [[this + last_array_element_pointer_offset]]. Сэкономили одно умножение, одно сложение и одно разыменование, чем драматически ускорили выполнение программы, зато полностью заговнякали возможность перемещения этого объекта.

deep-copy?

Нет, вот именно переместить. Вот случай, когда дочерним элементам надо иметь доступ к родительским. Допустим, есть вектор деревьев. Больших. И хранятся в векторе они как значения-корни. Охеренно больших деревьев по 100 мегабайт каждое в начале, но в конец добавляются деревья маленького размера. Вот это нормальное поведение, когда при добавлении в конец вектора какого-то наносаженца в три элемента будет вызываться deep-copy всех деревьев из начала вектора?

Что с этим делать, чтобы этого не было? Именно что

хранить указатели на такие объекты
И получить кучу сложностей с ручным управлением памятью.

Естественно, не хранить просто TreeNode*. А хранить некий Tree, который внутри хранит указатель на TreeNode-корень. Перемещаться будут только эти небольшие Tree, а вся инфонагрузка деревьев остаётся на месте и вообще никуда не копируется. Это как раз вот эти объекты-значения:

Тем не менее, если объект имеет семантику значения, то ничто не мешает правильно реализовать сложный оператор присваивания и конструктор копирования, каким бы сложным объект не был внутри.

Я о чём и говорю: перемещаемость-неперемещаемость объектов — это их собственные проблемы, не вектора; пусть эти их сами и решают каким угодно indirection'ом, а вектор пусть подразумевает перемещаемость.

* [[ [[this + last_array_element_pointer_offset]] ]]

Даже вот так, потому что это тоже указатель. ([[адрес]] = вытягивание значения из памяти по адресу.) Так что в итоге экономим только одно сложение и одно уможение. И получаем вдобавок необходимость следить не только за размером массива, но ещё и за указателем на его конец.

vector.resize

realloc теоретически может быть быстрее, например если за ним есть свободная память и можно просто увеличить размер на месте без копирования памяти. Или уменьшить. Может и не быть. В любом случае изменять размер надо realloc-ом, он для этого придуман.

realloc, vector внутри так и делает

4.2

И чем же циклический буфер так драматически отличается от массива, кроме небольшой поправки индексации (которую можно скрыть абстракцией)?

Ограниченной длиной.

Вот только до этого любого места надо ещё дойти

Для очереди и стэка некритично.

4.2

да, написал ерунду

realloc теоретически может быть быстрее

Бессмысленно сравнивать один интерфейс (realloc) с другим интерфейсом (vector) по скорости работы. Сравнивать можно только реализации.

ЗЫ. В случае с g++ на Linux/glibc@i686 пару лет назад realloc _практически_ был быстрее, иногда в разы, что в общем-то неудивительно.

Ограниченной длиной.

Если быть вообще строгим, то у массива длина вообще неизменяема и у него нет «добавления куда угодно», есть только «копирование всего в новый массив с длиной на единичку больше и заполнение „лишнего“ элемента вставляемым значением». Иначе массив, у которого есть неиспользуемые элементы справа — это именно что циклический буфер, только неиспользуемые ячейки у него с одной стороны, а не с двух.

Для очереди и стэка некритично.

Ну потому и сказал, что множитель малый. Почти никогда не надо удалять и вставлять вот просто в случайных местах; обычно это ж сопряжено с проходом по контейнеру, так что до нужного места добираемся за одинаковое время, а дальше да: у массива вставка за O(N), для списка O(1).

Я сравнивал realloc с free/malloc, вроде топикстартер это спрашивал.

В любом случае это не мешает реализовать в векторе обе стратегии: и пессимистическую (нельзя realloc, вызывать конструктор копирования), и оптимистическую (можно realloc, делать realloc), описать это в документации, поставить от балды дефолтный выбор и дать возможность выбирать стратегию при создании вектора.

Сэкономили одно умножение, одно сложение и одно разыменование, чем драматически ускорили выполнение программы, зато полностью заговнякали возможность перемещения этого объекта.

Перед этим мы сделали vector<T>::iterator тайпдефом на T*, а не классом { vector<T>* v; size_t offset; }, чтобы экономить ровно столько же.

Нет, вот именно переместить.

C++11 позволяет перемещать объекты, вектор так и делает (если объект имеет конструктор перемещения). Но хранить дерево вместо указателя на корень действительно глупо, так как при реализовывании дерева всё равно приходится думать об управлении паматью.

Я о чём и говорю: перемещаемость-неперемещаемость объектов — это их собственные проблемы, не вектора; пусть эти их сами и решают каким угодно indirection'ом, а вектор пусть подразумевает перемещаемость.

Если вектор хочет работать не только с POD, то эти проблемы становятся его проблемами. В мире си++ перемещаемость — это наличие operator=, T(const T&) и ~T, с недавнего времени — наличие T(T&&).

Да, многие писатели собственных векторов так и делают.

с free/malloc, вроде топикстартер это спрашивал.

Верно, я не врубился. Подумал, что он спрашивает о vector'е.

Причем тут операторы копирования? realloc не создает копий.

А как переместить c++-объект в другое место памяти без свопа или конструктора копирования/оператора присваивания?

Переместить объект можно множеством способов. мемкпу — чем не вариант? Единственное, надо следить чтобы при перемещении его не размножило. Чего как раз и не происходит при реаллоке.

мемкпу — чем не вариант?

А почему не memmove?

Опять двадцать пять. Тем не вариант, что не вызывает A::operator= или A::A(const A&) или A::A(A&&), которые обеспечивают объектам возможность их копирования/перемещения с учётом их семантики.

class MyCoolMutex 
{
    private:
        pthread_mutex_t m;
        operator=(const MyCoolMutex&);
        MyCoolMutex(const MyCoolMutex&);
    public:
        MyCoolMutex() { pthread_mutex_init(...); }
        ~MyCoolMutex() { pthread_mutex_destroy(...); }
        void lock() { ... }
        void unlock() { ... }
};
MyCoolMutex a;
a.lock();
MyCoolMutex *b = malloc(sizeof(a));
memmove(b, &a, sizeof(a));
b->unlock(); // fail!

Потому что кусочки не пересекаются