std::vector container can also be used as a stack as it provides mechanism to pushing and popping elements.
Info
A stack is a data structure that works on LIFO (last in first out) manner and provides push and pop operations. Push which puts a item on the stack top and pop that removes the item from the top.
std::vector provides following stack operations:
| Function | Description |
|---|---|
push_back | Push item to stack |
pop_back | Pop item from stack(it does not return the popped item) |
back | Peek the item on the top without removing it |
emplace_back | Same as push_back but can be efficient in certain cases (explain in subsequent sections) |
An example of using std::vector as stack: |
#include <iostream>
#include <vector>
void printStack(const std::vector<int> &stack)
{
if (stack.empty())
{
std::cout << "Empty";
}
for (const auto &item : stack)
{
std::cout << item << " ";
}
std::cout << "\tCapacity: " << stack.capacity() << " | Length: " << stack.size() << "\n";
std::cout << "---------------\n";
}
int main(int argc, char const *argv[])
{
std::vector<int> stack{};
printStack(stack);
stack.push_back(1);
printStack(stack);
stack.push_back(2);
printStack(stack);
stack.push_back(3);
printStack(stack);
std::cout << "Top: " << stack.back() << '\n';
stack.pop_back();
printStack(stack);
stack.pop_back();
printStack(stack);
stack.pop_back();
printStack(stack);
return 0;
}When we run this program, we should see the following output:
Empty Capacity: 0 | Length: 0
---------------
1 Capacity: 1 | Length: 1
---------------
1 2 Capacity: 2 | Length: 2
---------------
1 2 3 Capacity: 4 | Length: 3
---------------
Top: 3
1 2 Capacity: 4 | Length: 2
---------------
1 Capacity: 4 | Length: 1
---------------
Empty Capacity: 4 | Length: 0
One thing to notice in the output is the capacity. As we can see, the capacity changes whenever vector requires storage to store pushed element. Each time the capacity is changed, reallocation happens and we know that reallocation is expensive (in this note). We could avoid this if we could specify storage in advance. We can use provide the stack length while initialization (using direct initialization) as shown below:
std::vector stack(10);However, this also add 10 elements that we would not want. We could also use resize() member function but it also adds new elements (changes the length and capacity).
C++ provides one more member function reserve() which only changes the capacity.
#include <iostream>
#include <vector>
void printStack(const std::vector<int> &stack)
{
if (stack.empty())
{
std::cout << "Empty";
}
for (const auto &item : stack)
{
std::cout << item << " ";
}
std::cout << "\tCapacity: " << stack.capacity() << " | Length: " << stack.size() << "\n";
std::cout << "---------------\n";
}
int main(int argc, char const *argv[])
{
std::vector<int> stack{};
printStack(stack);
// settings the capacity to 10 so that no more reallocation happens
stack.reserve(10);
stack.push_back(1);
printStack(stack);
stack.push_back(2);
printStack(stack);
stack.push_back(3);
printStack(stack);
std::cout << "Top: " << stack.back() << '\n';
stack.pop_back();
printStack(stack);
stack.pop_back();
printStack(stack);
stack.pop_back();
printStack(stack);
return 0;
}With this, we should see the reallocation happening only one time.
Empty Capacity: 0 | Length: 0
---------------
1 Capacity: 10 | Length: 1
---------------
1 2 Capacity: 10 | Length: 2
---------------
1 2 3 Capacity: 10 | Length: 3
---------------
Top: 3
1 2 Capacity: 10 | Length: 2
---------------
1 Capacity: 10 | Length: 1
---------------
Empty Capacity: 10 | Length: 0
So, when using vector as stack, we can use reserve() function to change capacity or use resize() otherwise.
push_back() vs emplace_back()
push_back() and emplace_back() both pushes an element to the vector but emplace_back gets efficient when we push temporary object.
push_back() pushes already created object, if we pass temporary object, that object is copied (or moved if move is supported) into the vector.
However, emplace_back() takes the arguments used to create the object, it forwards them to vector where the object gets created. So, it saves on the extra copy (if move is not possible) to be made.
For example:
#include <iostream>
#include <vector>
#include <string>
class Grade
{
int m_marks{};
std::string m_grade{};
public:
Grade(int marks, std::string_view grade)
: m_marks{marks}, m_grade{grade}
{
}
explicit Grade(int marks)
: m_grade{"A"}, m_marks{marks} {}
};
int main(int argc, char const *argv[])
{
std::vector<Grade> grades{};
grades.push_back({1, "A+"}); // creates temporay object which gets copied/moved.
grades.emplace_back(10, "B+"); // forwards argument to vector to create object inside.
grades.emplace_back(11); // also works by using explicit constructor.
}emplace_back() works with explicit constructor which could be problematic in cases where we do not want unwanted conversions.
Tip
emplace_back()taking single argument maybe explicitly creating object usingGrade{10}, which works.
One more thing to note about emplace_back(). Prior to C++20, it does not support aggregate initialization. So, following would fail if compiled with C++17:
#include <iostream>
#include <vector>
struct Point
{
int x{};
int y{};
};
int main(int argc, char const *argv[])
{
std::vector<Point> points{};
points.push_back({1, 2});
points.emplace_back(1, 2); // only works C++20 and onwards as prior versions do not support aggregate initialization.
return 0;
}