STL vector VS list

[silverburgh.meryl]

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.

 

[Victor Bazarov]

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

 

[Andre Kostur]

(e-mail address removed) wrote in @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.

 

[Ben Pope]

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

 

[Artie Gold]

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

 

[Neil Cerutti]

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.

 

[Calum Grant]

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.

 

[persenaama]

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.