CODEWITHSUNDEEP
c++
McLovin
McLovin

Reputation: 3417

Are std::stack and std::queue cache friendly?

Do std::stack and std::queue allocate their data in contiguous memory, so they are considered "cache-friendly"?

Upvotes: 2

Views: 2093

Answers (2)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

std::stack and std::queue are container adapters, a strange beast that provides a stripped down uniform interface on a compile time determined container.

By default, they use std::deque as their backing store, which is not all that cache friendly (in every implementation I have examined).

stack can easily be handed a vector, which makes it friendly to the cache.

Making queue use a vector is tricky. You either have to wrap the vector into a circular buffer, or make it a double-ended vector. Both of those are non-trivial.

The only cache-friendly adaptive-size container in std is vector (and its near clone string), so there you go.

Upvotes: 3

Vlad from Moscow
Vlad from Moscow

Reputation: 310960

std::stack and std::queue are container adapters, They are based on the underlaying conteiner that can be for example std::vector and in this case they will be as you are saying "cache-friendly" or std::list and in this case they will not be "cache-friendly".

By default the both container adapters use std::deque as the underlaying container because it has all necessary methods to simulate the adapters. For example std::vector does not have required method pop_front and can not be used as an underlaying container for std::queue.

You can define your own underlaying container. The requirements are described in the C++ Standard.

Upvotes: 1

Related Questions