How do deques work?

This is a discussion on How do deques work? within the C++ Programming forums, part of the General Programming Boards category; This is the definition from visual studio .net 2003. The one that holds the items is this Code: typedef _POINTER_X(_Tptr, ...

  1. #31
    unleashed alphaoide's Avatar
    Join Date
    Sep 2003
    Posts
    696
    This is the definition from visual studio .net 2003.
    The one that holds the items is this
    Code:
    typedef _POINTER_X(_Tptr, _Alloc) _Mapptr;
    _Mapptr _Map;	// pointer to array of pointers to blocks
    And, yes, access time is amortized constant time, obvious from this definition below.
    Code:
    const_reference operator[](difference_type _Off) const
    {	// subscript
        return (*(*this + _Off));
    }
    And that concludes it.
    source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense

  2. #32
    Registered User
    Join Date
    Apr 2006
    Posts
    2,047
    Quote Originally Posted by hk_mp5kpdw
    Due to the way templated code is handled by most compilers, the code is probably not hidden in any sort of precompiled library. Just open up the deque header file and look at it, it's there for you to see in all its wondrous glory. It will show you everything you want to know in excrutiating detail. It's then just a matter of translating that into English (...or whatever language you speak) which may be quite difficult depending on your level of expertice in the matter.

    P.S. Don't ask me for any translation, I don't care, that's the beauty of the STL; as long as it works correctly and efficiently the internal workings don't matter. It's just that if you really want to know how it is implemented then the code is right there in front of you to look at.
    Trouble is, I can't find the file. I can find deque.h, but that just gives
    using std::deque; and includes <deque>. I'm using Dev C++4.9.9.2, so if anyone knows where to find it, that would help.

    @alphaoide
    Linked lists (such as STL the list container) have O(N) complexity for lookup and O(1) complexity for Insertion and deletion.
    The vector container has O(1) lookup and O(N) for insertion and deletion everywhere except for the end, where it has O(1) insertion and deletion.
    Deques have O(1) complexity lookup and O(N) insertion and deletion everywhere except the beginning and end which have O(1) complexity insertion/deletion.

    Each of these containers is different.
    Last edited by King Mir; 05-08-2006 at 11:36 AM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #33
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    A deque is often implemented as a series of fixed size arrays. Random access is constant time, like vector, although in practice it is a little slower than vector. A list, on the other hand, has linear time random access because it must walk the list.

    The reason you can constant time access from the deque is that you know the size of each array. Say for example, each array has a size of 20, and you have 105 elements in your deque that you added through push_back. The first pushed back item is added to the first array slot. The second comes right after it, and so on, until the 20th fills the first array. Then a second array is allocated somewhere else in memory (not contiguous), and its location is saved. Then the next 20 elements are added to it. This is done until you've added all 105 elements.

    Then, when you want to retrieve element number 77, you divide 77 by the array size and get 3, so element is in the 4th array (array position 3). Then you do a mod of 77 by the array size, and get 17, so the element is at index 16 in the 4th array. (Ignore the seemingly incorrect math.) All that division and modulus is considered O(1), or constant time, since it doesn't depend on the number of elements in the container. That is how you get constant time random access without a contiguous array.

    That is also why adding to the front or back of the deque is "fast", because you can always add another array to the front or back of the set of arrays without every having to reallocate space for the whole container like vector does.

  4. #34
    Registered User
    Join Date
    Apr 2006
    Posts
    2,047
    @Daved

    So how is the series stored? How are the segments linked together?

    I take it that there is some kind of array of pointers to segments, but how does such an "array" ensure adding segments to the beginning is just as easy as adding them to the end?
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #35
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    Good question. I was wondering that myself, and I don't know the exact answer, so I didn't mention it.

    I'm sure there are ways, though. I would probably use another "master" array that held the pointers to the data arrays, and start filling it from the middle. If that array filled up to its end or its beginning, then allocating space for a new master array wouldn't stop it from being a constant time operation. I'd probably have an index or pointer to the first valid element in the master array, an index or pointer to the first valid element in the first data array, and the total number of elements stored. From that you can quickly get to any element or add a new one easily.

  6. #36
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    Quote Originally Posted by King Mir
    Trouble is, I can't find the file. I can find deque.h, but that just gives
    using std::deque; and includes <deque>. I'm using Dev C++4.9.9.2, so if anyone knows where to find it, that would help.
    You can find all the actual includes in your
    Code:
    /Dev-Cpp/include/C++/<version number>/
    directory. Now, keep in mind, these don't have .h extensions, as their included counterparts (like #include <deque>). If you look in those "files", you'll see they include .h libraries in the
    Code:
    /Dev-Cpp/include/C++/<version number>/bits/
    directory. The one you're looking for of course is stl_deque.h

    A word of advice. While the logic is not too complicated if you understand Object Oriented Programming, whoever wrote this library for MingGW has a disturbing idea of what a good identifier is and it makes the code very hard to read. An example:
    Code:
          void
          push_front(const value_type& __x)
          {
    	if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
    	  {
    	    std::_Construct(this->_M_impl._M_start._M_cur - 1, __x);
    	    --this->_M_impl._M_start._M_cur;
    	  }
    	else
    	  _M_push_front_aux(__x);
          }
    I suppose the logic of making them riddled with underscores is so they never interfere with the identifiers in the code that uses the standard libraries. Anyway, enjoy.
    Last edited by SlyMaelstrom; 05-08-2006 at 01:07 PM.
    Sent from my iPadŽ

  7. #37
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    whoever wrote this library for MingGW has a disturbing idea of what a good identifier is and it makes the code very hard to read.
    ...
    I suppose the logic of making them riddled with underscores is so they never interfere with the identifiers in the code that uses the standard libraries.
    Well, the writer was writing the implementation, so he/she had the right (duty?) to use identifiers reserved to the implementation.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #38
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    There are lots of things I have the "right" to do, but out of respect to others, I probably shouldn't.

    I'm sure the standard has a certain template for declaring identifiers in standard libraries, but I mean, if they didn't... what the author did is just plain rude to our eyes. Though more than likely kind to our code.
    Sent from my iPadŽ

  9. #39
    Registered User
    Join Date
    Jan 2005
    Posts
    7,328
    Actually, those identifiers are much easier to read than some from some other standard library implementations I've seen. I've seen identifiers that are all an underscore followed by one or two letters: if (_Mi._Mx._B != _Mi._Mx._Bs).

  10. #40
    Registered User
    Join Date
    Apr 2006
    Posts
    2,047
    Quote Originally Posted by SlyMaelstrom
    You can find all the actual includes in your
    Code:
    /Dev-Cpp/include/C++/<version number>/
    directory. Now, keep in mind, these don't have .h extensions, as their included counterparts (like #include <deque>). If you look in those "files", you'll see they include .h libraries in the
    Code:
    /Dev-Cpp/include/C++/<version number>/bits/
    directory. The one you're looking for of course is stl_deque.h
    Thanks. I found what I was looking for .
    If anyone is interested here is the Quote. Apparently it uses a master array of pointers that is filled from the middle, and resized as it gets full.

    /**
    * @brief A standard container using fixed-size memory allocation and
    * constant-time manipulation of elements at either end.
    *
    * @ingroup Containers
    * @ingroup Sequences
    *
    * Meets the requirements of a <a href="tables.html#65">container</a>, a
    * <a href="tables.html#66">reversible container</a>, and a
    * <a href="tables.html#67">sequence</a>, including the
    * <a href="tables.html#68">optional sequence requirements</a>.
    *
    * In previous HP/SGI versions of deque, there was an extra template
    * parameter so users could control the node size. This extension turned
    * out to violate the C++ standard (it can be detected using template
    * template parameters), and it was removed.
    *
    * @if maint
    * Here's how a deque<Tp> manages memory. Each deque has 4 members:
    *
    * - Tp** _M_map
    * - size_t _M_map_size
    * - iterator _M_start, _M_finish
    *
    * map_size is at least 8. %map is an array of map_size pointers-to-"nodes".
    * (The name %map has nothing to do with the std::map class, and "nodes"
    * should not be confused with std::list's usage of "node".)
    *
    * A "node" has no specific type name as such, but it is referred to as
    * "node" in this file. It is a simple array-of-Tp. If Tp is very large,
    * there will be one Tp element per node (i.e., an "array" of one).
    * For non-huge Tp's, node size is inversely related to Tp size: the
    * larger the Tp, the fewer Tp's will fit in a node. The goal here is to
    * keep the total size of a node relatively small and constant over different
    * Tp's, to improve allocator efficiency.
    *
    * **** As I write this, the nodes are /not/ allocated using the high-speed
    * memory pool. There are 20 hours left in the year; perhaps I can fix
    * this before 2002.
    *
    * Not every pointer in the %map array will point to a node. If the initial
    * number of elements in the deque is small, the /middle/ %map pointers will
    * be valid, and the ones at the edges will be unused. This same situation
    * will arise as the %map grows: available %map pointers, if any, will be on
    * the ends. As new nodes are created, only a subset of the %map's pointers
    * need to be copied "outward".
    *
    * Class invariants:
    * - For any nonsingular iterator i:
    * - i.node points to a member of the %map array. (Yes, you read that
    * correctly: i.node does not actually point to a node.) The member of
    * the %map array is what actually points to the node.
    * - i.first == *(i.node) (This points to the node (first Tp element).)
    * - i.last == i.first + node_size
    * - i.cur is a pointer in the range [i.first, i.last). NOTE:
    * the implication of this is that i.cur is always a dereferenceable
    * pointer, even if i is a past-the-end iterator.
    * - Start and Finish are always nonsingular iterators. NOTE: this means that
    * an empty deque must have one node, a deque with <N elements (where N is
    * the node buffer size) must have one node, a deque with N through (2N-1)
    * elements must have two nodes, etc.
    * - For every node other than start.node and finish.node, every element in
    * the node is an initialized object. If start.node == finish.node, then
    * [start.cur, finish.cur) are initialized objects, and the elements outside
    * that range are uninitialized storage. Otherwise, [start.cur, start.last)
    * and [finish.first, finish.cur) are initialized objects, and [start.first,
    * start.cur) and [finish.cur, finish.last) are uninitialized storage.
    * - [%map, %map + map_size) is a valid, non-empty range.
    * - [start.node, finish.node] is a valid range contained within
    * [%map, %map + map_size).
    * - A pointer in the range [%map, %map + map_size) points to an allocated
    * node if and only if the pointer is in the range
    * [start.node, finish.node].
    *
    * Here's the magic: nothing in deque is "aware" of the discontiguous
    * storage!
    *
    * The memory setup and layout occurs in the parent, _Base, and the iterator
    * class is entirely responsible for "leaping" from one node to the next.
    * All the implementation routines for deque itself work only through the
    * start and finish iterators. This keeps the routines simple and sane,
    * and we can use other standard algorithms as well.
    * @endif
    */
    Quote Originally Posted by SlyMaelstrom
    A word of advice. While the logic is not too complicated if you understand Object Oriented Programming, whoever wrote this library for MingGW has a disturbing idea of what a good identifier is and it makes the code very hard to read. An example:
    Code:
          void
          push_front(const value_type& __x)
          {
    	if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
    	  {
    	    std::_Construct(this->_M_impl._M_start._M_cur - 1, __x);
    	    --this->_M_impl._M_start._M_cur;
    	  }
    	else
    	  _M_push_front_aux(__x);
          }
    I suppose the logic of making them riddled with underscores is so they never interfere with the identifiers in the code that uses the standard libraries. Anyway, enjoy.
    It's the same for me so it must be standard.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  11. #41
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,069
    Quote Originally Posted by King Mir
    It's the same for me so it must be standard.
    Actually it's the same for you because we're looking at the exact same implementation on the exact same compiler. Try a different one.

    Glad you found your answer.
    Sent from my iPadŽ

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. getline() don't want to work anymore...
    By mikahell in forum C++ Programming
    Replies: 7
    Last Post: 07-31-2006, 10:50 AM
  2. Why don't the tutorials on this site work on my computer?
    By jsrig88 in forum C++ Programming
    Replies: 3
    Last Post: 05-15-2006, 10:39 PM
  3. help getting program to work
    By jlmac2001 in forum C Programming
    Replies: 2
    Last Post: 11-13-2002, 10:04 PM
  4. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 11:39 AM
  5. DLL __cdecl doesnt seem to work?
    By Xei in forum C++ Programming
    Replies: 6
    Last Post: 08-21-2002, 04:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21