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.