0

Following from this here.

I am wondering how containers that are non-contiguous and are not linked lists actually know where to find the next element given that it is not guaranteed to come right after this element? Is there an extra table saying the first x chunks of the deque are located at this starting point, the next y chunks are starting over there, and so on?

Community
  • 1
  • 1
chrise
  • 4,039
  • 3
  • 39
  • 74
  • 2
    The iterator class holds enough information to know how to find the next element. For example, one way the deque iterator could work is to hold a pointer to the current "block" and also hold an index selecting an item in the block. – M.M Apr 10 '17 at 05:25
  • In general an iterator can some reference to the container (or some part of it) so it can access the internal information about the container. – Michael Burr Apr 10 '17 at 05:28
  • @M.M my question was aimed at explaining how it knows where the different blocks are. – chrise Apr 10 '17 at 06:12
  • Thanks Michael, I guess I actually should have asked how deques themselves store that information. So, following from your answer, my guess is every deque has a table with the location of all its blocks? And iterators have access to that list? – chrise Apr 10 '17 at 06:21
  • @chrise - Yes, one implementation for a deque iterator could be an iterator into the "block table" and an index or pointer into the current block. – Bo Persson Apr 10 '17 at 06:42
  • One way would be a linked list of blocks, so it would just look at the current block's "next" pointer in that case – M.M Apr 10 '17 at 07:05
  • Thanks for the info – chrise Apr 10 '17 at 07:06
  • Here's an explanation of how a `deque` might be implemented: http://stackoverflow.com/a/6292437/12711 – Michael Burr Apr 10 '17 at 08:13
  • good explanation, ty – chrise Apr 10 '17 at 09:08

1 Answers1

0

The container keeps necessary information internally for direct access to elements as the internal implementation of deque is basically a double ended queue of chunks(vectors). Each chunks has elements indexed,once the chunk is full,another chunk is added maintaining the integrity of indexing and the container class keeps information it needs to provide access,locating the correct chunk and thereafter the indexed location of the element sought.

You can read the great article here which would provide all the knowledge you seek and even more than what you seek: https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container

Also to see a brief implementation of deque,you can go through the accepted answer on stack overflow What really is a deque in STL?

Community
  • 1
  • 1
Valgrind1691
  • 182
  • 1
  • 11