According to SGI's STL reference, a deque:
Supports amortized constant time random access (like a vector)
Allows amortized constant time insertions at the beginning and end
One way you could implement this would be to allocate a chunk of memory
and start in the middle rather than in the beginning, but then deque
would have a reserve() function. So how is deque usually implemented?
Thanks,
-Peter 3 7992
Peter Ammon wrote: According to SGI's STL reference, a deque:
Supports amortized constant time random access (like a vector) Allows amortized constant time insertions at the beginning and end
One way you could implement this would be to allocate a chunk of memory and start in the middle rather than in the beginning, but then deque would have a reserve() function. So how is deque usually implemented?
No, it is usually an array of arrays. One end grows from 0 to x and the
other grows from x to 0.
......<=
=======
=======
=>.....
Jonathan
Jonathan Mcdougall wrote: Peter Ammon wrote: According to SGI's STL reference, a deque:
Supports amortized constant time random access (like a vector) Allows amortized constant time insertions at the beginning and end
One way you could implement this would be to allocate a chunk of memory and start in the middle rather than in the beginning, but then deque would have a reserve() function. So how is deque usually implemented?
No, it is usually an array of arrays. One end grows from 0 to x and the other grows from x to 0.
.....<= ======= ======= =>.....
Thanks for your reply, but I am still confused. How do you manage this
array of subarrays? You need the ability to insert a subarray at
either end with good performance to maintain the deque's performance
contract. What data structure allows you to insert stuff at either end
with good performance? A deque, of course. You can see my confusion.
To put it another way: Let's say a deque is a naive array of arrays;
how long is each of these subarrays? If each is a fixed length, say,
L, then inserting L elements into the beginning of a deque of N
elements will require allocating a new subarray, moving every subarray
pointer in the outer array forward by one, and then inserting the new
subarray at the beginning. That second step requires you to copy N/L
pointers to insert L elements; the work per element is therefore
N/L**L, which is O(N). But a deque is supposed to have O(1)
insertions.
-Peter
On 2005-11-17, Peter Ammon <pa****@gmail.c om> wrote: Jonathan Mcdougall wrote: Peter Ammon wrote: > According to SGI's STL reference, a deque: > > Supports amortized constant time random access (like a vector) > Allows amortized constant time insertions at the beginning and end > > One way you could implement this would be to allocate a chunk of memory > and start in the middle rather than in the beginning, but then deque > would have a reserve() function. So how is deque usually implemented? No, it is usually an array of arrays. One end grows from 0 to x and the other grows from x to 0.
.....<= ======= ======= =>.....
Thanks for your reply, but I am still confused. How do you manage this array of subarrays? You need the ability to insert a subarray at either end with good performance to maintain the deque's performance contract. What data structure allows you to insert stuff at either end with good performance? A deque, of course. You can see my confusion.
To put it another way: Let's say a deque is a naive array of arrays; how long is each of these subarrays? If each is a fixed length, say, L, then inserting L elements into the beginning of a deque of N elements will require allocating a new subarray, moving every subarray pointer in the outer array forward by one, and then inserting the new subarray at the beginning.
Yes, and the memory will be allocated in such a way that this
seldom happens, as with a vector.
That second step requires you to copy N/L pointers to insert L elements; the work per element is therefore N/L**L, which is O(N). But a deque is supposed to have O(1) insertions.
O(1) amortized time. I think that's how they put it. Memory
allocation won't have to take place very often with a good
implementation.
A good and simple approach doubles the size whenever capacity
fills up. Starting from zero capacity, it requires only 14
allocations for 10000 calls to push_front. So log2(N) times out
of N, performance is O(N). That's a very small ratio.
--
Neil Cerutti This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: chris |
last post by:
Hello,
I've recently been trying to understand the various structures supplied
by c++, and the one I find most confusing is deque.
One quick question about this. It seems most implementations of deque
are quite complex. Why couldn't I implement deque with a couple of
vectors V,W where the deque is the element of V in reverse order
followed by W? This would appear to me to satisfy all the conditions,
and be significantly simpler. Am I...
|
by: R.Z. |
last post by:
i was wondering whether it pays off in terms of memory use to maintain lots
of empty deques (it would be convenient for my algorithms but memory use is
more important). and does the size of a deque depends on the size of its
members even if the deque is empty? is there at all a way to check out how
much memory my deque occupies? i've read that the sizeof operator cannot be
used with dynamically allocated arrays so i figured it wouldn't give...
|
by: Russell Warren |
last post by:
Does anyone have an easier/faster/better way of popping from the middle
of a deque than this?
class mydeque(deque):
def popmiddle(self, pos):
self.rotate(-pos)
ret = self.popleft()
self.rotate(pos)
return ret
|
by: toton |
last post by:
Hi,
I am looking for a circular buffer solution ( a fixed buffer) , where
the elements can be pushed back & removed front. It looks stl deque
can be a solution. my question is,
1) circular buffer is random access? (i.e implemented over array and
not linked list)
2) if I reserve the required space & do push_back & remove_front so
that total memory doesn't exceed the reserved amount, will the internal
pointers will wrap, or the memory...
|
by: DevNull |
last post by:
Hello everyone,
I decided to pick c++ back up after not really having used it much in
10 years.
Just as a point of refference, there was no standard C++ last time I
used regularly.
Anyways coming back, I've fallen in love with all the improvements in
the language such as the STL. Congrats to anyone who worked on it,
you did an excellent job.
| |
by: Juha Nieminen |
last post by:
I'm sure this is not a new idea, but I have never heard about it
before. I'm wondering if this could work:
Assume that you have a common base class and a bunch of classes
derived from it, and you want to make a deque which can contain any
objects of any of those types. Normally what you would have to do is to
make a deque or vector of pointers of the base class type and then
allocate each object dynamically with 'new' and store the...
|
by: t |
last post by:
The stack container adaptor uses deque as its default underlying
sequential container. I don't understand why since we only add
elements and remove elements from one side of a stack. Why isn't the
default vector instead? For that matter, why not list since we don't
access elements in the middle of the stack? I don't know if it's
necessary (and don't see that it is) to do so in the implementation of
stack.
Separate question: vector...
|
by: Donos |
last post by:
Hello
I have the following declaration in my code,
******************************************************************
struct mHandleObj
{
HANDLE h;
};
|
by: NvrBst |
last post by:
I've read a bit online seeing that two writes are not safe, which I
understand, but would 1 thread push()'ing and 1 thread pop()'ing be
thread-safe? Basically my situation is the follows:
--Thread 1--
1. Reads TCPIP Buffer
2. Adds Buffer to Queue (q.size() to check queue isn't full, and
q.push_back(...))
3. Signals Reading Thread Event & Goes Back to Wait for More Messages
on TCPIP
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
| |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |