The difference between sequence containers and container adapters in C ++

Question

What is the difference between sequence containers and container adapters in C ++?

Here I mean containers of sequences as vectors, deque, list, while container adapters as a stack, queue, priority_queue. When do we prefer sequential containers and container adapters?

Answer 1

Sequence containers

You can see the sequence container as “built from scratch” containers. They use different structures for storing data and have a different algorithm time for inserting, deleting and retrieving an element.

You can find a lot of information about algorithmic container time here.

Container Adapters

Container adapters are behaviors added across sequence containers , making them respect different paradigms. Added behavior can be more strict (stacks will only allow you to click / click on it, without accidentally pasting). They are other types of containers that do not require new storage behavior, and then existing ones. For example, a stack can be built over a vector. Then it will use the vector data structure, but it hinders the use of a certain set of functions that mimic the stack.

The most important thing in all of this is to make sure that you use the right container to meet your needs. A more rigorous container will help you prevent the omission of your data and find out how using your data will help you choose a good container to get better results.

More information on container adapters can be found here.

What should be used most of the time?

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

Answer 2

A sequence is a special kind of container in which elements have an order that is independent of their values. Instead, it is the order that they attach to the container (or inserted, etc.).

The container adapter is not a container at all, because it does not implement the container interface (does not provide an iterator, etc.). Instead, it provides limited access to the container. Those presented in the standard library work using sequence.

You use a container adapter if you want limited access to a collection of objects. Both stacks and queues allow adding at only one end. In addition, the stack only allows you to read / delete from the same end that you are writing to, and the queue only allows you to read / delete at the opposite end. They do nothing that the sequence does, except that you interrupt the execution of all elements, etc.

Behavior

priority_queue is a little trickier and it adds behavior that is not yet part of the sequence.

Answer 3

Container adapters use containment to provide limited access to sequence container functions. Many public container adapter methods are simply wrappers around calls to this non-public element. If your application can work with the limited functionality of the container adapter, it is better to use a container adapter.

Suppose you just used one of the sequence containers to implement the queue. You call push_front to add to the queue, pop_back to remove from it. Now some bozo helper comes in and calls pop_front instead of pop_back . If you do not want someone to go beyond the wrong end of the thing that you intend to use as a queue or stack, do not provide this function. Container adapters intentionally do not provide full access to the base sequence container.

On the other hand, if you need to get under the hood (for example, you need to look into the second element on the stack), you will need to use the sequence container instead of the adapter. Perhaps you should consider using an adapter philosophy: do not export the full functionality of the container. Just export the functionality you really need.

Answer 4

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

If you are not sure when you need it: the stack grows and shrinks from one end, so you can use it as a battery for storing intermediate results (stack computer); use the queue to process things on a first-in-first basis (FIFO); priority queue exposes items in a specific order (for example, saves tasks and then retrieves them in order of importance).