Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL vector VS list

Reply
Thread Tools

STL vector VS list

 
 
silverburgh.meryl@gmail.com
Guest
Posts: n/a
 
      01-13-2006
in STL, why vector has an API to return the n-th element, but list does
not have such API?

http://www.sgi.com/tech/stl/Vector.html
http://www.sgi.com/tech/stl/List.html

Thank you.

 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      01-13-2006
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> in STL, why vector has an API to return the n-th element, but list does
> not have such API?
> [..]


According to the design intent, 'list' is not a container that allows
random access to its elements. It's designed to allow quick insertions
and deletions, while not invalidating any references or iterators except
the ones to the deleted element. Providing efficient random access to
elements would not be possible. If you need random access to elements
of a container, use 'vector'. If you need robust and fast insertions
in any part of the container, use 'list'.

Read more books.

V
 
Reply With Quote
 
 
 
 
Andre Kostur
Guest
Posts: n/a
 
      01-13-2006
(E-Mail Removed) wrote in news:1137173258.277178.298990
@g49g2000cwa.googlegroups.com:

> in STL, why vector has an API to return the n-th element, but list does
> not have such API?
>
> http://www.sgi.com/tech/stl/Vector.html
> http://www.sgi.com/tech/stl/List.html


Vector is basically an array, so going to the n-th element of a vector is
only pointer arithmetic. List is a chain of nodes, so in order to get to
the n-th element, you must traverse the list from .begin() to the n-th
element.

Note that you can do something very similar by using std::advance on an
iterator into the list.

 
Reply With Quote
 
Ben Pope
Guest
Posts: n/a
 
      01-13-2006
(E-Mail Removed) wrote:
> in STL, why vector has an API to return the n-th element, but list does
> not have such API?


Because a vector provides random access iterators, and a list does not.

> http://www.sgi.com/tech/stl/Vector.html
> http://www.sgi.com/tech/stl/List.html


http://www.sgi.com/tech/stl/RandomAccessIterator.html
http://www.sgi.com/tech/stl/BidirectionalIterator.html

Ben Pope
--
I'm not just a number. To many, I'm known as a string...
 
Reply With Quote
 
Artie Gold
Guest
Posts: n/a
 
      01-13-2006
(E-Mail Removed) wrote:
> in STL, why vector has an API to return the n-th element, but list does
> not have such API?
>
> http://www.sgi.com/tech/stl/Vector.html
> http://www.sgi.com/tech/stl/List.html
>
> Thank you.
>

A vector is a container that supports random access. A list is not.
It's as simple as that.

HTH,
--ag

--
Artie Gold -- Austin, Texas
http://goldsays.blogspot.com
http://www.cafepress.com/goldsays
"If you have nothing to hide, you're not trying!"
 
Reply With Quote
 
Neil Cerutti
Guest
Posts: n/a
 
      01-13-2006
On 2006-01-13, (E-Mail Removed)
<(E-Mail Removed)> wrote:
> in STL, why vector has an API to return the n-th element, but
> list does not have such API?


The standard containers attempt to provide an interface that's
reasonably efficient. If an efficient implementation is not
possible for a given container, it does not provide it.
A list could offer an operator[] interface that provides random
access, but it would be very inefficient, so it does not.

The same type of reasoning dicates that vector provide push_back,
but not push_front, while deque provides both.

It's more of a guideline than a rule, though. There's usually a
way to get the inefficient behavior if you really want it.

--
Neil Cerutti
 
Reply With Quote
 
Calum Grant
Guest
Posts: n/a
 
      01-13-2006
Artie Gold wrote:
> (E-Mail Removed) wrote:
>
>> in STL, why vector has an API to return the n-th element, but list does
>> not have such API?
>>
>> http://www.sgi.com/tech/stl/Vector.html
>> http://www.sgi.com/tech/stl/List.html
>>
>> Thank you.
>>

> A vector is a container that supports random access. A list is not.
> It's as simple as that.


One could quite easily implement access to the nth element on a list.
But it was deliberately omitted.

Why?

Because it would not be efficient. The list would perform n operations,
while a vector could go straight to the element in one operation.
Providing an operator[] would just tempt people (who didn't get around
to reading every minutiae on the subject) to actually use it and
inadvertently write inefficient code.

 
Reply With Quote
 
persenaama
Guest
Posts: n/a
 
      01-15-2006
You already got good answers, but here's a question for you: describe
how you would implement the operator [] ?

Background information:

- std::vector is fundamentally, an array
- std::list is fundamentally, a linked list

For an array, providing [] is trivial. For list, it is not-so trivial
to do efficiently. If you have any good ideas I'm all ears.

I don't expect any reasonably efficient solution to be found at this
time, but, it would be interesting to discuss any approach you come up
with, because, once upon a time I put some thinking into the very same
question and came up with compromises and tradeoffs between various
aspects of the implementation. It all boils down to the fundamentals of
what you expect from array and linked list.

It would make more sense to ask what use is container which is
jack-of-all-trades but master of none. The answer won't be all black
and white, that's why there are containers like std::map, std::deque
and so on.

Let's take a look at container, where we have [], doing pointer
arithmetic is going to be hard to beat:

struct container {
type* base;
type& operator [] (int index) { return base[index]; }
};

Now, the problem with this setup is that inserting into the middle is
going to be rather cumbersome to say the least, we have to *move*
elements after the insertion point to make room for the new elements
being inserted into the sequence. That goes without saying, but you
surely see the problem this imposes?

Linked list is the next step, here's similiarly naive framework:

template <typename x>
struct container {
struct node { x data; node* next; node* prev; };
node* head;
node* tail;
};

Eg. each object has pointer to previous, and next one in the sequence.
That makes implementing [] efficiently rather tricky. That's why
std::list doesn't do [].

If you want both "traits" in one container, you start designing and see
what you trade for what. Most likely you'll be balancing between these
things:

- insert/remove runtime performance
- operator [] performance
- iteration performance
- memory footprint
- and more

Sometimes it is more critical that iteration, or some other operation
is very efficient. It all depends what's the design purpose of the
container.

Please discuss this further.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can list container contain an vector object, such as list< vector<string> >?? ehui928 C++ 2 05-29-2006 01:09 PM
Free memory allocate by a STL vector, vector of vector, map of vector Allerdyce.John@gmail.com C++ 8 02-18-2006 12:48 AM
Vector of STL maps versus Vector of objects amolpan@gmail.com C++ 2 07-26-2005 10:16 PM
Automatic Conversion of STL Containers: e.g. from vector<derived*> to vector<base*> CD C++ 2 10-05-2004 02:29 PM
STL algorithm problem vector<vector<double> > and find Dennis C++ 1 06-07-2004 10:09 PM



Advertisments