This is the definition from visual studio .net 2003.
The one that holds the items is this
And, yes, access time is amortized constant time, obvious from this definition below.Code:typedef _POINTER_X(_Tptr, _Alloc) _Mapptr; _Mapptr _Map; // pointer to array of pointers to blocks
And that concludes it.Code:const_reference operator[](difference_type _Off) const { // subscript return (*(*this + _Off)); }
source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense
Trouble is, I can't find the file. I can find deque.h, but that just givesOriginally 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.
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.
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.
@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.
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.
You can find all the actual includes in yourdirectory. 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 theCode:/Dev-Cpp/include/C++/<version number>/directory. The one you're looking for of course is stl_deque.hCode:/Dev-Cpp/include/C++/<version number>/bits/
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: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.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); }
Last edited by SlyMaelstrom; 05-08-2006 at 01:07 PM.
Sent from my iPadŽ
Well, the writer was writing the implementation, so he/she had the right (duty?) to use identifiers reserved to the implementation.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.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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Ž
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).
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
*/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.
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Ž
