вектор по сравнению со списком в STL

Списки являются просто оберткой для вдвойне-LinkedList в stl, таким образом предлагая функцию, которую Вы могли бы ожидать от d-linklist а именно, O (1) вставка и удаление. В то время как векторы являются заразной последовательностью данных, которая работает как динамический массив. P.S. - легче пересечь.

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

вектор

• вектор А хранит свои элементы в непрерывной памяти. Поэтому произвольный доступ возможен в векторе, что означает, что доступ к элементу вектора очень быстр, потому что мы можем просто умножить базовый адрес с индексом объекта для доступа к тому элементу. На самом деле это берет только O (1) или постоянное время с этой целью.

• , Так как вектор в основном переносит массив, каждый раз, когда Вы вставляете элемент в вектор (динамический массив), он должен изменить размер себя, найдя, что новый непрерывный блок памяти размещает новые элементы, который является дорогостоящим временем.

• Это не использует дополнительную память для хранения любых указателей на другие элементы в нем.

список

• список А хранит свои элементы в памяти, состоящей из нескольких несмежных участков. Поэтому произвольный доступ не возможен в списке, что означает, что для доступа к его элементам мы должны использовать указатели и пересечь список, который медленнее относительно вектора. Это берет O (n) или линейное время, которое медленнее, чем O (1).

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

• Это использует дополнительную память для хранения указателей на элемент прежде и после конкретного элемента.

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

Делают это простым -
В конце дня, когда Вы смущены, выбрав контейнеры в использовании C++ это изображение блок-схемы (Скажите спасибо мне):- вводит описание изображения здесь

Вектор -
1. вектор основан на заразной памяти
2. вектор является способом пойти для небольшого набора данных
3. вектор работает самый быстрый при пересечении на наборе данных
4. векторное удаление вставки является медленным на огромном наборе данных, но быстро для очень маленького

Список -
1. список основан на памяти "кучи"
2. список является способом пойти для очень огромного набора данных
3. список является сравнительно медленным при пересечении небольшого набора данных, но быстро в огромном наборе данных
4. удаление вставки списка является быстрым на огромном наборе данных, но медленным на меньших

Если вам не нужно часто вставлять элементы, вектор будет более эффективным. У него гораздо лучшая локализация кэша ЦП, чем у списка. Другими словами, доступ к одному элементу делает очень вероятным, что следующий элемент присутствует в кэше и может быть извлечен без необходимости чтения медленной RAM.

В вашей функции

void do_something(double *arr_in, ...) {
   for (...) {
      arr_in = do_that_something;
   }
}

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

void do_something(double **arr_in, ...) {
   for (...) {
      *arr_in = do_that_something;
   }
}
/*
** Would be called like this:
** do_something(&array, ...);
*/

Придерживаться первого примера, как это легче читать. Необходимо добавить проверку ошибок в первом примере, если вызов malloc не удался, и продолжить обработку с помощью указателя NULL...

Надеюсь, что это поможет, С уважением, Том.

Возврат самого двойника не стоит вам много с точки зрения времени выполнения.

Гораздо более важным является выделение памяти при каждом входе в функцию. Если вы можете предварительно распределить или сохранить результат на месте, как вы предлагали, это должно значительно увеличить скорость.

Другое дело, что на самом деле вам нужна вся точность, которую обеспечивает двойник (в сравнении с плавающим типом). Во многих случаях поплавки намного быстрее.

В основном вектор представляет собой массив с автоматическим управлением памятью. Данные являются непрерывными в памяти. Попытка вставить данные в середине является дорогостоящей операцией.

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

Чтобы ответить более конкретно на ваш вопрос, процитирую векторы на этой странице

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

Одной из специальных возможностей std::list является сращивание (связывание или перемещение части или целого списка в другой список).

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

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

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

Когда в середине последовательности много вставок или удалений. например менеджер памяти.

Если вы хотите перемещать объекты между контейнерами, вы можете использовать list :: splice .

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

Изменить: по мере того, как библиотеки готовятся к реализации C ++ 0x, общий случай объединения подпоследовательности в список становится линейной сложностью в зависимости от длины последовательности.Это связано с тем, что splice (сейчас) необходимо перебирать последовательность, чтобы подсчитать количество элементов в ней. (Поскольку список должен записывать свой размер.) Простой подсчет и повторное связывание списка по-прежнему выполняется быстрее, чем любая альтернатива, а сращивание всего списка или одного элемента - особые случаи с постоянной сложностью. Но если вам нужно склеить длинные последовательности, возможно, вам придется поискать лучший, старомодный, несовместимый контейнер.

Сохранение валидности итераторов является одной из причин использования списка. Другая причина - когда не нужно, чтобы вектор перераспределялся при нажатии на элементы. Этим можно управлять с помощью интеллектуальной функции reserve(), но в некоторых случаях проще или целесообразнее просто использовать список.

вектор:

• Сплошная память.
• Предварительно выделяет пространство для будущих элементов, поэтому требуется дополнительное пространство за пределами того, что необходимо для самих элементов.
• Каждый элемент требует только пространства для самого типа элемента (без лишних указателей).
• Может перераспределять память для всего вектора в любой момент времени, когда вы добавляете элемент.
• Вставки в конце являются постоянными, амортизированными по времени, но вставки в других местах являются дорогостоящими O(n).
• Стирания в конце вектора - постоянное время, но для остальных - O(n).
• Вы можете случайным образом получить доступ к его элементам.
• Итераторы недействительны, если вы добавляете или удаляете элементы в вектор или из него.
• Вы можете легко получить доступ к базовому массиву, если Вам нужен массив элементов.

list:

• Non-contiguous memory.
• Нет предварительно распределенной памяти. Нагрузка на память для самого списка постоянная.
• Каждый элемент требует дополнительного места для узла, в котором хранится элемент, включая указатели на следующие и предыдущие элементы списка.
• Никогда не нужно перераспределять память для всего списка только потому, что вы добавляете элемент.
• Вставки и стирания дешевы вне зависимости от того, где в списке они встречаются.
• Дешево комбинировать списки с сращиванием.
• Вы не можете получить случайный доступ к элементам, поэтому добраться до определенного элемента в списке может быть дорого.
• Итераторы остаются действительными даже при добавлении или удалении элементов из списка.
• Если вам нужен массив элементов, вам придется создать новый и добавить в него все элементы, так как нет базового массива.

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

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