-2

I was looking to implementing a c++ container object with following properties:

  1. Keeps all the elements contiguously in memory, so that it can be iterated over without causing any cache misses.
  2. Expandable, not like arrays which are of a fixed sized, but much like vectors in stl which can adjust the memory allocated to accommodate as many elements as i add.
  3. Does not reallocate elements to new place in memory when resizing like in the case of std vectors. I need to keep pointers to the elements that are in the container, so reallocation the pointers should not be invalidated when adding new elements.
  4. Must be compatible with ranged based for loops, so that the contents can be efficiently iterated through.

Is there any container out there which meets these requirements, in any external library or do i have to implement my own in this case?

As some comments have pointed out, not all the desired properties can be implemented together. I had ought over this, and i have an implementation in mind. Since making things contiguous entirely is not possible, some discontinuity can be accomodated. For example, the data container allocates space for 10 elements initially, and when the cap is reached, allocates another chunk of memory double the amount of the previous block, but doesn't copy the existing elements to that new block. Instead, it fills the new block with the new elements i put into it. This minimizes the amount of discontinuity.

So, is there a data structure which already implements that?

Lalit Kumar B
  • 47,486
  • 13
  • 97
  • 124
The Light Spark
  • 504
  • 4
  • 19

1 Answers1

3

IMHO, the data-structure that is the closest from your need is the deque in the STL. Basically it stores chunk of contiguous memories and provides both random access iterators and stability regards to push_back (your elements stays at the same place although iterators are invalidated). The only problem with your constrains is that the memory is not contiguous everywhere but as others commented, your set of needs is incompatible if you want to fully satisfy them all. By the way one sweet thing with this container is that you can also push on the front.

geoalgo
  • 678
  • 3
  • 11
  • Yes, a deque seems very close, but as from the understanding of deques, which i got from reading http://msdn.microsoft.com/en-us/library/t4x090h4.aspx, the size of each block is fixed. Do you know of any data structure that behave like a deque, but the size of the blocks increase exponentially? – The Light Spark Nov 29 '14 at 13:27
  • I meant this link, not that: http://cpp-tip-of-the-day.blogspot.in/2013/11/how-is-stddeque-implemented.html – The Light Spark Nov 29 '14 at 13:34
  • 1
    No, I dont... but having both random access iterators and different block size seems difficult. – geoalgo Nov 29 '14 at 13:53
  • I could do away with random access really. Is there a way i can specify what this fixed size was? – The Light Spark Nov 29 '14 at 13:54
  • @TheLightSpark: vectors grow exponentially in order to amortise the reallocation time. Why would you need that for a deque? – Oliver Charlesworth Nov 29 '14 at 13:54
  • Apparently, from the author of the GNU implementation it used to be but was removed because it violated standard (http://stackoverflow.com/questions/5728359/stl-internals-deque-implementation). – geoalgo Nov 29 '14 at 13:59
  • 1
    @OliverCharlesworth one use would be I guess to ensure that some blocks (of a given size) are stored contiguously if their content is accessed at the same time. – geoalgo Nov 29 '14 at 14:02