No it isn't. In fact a C++ vector is implemented as an array, and yet can hold a variable number of items. It simply creates a larger vector when the original one fills to capacity, and copies everything over to the new larger one.
Originally Posted by bennyboy
No need to declare a static array and 'bodge' it when you can use a dynamic array.
(I don't want to bodge it by making a massive array and hoping its OK - unless this is the best option in your opinions).
The above technique used by a vector has zero per item memory usage overhead, and has amortised constant time overhead per insertion, meaning that it is indeed very fast.
I only want each identity to have 3 entries in the list, any more and I don't want them added. The most important aspect of this is that it is fast and low on memory requirements.
No it doesn't, for the same reasons as mentioned earlier. A std::tr1::hashmap uses a hash table, and yet can hold a variable number of items.
Here are my ideas on how to implement:
1) Use a hash table - no good as this requires a set size of the list from the beginning.
In that case you have a very limited knowledge of data structures. For starters, as binary tree might be a sensible option. There are many different kinds of binary trees too, and there are other structures such as skip-lists, that would be appropriate.
2) Use a linked list where each element contains an array of 3 containing the details of each entry with the same identity.
I think the linked list idea (2) is the only way of doing it due to the variable size,
Use a self-balancing binary-tree of small 3-item lists or arrays.
but this means that each time I want to add a new entry to the list I have to search through the whole list to check for previous identical entries - unlike the hash table where I can key straight to it.
Basically, I would like some advice on what's the best option, or if there's a better way of doing this?
Even better, if you're programming in Windows, look into the VirtualAlloc function.