Блог пользователя AMIT-_-PANDEY

STACK vs VECTOR
Автор AMIT-_-PANDEY, история, 9 месяцев назад, По-английски

If in a vector we can use use push_back() and pop_back() and in a stack we do push and pop from the rear end of the stack . So what is the significance of stack over a vector ? Is it size related or something else ?

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One of the major differences is you can resize the vector and access the element using indexing but you cannot access the element using indexing in stack.

→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    The main question is what is the significance to use stack over vectors.

    → Ответить
    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Only where is more intuitive to use a Stack. It's an interface, A Stack uses a Vector internally. It's the same as a Queue in BFS for example. In reality a Queue uses a Deque, a LinkedList or a Vector internally but makes more sense using the API of a Queue (front / pop / push) for the algorithm.

      → Ответить
      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        One little thing: by default stack uses deque internally (internal container is template parameter, so you can use vector too though)

        → Ответить
»
9 месяцев назад, # |
← Rev. 6   Проголосовать: нравится +15 Проголосовать: не нравится

vector guarantees insertions by "new and copy", so when there are enough elements, it will request a new space and copy everything in it, which means that some operation may reach O(n).

This is safe to amortized analysis, so it's safe in CP, but not every where accept amortized analysis. For example, you wouldn't want an AI driving your car to cause a 0.5s brake failure because of vector.

on the other hand ,stack is implemented using linked lists, which can cause some constant problems with cache miss, but it guarantees that all operations are O(1).

here's why. This feature also leads to you can make a persistent stack with O(1), but you have to use persistent segment tree to make a persistent vector in O(log n). But this is not reflected in the C++.

this answer is not generate by chatGPT. it's generate by catGPT. meow

the cat used to generate the answer
→ Ответить
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "For example, you wouldn't want an AI driving your car to cause a 0.5s brake failure because of vector."

    Huh. Never thought about that before. Interesting.

    → Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If you only need 1 stack, a fixed size vector/array can run faster than the STL stack because of the way cache works. If you needed more, with dynamic size i'd recommend stack. Be aware declaring an array of stack can be dangerous, even if they are never used. Most STL data structures have internal values and even empty they use some memory which can lead to TLE/MLE.

→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Stack is a container adapter which uses std::deque container by default (it can use std::vector too if you declare it like stack<T, vector>).

std::vector and std::deque allocate memory differently. std::vector allocates memory like an dynamic array in a continuous block of memory where std::deque allocates memory like double linked list in a quite scattered way(not sure what is the accurate terminology for that).

Here are some performance benchmarks you can check.

→ Ответить