Difference between sequence containers and container adaptors in c++

What is the difference between sequence containers and container adaptors in c++?

Here i mean sequence containers as vectors, deque, list while container adaptors as s开发者_如何转开发tack, queue, priority_queue. When do we prefer sequence containers and container adaptors?

The container adaptors use containment to provide limited access to sequence container functionality. Many of the container adaptor public methods are simply wrappers around calls to this non-public element. If your application can live with the limited functionality of a container adaptor it is better to use the container adaptor.

Suppose you just used one of the sequence containers directly to implement a queue. You call push_front to add to the queue, pop_back to remove from it. Now along comes some bozo maintainer and calls pop_front instead of pop_back. If you don't want somebody to pop the wrong end of the thing that you intend to be used as a queue or stack, don't provide that functionality. The container adaptors intentionally do not provide full access to the underlying sequence container.

On the other hand, if you need to get under the hood (for example, you need to peek at the second element in a stack), you are going to need to use a sequence container instead of an adaptor. You might want to think of using the adaptor philosophy: Don't export the full functionality of the container. Just export the functionality that truly is needed.

A sequence is a particular kind of container, in which the elements have an order independent of their values. Instead, it's the order they're appended to the container (or inserted, etc).

A container adaptor is not a container at all, since it doesn't implement the interface of a container (doesn't provide an iterator, etc). Instead, it provides limited access to a container. Those provided in the standard library operate using a sequence.

You use a container adaptor when you want limited access to a collection of objects. Both stack and queue only let you add at one end. In addition, stack only lets you read/remove at the same end you write to, and queue only lets you read/remove at the opposite end. They don't do anything that a sequence doesn't already do, except for stopping you iterating over all elements and so on.

priority_queue's behavior is a bit more complicated, and it does add behavior that isn't already part of the sequence.

Sequence containers

You could see sequence container as containers "built from scratch". They use different structures to hold data and have different algorithmic time to insert, delete and retreive element.

You can find a lot of information about the algorithmic time of containers here

Container adapters

Container adapters are behavior added over sequence containers making them respect different paradigms. The added behavior can be a stricter behavior (the stack will only allow you to pop/push item on it, no random insert). They are other type of containers that did not need a new storing behavior then those already existing. As an example, a stack could be built over a vector. It would then uses the data structure of vector, but restrain the usage to a certain set of functions to mimic a stack.

Most important over all this is to make sure that you use the right container to suit your needs. A stricter container will help you prevent missuses of your datum and knowing the usage of your data will help you chose the good container to get the best performances.

More information about container adapters can be found here

What should I use most of the time?

Many experts (Scott Meyer, Bjarne Stroustrup) suggest the use of the vector by default while others (like Herb Sutter as Steve Jessop pointed out) suggest the deque. I would strongly suggest you to chose the container that best suits your need.

You should use the stack container adapter when you need a stack, the queue adapter when you need a queue, and the priority_queue adapater when you need a priority queue.

If you're not sure when you need these: a stack grows and shrinks at one end, so you can use it as an accumulator to store intermediate results (a stack machine); use a queue to treat things in a first-in, first-out (FIFO) manner; a priority queue pops elements in a defined order (e.g., store tasks, then retrieve them in order of importance).