Is my understanding of containers valid?

[Simon]

Hi,

I understand what one the differences between std::vector, std::deque and
std::list is,
the std::vector can have data inserted/deleted at the end.
The std::deque can have data inserted/deleted at the end and at beginning
and the std::list can have data inserted/deleted anywhere.

But how can those differences be physically understood?

If I understand correctly a std::vector with 3 items has data placed one
after the other.
V[0]V[1]V[2]
if I add another item it becomes, V[0]V[1]V[2]V[3]
and if a delete item V[2] the data is moved to remain one after the other,
V[0]V[1]V[3]
Because of the moving of data the item is slower.

With std::deque we can insert data at the front of the block, but how is
that different from std::vector, I mean the data has to be moved the same
way.
The only difference is that it is slower because when you insert data V[x]
you need to move the whole memory block V[x]V[0]V[1]V[2]

And finally the std::list is the same as a std::vector but all items are
pointers to the actual element so if I insert an element all I need to do is
to add it at the end of the block of memory and place the address of that
element is an ordered list of pointers. so if I have 3 elements
V[0]V[1]V[2]

the address will have the correct order A[0] = &V[2], A[1] = &V[0] and A[2]
= &V[1].
That way I can sort items or add and delete them.
The items in the list don't need to be one after the other really as the
address is ordered.

Is my understanding of containers correct?

If my understanding is correct why even bother about using std::vector and
std::deque, std::list seems to do the job ok.

Many thanks.

Simon

 

[Mark P]

Hi,

I understand what one the differences between std::vector, std::deque and
std::list is,
the std::vector can have data inserted/deleted at the end.

You can insert/delete anywhere, however it's only guaranteed O(1)
(amortized) if you do so at the end.

The std::deque can have data inserted/deleted at the end and at beginning

Again, you can insert/delete anywhere, but it's amortized O(1) at the
beginning and end only.

and the std::list can have data inserted/deleted anywhere.

But how can those differences be physically understood?

If I understand correctly a std::vector with 3 items has data placed one
after the other.
V[0]V[1]V[2]
if I add another item it becomes, V[0]V[1]V[2]V[3]
and if a delete item V[2] the data is moved to remain one after the other,
V[0]V[1]V[3]
Because of the moving of data the item is slower.

With std::deque we can insert data at the front of the block, but how is
that different from std::vector, I mean the data has to be moved the same
way.
The only difference is that it is slower because when you insert data V[x]
you need to move the whole memory block V[x]V[0]V[1]V[2]

You're making assumptions about implementation details. Front insertion
into a deque is amortized O(1)-- how the implementation manages that is
arbitrary provided it satisfies the requirements on the container.

And finally the std::list is the same as a std::vector but all items are
pointers to the actual element so if I insert an element all I need to do is
to add it at the end of the block of memory and place the address of that
element is an ordered list of pointers. so if I have 3 elements
V[0]V[1]V[2]

the address will have the correct order A[0] = &V[2], A[1] = &V[0] and A[2]
= &V[1].
That way I can sort items or add and delete them.
The items in the list don't need to be one after the other really as the
address is ordered.

Is my understanding of containers correct?

If my understanding is correct why even bother about using std::vector and
std::deque, std::list seems to do the job ok.

For one thing a vector provides random access iterators which means,
among other things, you can get from any element to any other element in
constant time. The speed of random access vs. the speed of random
insertion is really the canonical distinction between a vector and a
list. There are also certain STL algorithms which require random access
iterators. Also from a pracitcal point of view, lists have some
overhead due to the additional pointers needed to track the list structure.

Mark

 

[Victor Bazarov]

I understand what one the differences between std::vector, std::deque
and std::list is,
the std::vector can have data inserted/deleted at the end.

std::vector can have data inserted at any position.

The std::deque can have data inserted/deleted at the end and at

Same thing, std::deque you can insert anywhere.

beginning and the std::list can have data inserted/deleted anywhere.
Yes.

But how can those differences be physically understood?

There are no differences.

If I understand correctly [...]

You don't.

Is my understanding of containers correct?
No.

If my understanding is correct why even bother about using
std::vector and std::deque, std::list seems to do the job ok.

Your understanding is incorrect. Get a better book.

V

 

[Simon]

If my understanding is correct why even bother about using

Your understanding is incorrect. Get a better book.

V

wow, thanks for your help!

I hope you achieve the post count you are after this month.

Simon

 

[Simon]

You can insert/delete anywhere, however it's only guaranteed O(1)
(amortized) if you do so at the end.


Again, you can insert/delete anywhere, but it's amortized O(1) at the
beginning and end only.

So all three are the same then?
I just cannot get my head around the actual differences between the 3
containers.

You're making assumptions about implementation details. Front insertion
into a deque is amortized O(1)-- how the implementation manages that is
arbitrary provided it satisfies the requirements on the container.

So what you are saying is that the standard does not care how the containers
are implemented as long as they follow the rules, (standards)?
but I don't really seem to find anywhere a definition of vector, deque and
list that would explain the difference(s) for all three.

For one thing a vector provides random access iterators which means, among
other things, you can get from any element to any other element in
constant time. The speed of random access vs. the speed of random
insertion is really the canonical distinction between a vector and a list.
There are also certain STL algorithms which require random access
iterators. Also from a pracitcal point of view, lists have some overhead
due to the additional pointers needed to track the list structure.

Mark

Simon

 

[Mark P]

So all three are the same then?
I just cannot get my head around the actual differences between the 3
containers.

The containers have some common functionality and anything you can do
with one can in principle (but perhaps not easily or efficiently) be
done with the other. For particular tasks however it is often the case
that one is preferable to another.

So what you are saying is that the standard does not care how the containers
are implemented as long as they follow the rules, (standards)?
but I don't really seem to find anywhere a definition of vector, deque and
list that would explain the difference(s) for all three.

As long as an implementation behaves in accordance with the
specifications of the standard, then it is a compliant implementation.
Seems sort of obvious, doesn't it?

There are numerous detailed references on the definitions of standard
library elements, including the containers you mention.

http://www.sgi.com/tech/stl/table_of_contents.html
http://www.dinkumware.com/refxcpp.html

 

[Axter]

If my understanding is correct why even bother about using std::vector and
std::deque, std::list seems to do the job ok.

The main difference is in efficiency.
For most code requirement, the std::vector is the most efficient, and
that's why it's recommended by the C++ standard as the default
container.

std::vector is also compatible to C-Arrays in that it has a contiguous
memory, IAW second addition of the C++ standards.

You should only consider using std::list if you're doing many inserts
and or deletions from the center of the container.

Otherwise use vector or deque.

 

[John Carson]

wow, thanks for your help!

I hope you achieve the post count you are after this month.

Simon

Victor actually gives very good advice, even if it is not diplomatically
worded.

As others have pointed out, the C++ standard doesn't generally say how these
containers are to be implemented, it merely says how they must behave.
However, the containers generally are implemented in particular ways. To
understand these, you need a texbook that discusses data structures; it is
difficult to describe them in the short space appropriate to a newsgroup
post.

vectors are basically class wrappers around arrays, lists are class wrappers
around "doubly linked lists", and deques are usually class wrappers around
"doubly linked lists of arrays". Any data structures/algorithms textbook
should explain linked lists and many will explain at least one way to
implement a deque.

 

[Simon]

As long as an implementation behaves in accordance with the specifications
of the standard, then it is a compliant implementation. Seems sort of
obvious, doesn't it?

There are numerous detailed references on the definitions of standard
library elements, including the containers you mention.

http://www.sgi.com/tech/stl/table_of_contents.html
http://www.dinkumware.com/refxcpp.html

Thanks for that, it does make a little bit more sense.

the part I am having problem understanding is what is meant by "constant
time insertion" vs. "linear time insertion"

Both books I have, (and the links you provided), define the differences
between the containers as "constant" or "linear"
but are they both really?

Simon

 

[TB]

Simon sade:

Thanks for that, it does make a little bit more sense.

the part I am having problem understanding is what is meant by "constant
time insertion" vs. "linear time insertion"

http://en.wikipedia.org/wiki/O_notation
http://www.cprogramming.com/tutorial/computersciencetheory/algorithmicefficiency1.html

TB

 

[Bo Persson]

Thanks for that, it does make a little bit more sense.

the part I am having problem understanding is what is meant by
"constant time insertion" vs. "linear time insertion"

"constant time" means exactly that. The operation takes a certain
amount of time.
"linear time" means that the operation depends on the current size of
the container.

For example, adding an element to the front of a vector will move all
other element one position. This takes "linear time", as it depends on
how many elements must be moved. Adding to the end of the vector is
much easier.


Bo Persson

 

[Bo Persson]

Hi,

I understand what one the differences between std::vector,
std::deque and std::list is,
the std::vector can have data inserted/deleted at the end.
The std::deque can have data inserted/deleted at the end and at
beginning
and the std::list can have data inserted/deleted anywhere.

But how can those differences be physically understood?

If I understand correctly a std::vector with 3 items has data placed
one after the other.
V[0]V[1]V[2]
if I add another item it becomes, V[0]V[1]V[2]V[3]
and if a delete item V[2] the data is moved to remain one after the
other, V[0]V[1]V[3]
Because of the moving of data the item is slower.
Correct.


With std::deque we can insert data at the front of the block, but
how is that different from std::vector, I mean the data has to be
moved the same way.

No. The std::deque has to be able to insert and delete at the front,
without moving the other elements around.

One way of doing this is to have several smaller blocks of memory
containing tha data. You can then add additional blocks at either end,
without moving things around.

The vector, on the other hand, is required to have everything in one
large block. That way, it can find each element much faster.

And finally the std::list is the same as a std::vector but all items
are pointers to the actual element so if I insert an element all I
need to do is to add it at the end of the block of memory and place
the address of that element is an ordered list of pointers. so if I
have 3 elements
V[0]V[1]V[2]

A more common way to implement his is to have a 'list node' containing
the data element as well as two pointers. That way you don't need a
sorted master directory. Rearranging a list is then as simple as
changing the pointers.

Is my understanding of containers correct?
Well...

If my understanding is correct why even bother about using
std::vector and std::deque, std::list seems to do the job ok.

Generally, std::vector will do most kinds of jobs well enough. For one
thing, it uses less memory than the others. It is very fast to find a
specific element.

If it is not extremely large, and with very frequent inserts/deletes,
the actual moving around of the elements will not take much time
compared to everything else you do in a program.

Also, std::vector allocating one big block for all elements might be
much faster than allocating each list node inidividually.

As usual, "it depends". That's why there are several container types
to choose from.



Bo Persson

 

[Simon]

"constant time" means exactly that. The operation takes a certain amount
of time.
"linear time" means that the operation depends on the current size of the
container.

For example, adding an element to the front of a vector will move all
other element one position. This takes "linear time", as it depends on how
many elements must be moved. Adding to the end of the vector is much
easier.


Bo Persson

Thanks for all the replies.
To summarize, in simple terms.

All the standard says is

std::vector can add, insert, delete members but adding/inserting/deleting at
the end must be "constant time"
std::deque can add, insert, delete members but adding/inserting/deleting at
the end _and_ beginning must be "constant time"
std::list can add, insert, delete members but adding/inserting/deleting at
the end, beginning, middle must be "constant time"

In other cases, (insert or add in front of std::vector for example), is not
defined by the standard, but is usually done in "linear time".

Is the above correct?

Simon

 

[Bo Persson]

Thanks for all the replies.
To summarize, in simple terms.

All the standard says is

std::vector can add, insert, delete members but
adding/inserting/deleting at the end must be "constant time"
std::deque can add, insert, delete members but
adding/inserting/deleting at the end _and_ beginning must be
"constant time"
std::list can add, insert, delete members but
adding/inserting/deleting at the end, beginning, middle must be
"constant time"

In other cases, (insert or add in front of std::vector for example),
is not defined by the standard, but is usually done in "linear
time".

Is the above correct?

Yes, seems correct.

You may consider also, that the constant in "constant time" might be
different for different containers. Adding n elements to the different
types may take 1*n, 2*n, and 5*n units of time, respectively.


Bo Persson

 

[JustBoo]

Way to go "V." Converted yet another I "C". Now that's all they'll
want to write and "B."

Do you "work" in academia?

wow, thanks for your help!
I hope you achieve the post count you are after this month.
Simon

Excellent observation. Ego and acting superior is clear, but I
never considered that was coupled with "waving a big foam
hand around with ' I'm # 1 Poster' on it" as a motivating factor
as well. Thanks.

I hear it coming like a Sheep Stampede - the "P" word.

So as to keep this Standard:
Petty Myopic Bureaucrat = Language Lawyer += NetCop;

 

[Sgt. York]

Way to go "V." Converted yet another I "C". Now that's all they'll
want to write and "B."

Do you "work" in academia?


Excellent observation. Ego and acting superior is clear, but I
never considered that was coupled with "waving a big foam
hand around with ' I'm # 1 Poster' on it" as a motivating factor
as well. Thanks.

I hear it coming like a Sheep Stampede - the "P" word.

So as to keep this Standard:
Petty Myopic Bureaucrat = Language Lawyer += NetCop;

This "JustBoo" character has just given me reason to set up kill files.
You, Sir, need to get a life. And a prescription of lexapro or prozac
or something. And maybe get through puberty. In any case, farewell, I
will never see another post from you again.

 

[JustBoo]

This "JustBoo" character has just given me reason to set up kill files.

Thanks for sharing and caring.

To avoid criticism, do nothing, say nothing, BE nothing.

 

[Al Slater]

Way to go "V." Converted yet another I "C". Now that's all they'll
want to write and "B."

What the hell does that lot mean?

Get a life.

Al

 

[JustBoo]

What the hell does that lot mean?

Always been slow on the uptake, eh? Sorry, don't have time

Get a life.

Already have one, thanks. I guess you need to refer to the
Standard to figure-out what to do in your "life." Sad really.

He is a modest little man who has a good deal to
be modest about. - Winston Churchill