Which structure is best for implementation when the number of elements in a list/array is variable?

I have a slightly specific question. I am using C/C++ with OpenCV. My aim to store detected rectangles in a list/array style structure. However, the length is variable for every frame (iteration).

What should I use to store this info? I thought of Linked Lists, however, they are slow to traverse and also if the number of nodes decrease, I will have to manually delete the extra nodes which would take up even more processor time. I discarded Arrays as they are not very flexible in 开发者_开发百科terms of their length. I can do dynamic arrays with malloc but even with that I think I will need to specify the maximum number of elements.

feel free to correct me if i'm wrong somewhere. Also please do share your views and let me know what you think is the best way to go about this?

Thanks

EDIT: I'm not restricted to C (i know i mentioned malloc). I can use C++ features as well as the rest of my program does not use any C specific functions. So do feel free to suggest me any better ways.

---

I would recommend you to use std::vector. The elements in a std::vector are guaranteed by the C++ Standard to be contiguous, just like a C array would be. This allows std::vector to be the interface between C++ data structures and C functions. You can use std::vector<T>::resize to make sure there is space allocated before passing it to the OpenCV functions.

Oh, to get a pointer to the internal storage of the vector you typically use this notation: &rectangleCollection[0].

Good luck!

---

You can do dynamic arrays and use realloc() when it needs to grow. If possible:

• Since your initial array to be (perhaps) the average length you expect
• Use exponential growth, so that when you do reallocate the array, you double the allocated size

Of course, you could also do something more intricate, but I would recommend testing with plain reallocated arrays first.

---

Typically, you would free an extant array of maximum size and then allocate a new array of larger size and assign the original pointer to the new array. Also, there's no need or reason to downsize your array just because you're not filling it, if you know that in the future you may well need more space. It's a waste of performance constantly resizing your data structures to be an exact fit for the data within them.

Edit: Oh, so you ARE actually using C++. In that case, just get a vector.

---

If you would like to use vectors because of their flexibility, but are restricted to C, you can easily replicate their behavior using structs and supporting functions. Here is an example definition for a C vector:

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

array_ would hold the internal array of pointers to rectangles, size_ would hold the total number of valid rectangles within the vector, and allocation is how much space is allocated for array_ currently. Some example declarations of helper functions you might write to work with this:

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

If you stick to your interface when accessing it, you should be able to get the same functionality of a vector without much work.

---

The answer depends:

Generally I would recommend CGrowableArray found in the DirectX SDK. (You don't need to include DirectX, just rip out that class template) (If you don't want to use a C++ class template , you can easily implement the same logic as a bunch of C functions)

What benefit does it have over a std::vector?

a) It allocates objects head of time, using a heuristic

b) You can Reset() it, which will only destroy the contained objects but not free the memory.

Each frame you Reset() the array, then happily add your objects. You only pay for ctor/dtor calls, but (most times) not for alloc/free calls.

---

On the other hand, if you're not going to store actual objects but pointers, an intrusive linked list is ideal. In that case, both "Append" (2 assignments) and "Clear" (1 assignment) are trivial and no allocation is involved whatsoever. "Remove" is a different story, but given your problem statement you don't seem to have a need for that anyway.