Deque random access vs vector

[Ganado]

While reading, it says that a vector's memory is continuous, while a deque's memory is not. So how then, I'm wondering, is random-access ( my_container[i] ) still possible in constant time with a deque?

Also, what's the point/advantage of using C++'s std::stack over directly using the individual Containers that are used to make an std::stack (deque by default, vector, or list), if any? (Note my question is not asking about whether to use a list vs a vector or whatever, just about the point of abstracting it into a stack).


Another related, but separate question:
I am trying to figure out the most efficient way to do the following code.

Using stack, I'd have to do something like this.

    T a = numbers.top();
    numbers.pop();
    T b = numbers.top();
    numbers.pop();
    numbers.push(a * b);

This makes me have to make 2 temporary variables to store the top and second-to-top variables. (3 for the overloaded multiplication)

But I'm wondering if there is, logically, a better way to go about modifying my container like this? Is there a way to not have to create two temporary variables? I don't think there is logically no matter what container is used, but just wondering if any of you have an idea. =)

Vectors seem to take extra care to only reallocate when necessary, so should I most likely stick to a stack using the vector container for this instead of deque?

Edit: changed .read() to .top()

[MiiNiPaa]

1) http://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl

2) It is an adapter to the container interface. Using it you make sure that nobody adds item to the middle or retrieve them from the front.

3) If you are using C++11 and T is cheap-to-move class, following will be as fast as you can get:

T a = std::move(numbers.top());
numbers.pop();
numbers.top() *= a; 

Vectors seem to take extra care to only reallocate when necessary, so should I most likely stick to a stack using the vector container for this instead of deque?

Deques do not reallocate memory at all. They can move elements around if you decide to insert in the middle, but existing memory blocks will not be reallocated.
http://www.gotw.ca/gotw/054.htm

[Smac89]

My guess for deque is that it allocates containers of the same size for each allocation. For example it might allocate each container to be of size 100 and each time you try to index a container. It takes your index and divides it by 100, this will indicate which bucket container you are trying to access. Then it will mod your index by 100 to determine which slot in the container you are trying to access. This might be slower but may be optimized by the compiler (somehow...), but if you are looking for pointer validation in a dynamic sort of array setting, then this is the container for you.

As for your second question, it is very simple to create a stack data type that will return the value at the top of the stack and remove it at the same time when stack.pop() is called, or you can use an array of size 3 or 4 which will use indexing to return each value and decrement the position of the current last element.

Ganado wrote:

Also, what's the point/advantage of using C++'s std::stack over directly using the individual Containers that are used to make an std::stack (deque by default, vector, or list), if any? (Note my question is not asking about whether to use a list vs a vector or whatever, just about the point of abstracting it into a stack).

The advantage is that provided by encapsulation. If you are told to use the underlying container directly, this will involve doing what I suggested about using arrays in the above answer

Take a look at this benchmark for std::list, std::deque and std::vector
http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

[MiiNiPaa]

This might be slower but may be optimized by the compiler (somehow...)

Finding quotent and remainder at the same time is a single command in assembly :)
Alternatively if bucked size is exponent of 2, bucket number is index >> exp and element index is index & (1 << exp) where 1 << exp is compile time constant

[Ganado]

Thanks for the replies!
I get what you mean encapsulation, it makes sense.
Been reading the tests linked from the SO page and the other links. Seems like vector and deque are indeed really close, and I'll have to re-read it some more to make more sense of it. Guess for now I'll stick with a stack using deque.

T a = std::move(numbers.top());
numbers.pop();
numbers.top() *= a; 

Thanks, it had gone right over my head about how top()'s reference doesn't have to be const. The type T I'll be using probably won't be more complicated than a 2 or 3-dimensional coordinate/number, so this seems like the sanest choice.