Array vs vector vs list

Ответ 1

Использовать STL vector. Он обеспечивает не менее богатый интерфейс как list и устраняет боль при управлении памятью, требуемой массивами.

Вам нужно будет очень стараться показать стоимость исполнения operator[] - он обычно становится вложенным.

У меня нет номера для вас, но я помню, как читал анализ производительности, который описывал, как vector<int> был быстрее, чем list<int> даже для вставок и удалений (по определенному размеру). Истина заключается в том, что эти процессоры, которые мы используем, очень быстрые, и если ваш вектор вписывается в кеш-память L2, то это будет действительно очень быстро. Списки, с другой стороны, должны управлять объектами кучи, которые будут убивать ваш L2.

Ответ 2

Преждевременная оптимизация - это корень всего зла.

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

Ответ 3

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

- Списки -

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

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

- Векторы -

Вектор содержит элементы в последовательности, как и массив. Это очень удобно для произвольного доступа. Доступ к элементу "nth" в векторе - это простой расчет указателя (скорость O (1)). Однако добавление элементов в вектор отличается. Если кто-то хочет добавить элемент в середине вектора - все элементы, которые появляются после этого элемента, должны быть выделены, чтобы освободить место для новой записи. Скорость будет зависеть от размера вектора и от положения нового элемента. В худшем случае вставка элемента в позицию 2 в векторе, лучший из которых - добавление нового элемента. Поэтому - вставляйте произведения со скоростью O (n), где "n" - это количество элементов, которые нужно переместить - необязательно размер вектора.

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

Как всегда... " Преждевременная оптимизация - это корень всех злых, поэтому сначала рассмотрите, что более удобно, и сделайте все так, как вы хотите, а затем оптимизируйте. За 10 записей, которые вы упомянули, это не имеет значения, что вы используете - вы никогда не сможете увидеть какую-либо разницу в производительности, какой бы метод вы ни использовали.

Ответ 4

Предпочитают std::vector и массив. Некоторые преимущества вектора:

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

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

Ответ 5

Вы делаете предположения, которые вы не должны делать, например, "доступ к элементу медленнее, чем массив, поскольку он является вызовом оператора []". Я могу понять логику, стоящую за ней, но вы и я не можем знать, пока мы ее не профилируем.

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

Некоторые решения должны выделять vector из стека и иметь распределитель пулов для list, так что узлы могут вписываться в кеш.

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

Контейнер по умолчанию имеет значение vector. Иногда массив вполне приемлем.

Ответ 6

Сначала несколько примечаний:

Хорошее правило о выборе структур данных: Как правило, если вы изучили все возможности и определили, что массив - ваш лучший выбор, начните сначала. Вы сделали что-то очень плохое.

Списки STL не поддерживают operator[], и если они сделали причину, что она будет медленнее, чем индексирование, массив не имеет ничего общего с накладными функциями вызова функции.

Говоря об этом, вектор является явным победителем здесь. Вызов operator[] существенно незначителен, поскольку содержимое вектора гарантированно смежно в памяти. Он поддерживает операции insert() и erase(), которые вы должны были бы описать самостоятельно, если бы вы использовали массив. В основном это сводится к тому, что вектор представляет собой, по существу, обновленный массив, который уже поддерживает все необходимые операции.

Ответ 7

Я поддерживаю таблицу с фиксированной длиной 10 записей. Каждый элемент структура как 4 поля. Будут вставлены, обновлены и удалены операции, заданные числовой позицией. Мне интересно, лучшая структура данных, используемая для поддержки этой таблицы информации:

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

Вопросы, которые вам нужно задать, - три раза. Во-первых, как часто вы планируете делать удаления/вставки в середине относительно случайных чтений. Во-вторых, насколько важно использовать числовую позицию по сравнению с итератором. Наконец, порядок в вашей структуре важен.

Если ответ на первый вопрос будет случайным, будет более распространенным, чем вектор/массив, вероятно, будет работать хорошо. Обратите внимание, что итерация через структуру данных не считается случайным чтением, даже если используется оператор []. Для второго вопроса, если вам абсолютно требуется числовая позиция, чем требуется вектор/массив, даже если это может привести к поражению производительности. Позже тестирование может показать, что это снижение производительности незначительно по сравнению с более простым кодированием с численными позициями. Наконец, если порядок неважен, вы можете вставить и удалить в векторе/массиве с помощью алгоритма O (1). Ниже приведен пример алгоритма.

template <class T>
void erase(vector<T> & vect, int index) //note: vector cannot be const since you are changing vector
{
  vect[index]= vect.back();//move the item in the back to the index
  vect.pop_back(); //delete the item in the back
}

template <class T>
void insert(vector<T> & vect, int index, T value) //note: vector cannot be const since you are changing vector
{
  vect.push_back(vect[index]);//insert the item at index to the back of the vector
  vect[index] = value; //replace the item at index with value
}