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 missing something obvious?
Chris
19  4365 
"chris" <ch***@bubblesc ope.net> wrote in message
news:cl******** **@pump1.york.a c.uk... 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 missing something obvious?
Chris
There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn't
store the elements in a continuous memory block, like vectors, but in linked
blocks. This means that it doesn't reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
br/
Catalin
Catalin Pitis wrote: There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn't
store the elements in a continuous memory block, like vectors, but in
linked blocks. This means that it doesn't reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
Herb Sutter recommends deque as the default container without a reason to
use another.
New questions:
Is deque more time efficient than vector? Is it more memory efficient than
list?
deque sounds similar to a data structure which I'l call "Rope". That's
designed for extra long and highly dynamic strings. When you insert a
character into the middle of the block, Rope might split the block, and
might put the new character into the lower block, with a reserved area after
the character, anticipating more. This naturally tunes for editors.
Does deque split blocks like that at insert time?
Block splitting requires eventual heap compaction. How could deque support
that? (Custom memory allocators need not apply!)
--
Phlip http://industrialxp.org/community/bi...UserInterfaces
Catalin Pitis wrote: "chris" <ch***@bubblesc ope.net> wrote in message
news:cl******** **@pump1.york.a c.uk...
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 missing something obvious?
Chris
There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn't
store the elements in a continuous memory block, like vectors, but in linked
blocks. This means that it doesn't reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
I've read claims that a deque can do constant time insertions at the
beginning and end and constant time random access. However is possible
to satisfy both of these requirements. I suspect that the insertions at
the beginning and end are only required to be amortized constant time?
If constant time random access is to be achieved, then we can't simply
be using a list of blocks else accessing an arbitary element would be
linear?
Chris
In message <cl**********@p ump1.york.ac.uk >, chris
<ch***@bubblesc ope.net> writes 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 missing something obvious?
What happens when you repeatedly pop from one end until one of the two
vectors is empty?
--
Richard Herring
Richard Herring wrote: In message <cl**********@p ump1.york.ac.uk >, chris
<ch***@bubblesc ope.net> writes
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 missing something obvious?
What happens when you repeatedly pop from one end until one of the two
vectors is empty?
Ah yes, I see your point. If you get pushing on one and and popping from
the other, then one of the two vectors would continue to grow bigger and
bigger over time while the deque remained the same size (I'm assuming in
this situation this kind of pushing on one end, popping off the other
should take a vaguely constant amount of memory, although I'm not
convinced the standard is clear about that requirement).
However, whenever we have to resize one of the vectors, then we could
take the opportunity to do a rebalancing between the two vectors, which
could take twice as long as just resizing one vector, but would still
have the same complexity I believe (although I would have to think about
it..)
Chris
Phlip wrote: Herb Sutter recommends deque as the default container without a reason to
use another.
New questions:
Is deque more time efficient than vector? Is it more memory efficient than
list?
TC++PL 3 has a table of container comparison on page 464 (17.1.2).
From that table:
[] list front back Iterators
operations operations operations
vector const O(n)+ const+ Ran
deque const O(n) const const Ran
"In the iterators column, Ran means random-access iterator and Bi means
bidirectional iterator; the operations for a bidirectional operator are
a subset of those of a random-access iterator (19.2.1).
Other entries are measures of the efficiency of the operations. A const
entry means the operation takes an amount of time that does not depend
on the number of elements in the container. Another conventional
notation for constant time is O(1). An O(n) entry means the entry takes
time proportional to the number of elements involved. A + suffix
indicates that occasionally a significant extra cost is incurred. For
example, inserting an element into a list has a fixed cost (so it is
listed as const), whereas the same operation on a vector involves moving
the elements following the insertion point (so it is listed as O(n)).
Occasionally, all elements must be relocated (so I added a +).
The "big O" notation is conventional. I added the + for the benefit of
programmers who care about predictability in addition to average
performance. A conventional term for O(n)+ is amortized linear time.
Naturally, if a constant is large it can dwarf a small cost proportional
to the number of elements. However, for large data structures const
tends to mean "cheap", O(n) to mean "expensive" , and O(log(n)) to mean
"fairly cheap". For even moderately large values of n, O(log(n)) is
closer to constant time than to O(n). People who care about cost must
take a closer look. In particular, they must understand what elements
are counted to get the n. No basic operation is "very expensive", that
is, O(n*n) or worse.
Except for string, the measures of costs listed here reflect
requirements in the standard. The string estimates are my assumptions.
These measures of complexity and cost are upper bounds. The measures
exist to give users some guidance as to what they can expect from
implementations . Naturally, implementers will try to do better in
important cases."
--
Ioannis Vranos http://www23.brinkster.com/noicys
chris wrote: I've read claims that a deque can do constant time insertions at the
beginning and end and constant time random access. However is possible
to satisfy both of these requirements. I suspect that the insertions at
the beginning and end are only required to be amortized constant time?
If constant time random access is to be achieved, then we can't simply
be using a list of blocks else accessing an arbitary element would be
linear?
Since it is a small paragraph, here is what TC++PL 3 says about deque:
"17.2.3 Deque
A deque (it rhymes with check) is a double-ended queue. That is, a deque
is a sequence optimized so that operations at both ends are about as
efficient as for a list, whereas subscripting approaches the efficiency
of a vector:
template <class T, class A = allocator<T> > class std: :deque {
// types and operations like vector (§16.3.3, §16.3.5, §16.3.6)
// plus front operations (§17.2.2.2) like list
}
;
Insertion and deletion of elements "in the middle" have vector-like
(in)efficiencie s rather than list-like efficiencies. Consequently, a
deque is used where additions and deletions take place "at the ends".
For example, we might use a deque to model a section of a railroad or to
represent a deck of cards in a game:
deque<car> siding_ no_ 3;
deque<Card> bonus;"
--
Ioannis Vranos http://www23.brinkster.com/noicys
On Thu, 21 Oct 2004 13:51:38 GMT, "Phlip" <ph*******@yaho o.com> wrote: Catalin Pitis wrote: There are some differences between vectors and deques. A deque is very
performant at front and back insertions (constant time). A deque doesn't
store the elements in a continuous memory block, like vectors, but in
linked blocks. This means that it doesn't reallocate memory when the the size
becomes greater than capacity (like in the case of a vector), but instead
allocates a new memory block and links it to the last block used.
Herb Sutter recommends deque as the default container without a reason to
use another.
I changed my mind a couple of years ago. Bjarne convinced me.
In C++ Coding Standards, due on bookstore shelves in the next two weeks,
you'll find the first three Items in the STL Containers section have
titles that begin with "use vector." In particular:
76. Use vector by default. Otherwise, choose an appropriate container.
77. Use vector and string instead of arrays.
78. Use vector (and string::c_str) to exchange data with non-C++ APIs. http://www.gotw.ca/publications/coding.htm
Herb
---
Herb Sutter ( www.gotw.ca) ( www.pluralsight.com/blogs/hsutter)
Convener, ISO WG21 (C++ standards committee) ( www.gotw.ca/iso)
Contributing editor, C/C++ Users Journal ( www.gotw.ca/cuj)
Architect, Developer Division, Microsoft ( www.gotw.ca/microsoft)
Ioannis Vranos wrote: Phlip wrote:
Herb Sutter recommends deque as the default container without a reason to
use another.
New questions:
Is deque more time efficient than vector? Is it more memory efficient
than
list?
TC++PL 3 has a table of container comparison on page 464 (17.1.2).
From that table:
[] list front back Iterators
operations operations operations
vector const O(n)+ const+ Ran
deque const O(n) const const Ran
Thanks, this explains my mistake. I thought that deque only guaranteed
const+ on front and back operations, but it offers the stronger
guarantee const.
This is slightly misleading, as all the implementations I've seen only
promise a const number of copy operations on elements of the deque. The
messing around with internal structures might still be const+ (ie
amorised constant time), and I believe this is unavoidable.
Chris This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: newsock |
last post by:
What differences between queue, deque and priority_queue? And under what
situations choose one of them to use? Thanks for your help!
|
by: Jenny |
last post by:
Hi,
I have a class foo which will construct some objects in my code. some
of the objects store int values into the data deque, while others
store float values to the deque.
template <class TYPE>
class foo
{
protected:
|
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: Dan Trowbridge |
last post by:
He everyone,
I am just getting started with .NET and I am having a porting problem.
I get and error in code that lookssomething like this (really stripped down
but you get the idea)...
class dt
{
std::deque< class dt > dtdq;
};
|
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: Robbie Hatley |
last post by:
I'm getting a strange warning at work when I compile any file in our
product that contains a deque of a particular struct. I don't understand
this warning, so I'm not sure if this is a Microsoft Windows issue, or
a C++ issue, so I'm posting it both to a Windows group and to a C++
group.
My OS is Windows 2000, and my compiler is Visual C++ 6.0.
The warning I'm getting is this:
|
by: yancheng.cheok |
last post by:
after reading http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp,
i realize that deque has its own speed advantage over vector in all the
aspect (except for memory deallocation). does it mean that we should
prefer deque over vector? (in contrast with c++ standard, which
recommence vector over deque)
thanks!
|
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: subramanian100in |
last post by:
In ISO/IEC 14882:2003 document, in the section '23.2.1.3 deque
modifiers', the following is mentioned:
iterator insert(iterator position, const T& x);
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator
last);
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
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: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
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: 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: 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
| | |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
