Какая структура лучше всего подходит для реализации, когда количество элементов в списке / массиве является переменным?

Question

У меня есть немного конкретный вопрос. Я использую C / C ++ с OpenCV. Моя цель хранить обнаруженные прямоугольники в структуре списка / массива. Однако длина является переменной для каждого кадра (итерации).

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

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

Спасибо

РЕДАКТИРОВАТЬ: Я не ограничен C (я знаю, что упомянул malloc). Я могу использовать функции C ++, так как остальная часть моей программы не использует никаких специфических функций C. Так что не стесняйтесь предлагать мне лучшие способы.

Answer 1

Я бы порекомендовал вам использовать std::vector.Стандарты C ++ гарантируют, что элементы в std::vector будут смежными, как это сделал бы массив C .Это позволяет std::vector быть интерфейсом между структурами данных C ++ и функциями C.Вы можете использовать std::vector<T>::resize, чтобы убедиться, что есть место, выделенное перед передачей его функциям OpenCV.

О, чтобы получить указатель на внутреннее хранилище вектора, вы обычно используете эту запись: &rectangleCollection[0].

Удачи!

Answer 2

Вы можете создавать динамические массивы и использовать realloc(), когда он должен расти.Если возможно:

• Поскольку ваш начальный массив будет (возможно) средней ожидаемой длины
• Используйте экспоненциальный рост, чтобы при перераспределении массива вы удваивали выделенный размер

Конечно, вы также можете сделать что-то более сложное, но я бы рекомендовал сначала протестировать с обычными перераспределенными массивами.

Answer 3

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

Edit: О, так что вы на самом деле используете C ++. В таком случае просто получите вектор.

Answer 4

Ответ зависит:

Как правило, я бы рекомендовал CGrowableArray, найденный в DirectX SDK. (Вам не нужно включать DirectX, просто удалите этот шаблон класса) (Если вы не хотите использовать шаблон класса C ++, вы можете легко реализовать ту же логику, что и набор функций C) *

Какая польза от std :: vector?

a) Распределяет объекты по времени, используя эвристику

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

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

---

С другой стороны, если вы не собираетесь хранить реальные объекты, но указатели, навязчивый связанный список идеален. В этом случае как «Добавить» (2 назначения), так и «Очистить» (1 назначение) являются тривиальными, и никакого выделения не требуется. «Удалить» - это отдельная история, но, учитывая формулировку вашей проблемы, вам все равно это не нужно.

Answer 5

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

struct cvector {
  rectangle** array_;
  int size_;
  int allocation_;
};

array_ будет содержать внутренний массив указателей на прямоугольники, size_ будет содержать общее количество допустимых прямоугольников в векторе, а выделение - это то, сколько места занимаетвыделено для массива_ в настоящее время.Некоторые примеры объявлений вспомогательных функций, которые вы можете написать для работы с этим:

int cvector_push_back(rectangle* rec);
rectangle* cvector_access(int index);
cvector* cvector_create();
int cvector_free(cvector* cv);

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