Должен ли мой std :: vector содержать указатели или структуры? - PullRequest
8 голосов
/ 28 августа 2011

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

Однако мое предпочтение должно определятьсяпреимущество наличия члена std::vector<myStruct> *ptr2Vect.А именно, не нужно вызывать delete для каждого элемента.Насколько велико это преимущество в производительности?Может ли вектор действительно размещать объекты в стеке?Я довольно новичок в шаблонных классах и задаюсь вопросом, возможно ли расширение динамического массива в стеке и по какой цене?

_ EDIT _

Мне не удается понять конструктор копирования по умолчанию и члены operator =, и я пытаюсь придерживаться упрощенных структур.У меня нет ни одной явно определенной реализации, поэтому я опасаюсь, что при создании элемента вектора вместо указателя во время присваивания будет создан временный объект, который будет разрушен, и поэтому испорчена его копия.1016 * _

Извините за задержку с доставкой соответствующей информации (я стесняюсь с моим кодом).

Я хочу вызвать push_back (newObj).Теперь, если я не использую указатели, у меня есть большая проблема в том, что я не хочу выполнять глубокое копирование, но мой dtor освободит память, разделяемую LHS и RHS этого вызова конструктора копирования.

Ответы [ 7 ]

7 голосов
/ 28 августа 2011

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

Возможные причины для рассмотрения указателей:

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

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

Отсутствие указателей в ваших контейнерах значительно упрощает использование STL <algorithms>, рассмотрим:

#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>

int main() {
  std::vector<std::string> test;
  test.push_back("hello world");
  std::copy(test.begin(), test.end(), 
            std::ostream_iterator<std::string>(std::cout, "\n"));
}

В сравнении:

#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>

int main() {
  std::vector<std::string*> test;
  // if push_back throws then this will leak:
  test.push_back(new std::string("hello world"));
  // Can't do:
  std::copy(test.begin(), test.end(), 
            std::ostream_iterator<std::string>(std::cout, "\n"));
  // Will now leak too
}

(что я бы никогда делать)

Или, возможно:

#include <vector>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>

int main() {
  std::vector<std::string*> test;
  std::string str("hello world");
  test.push_back(&str);
  // Can't do:
  std::copy(test.begin(), test.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}

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

3 голосов
/ 28 августа 2011

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

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

Забота о скорости # 1, конечно, использует хорошие алгоритмы. Но проблема №2 заключается в хорошей локализации, потому что память медленная ... А по сравнению с процессором она замедляется с каждым годом.

Таким образом, для небольших простых объектов vector<Obj> почти наверняка будет быстрее, чем vector<Obj *>, и, возможно, намного быстрее.

Что касается «может ли вектор действительно размещать объекты в стеке», то ответ «да» с точки зрения семантики, но не с точки зрения реализации (скорее всего). Типичная векторная реализация состоит из трех указателей внутри: Base, Current и End. Все три указывают на непрерывный блок в куче, и деструктор вектора освободит этот блок. (Опять же, это типичная реализация; теоретически ваш компилятор и / или среда выполнения могут делать что-то еще. Но я уверен, что это не так.)

Такая реализация поддерживает динамическое расширение, перераспределяя этот блок и копируя данные. Это не так медленно, как кажется по двум причинам: (1) Линейный доступ к памяти (например, копирование) довольно быстрый; и (2) каждое перераспределение увеличивает размер блока на коэффициент , что означает, что push_back все еще O (1) амортизируется.

3 голосов
/ 28 августа 2011

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

Вы должны делать то, что (указатель или объект) имеет наибольшее значение для приложения.

2 голосов
/ 28 августа 2011

Единственное, что не упомянуто в отношении указателей и структур - это непрерывность памяти (более подробно о встроенных). По сути, вектор структуры будет размещен в 1 блоке памяти, а вектор указателей на структуру (вероятно) будет размещен повсеместно. Таким образом, серьезно пострадают фрагментация памяти и кэш данных.

1 голос
/ 28 августа 2011

Ваш вопрос не очень понятен.Сначала вы говорите о векторе указателей, а затем пишете что-то вроде: std::vector<myStruct> *ptr2Vect.

  1. std::vector<myStruct> *ptr2Vect - это указатель на вектор из myStruct объектов.Вектор не хранит указатели, поэтому вам не нужно беспокоиться об управлении памятью удерживаемых объектов - просто нужно убедиться, что myStruct является копируемым.Вам нужно вручную управлять очисткой указателя на вектор (ptr2Vect)
  2. Большинство современных систем работают очень эффективно с указателями, если вы задаете такой вопрос, вы следуетемаршрут для преждевременной оптимизации, остановка, шаг назад.
  3. vector опирается на динамическое распределение, но как он расширяется, он управляет (вы можете контролировать его до некоторой степени, например, если вы знаете размерперед этим вы можете reserve)

Из того, что я понял из вопроса, вы действительно не в той точке, где вам нужно беспокоиться об издержках автоматического / динамического выделения и указателя-referencing.Это наименьшая из ваших проблем, просто научитесь писать хороший код - все остальное придет позже (если потребуется)

0 голосов
/ 28 августа 2011

Мое первое предложение: «Вам не обязательно указывать указатель на вектор» в качестве члена. Вы хотите простой вектор myVector; ИЛИ вектор

Во-вторых, вы примете решение на основе следующих вопросов

  1. Каков размер вектора? (сколько элементов макс.) скажи п
  2. Каков размер структуры? (SizeOf (Т)) скажи с
  3. Сколько стоит копирование структуры? скажи с
  4. Ваша структура содержит какой-то ресурс? (например, какой-нибудь дескриптор файла или семафор и так далее)? Если он содержит какой-то ресурс, то вектор может значительно усложнить вашу жизнь.

Теперь n, s, c определят ваши накладные расходы времени выполнения вектора Для вектора стоимость из-за n, s, c равна нулю. Для вектора стоимость из-за n, s, c равна n * s sizeUnits + n * c исполнительных единиц.

Мое эмпирическое правило: эмпирического правила не существует. Сначала закодируйте его с вектором, если он недостаточно хорош, затем перейдите с вектором

Если ваша программа - это небольшая программа, которая собирается завершить процесс после того, как вы использовали свой вектор, то я бы даже не стал их освобождать. Если нет, тогда просто запустите
for (auto it = v.begin (); it! = v.end (); ++ it) удалить * it;

0 голосов
/ 28 августа 2011

Однако мое предпочтение определяется преимуществом наличия члена std :: vector * ptr2Vect. А именно, не нужно вызывать delete на каждом элементе. Насколько велико это преимущество в производительности?

зависит от количества элементов, но может сэкономить массу памяти и времени. см:

Сколько стоит наследство?

Может ли вектор действительно размещать объекты в стеке?

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

Я довольно плохо знаком с шаблонными классами и задаюсь вопросом, может ли динамический массив расширяться в стеке и по какой цене?

Если у вас постоянный размер, то конкретная реализация (например, boost::array) может сэкономить массу времени выполнения. я написал несколько типов для разных контекстов.

...