Some Basic STL Operation

Upper Bound & Lower Bound:
Suppose we are searching for a value that is exactly greater than value 'x', or let's say we are searching for a value that is exactly greater or equal to value 'x'.

Let me more explain, suppose we have a vector.
vector<int>a = {1,2,4,7,9}, sorted in ascending order.

Now, we are searching for a value in vector 'a' that is exactly greater than '3'. So if start searching for the left to right we can get '4' in the 2nd(0th indexed) position. 

This searching for exactly greater value is called Upper_bound. This means the upper value of 'x'.
auto position = upper_bound(a.begin(), a.end(), x) - a.begin(); that's return the position of greater value(if exits in vector)

Similarly, searching for exactly greater or equal(>=) value is called Lower_bound.
auto position = lower_bound(a.begin(), a.end(), x) - a.begin(); 
that will also return the positon.

Examples,

The lower bound of 3 is the index 1.
The upper bound of 3 is the index 2.

In this case, it is logarithmic complexity. If we search for a random value, we can do a[x], this we take O(1).

Set and Multiset:

Set and Multiset are the very useful STL techniques that have been used in most algorithmic problems.

Set contains only unique elements. Multiset contains duplicates value.
Suppose we insert this(2,1,2,2,4,5,9,1) values into Set and Multiset,

Set :      (1, 2, 4, 5, 9)
Multiset: (1, 1, 2, 2, 2, 4, 5, 9)

One thing didn't mention yet before that is, both of them contain values sorted in ascending order.

Now, if we apply upper bound and lower bound in Set and Multiset, this will not work as before.

Set and Multiset has lower_bound and upper bound.
Simply we can do, s.upper_bound('x'),(set or multiset in both case)

Here it is log N complexity, but if we want random access like s[n], it's not possible because set and multiset don't have random access.

we can also do, erase and count operations in set and multiset.

Example:

Set,
(2,7,5,5) => set s(2,5,7) [ after inserting into set ]
s.erase(5) => s(2,7)

Multiset,

(2,7,5,5) => multiset m(2,5,5,7)
m.erase(5) => it will remove all '5' from multiset.
if we want to remove only one '5' form there, we have to do remove one's position.

auto it = m.lower_bound(5) => 1
m.erase(it) => m(2,5,7)


Stack:

Stack is one of the data structures and supports two types of operations.
It maintains the LIFO sequence, which means Last-In-First-Out.

Picture from internet

We can use "A pile of plates" as an example. Here if we add a plate that will take place on the top, after that if we want to remove any plate, the latest one will be removed.

Two types of operation:
Push: Add an element to the end of the stack.

Pop: Remove an element from the top of the stack.

Details with example:

stack<int> st;

st.push(2); st.push(3); st.push(5); st.push(8);

// stack now is [2, 3, 5, 8]    

int topElement = st.top();

cout << topElement << endl; // 8

st.pop();  // stack now is [2, 3, 5]

st.pop(); // stack now is [2, 3]

Queue:

The queue is a container, it maintains the FIFO sequence, which means First-In-First-Out.

Source: Internet

We can take "People's Line" as an example of a queue, where a bunch of people makes lines for tickets, food, or something else.
In the line, First people come first then the second person, and so on. Declare as, queue<data_types>Q;

Some most used operations of Queue,

Q.empty()
Q.size()
Q.front()
Q.back()
Q.push() [ push_back ]
Q.pop()   [ pop_front ]

Usually takes O(1) complexity.


Priority Queue:

Another data structure supports some very important operations.

Insert an element in the queue in O(logN) time (N size of the queue).
Find the largest (or the smallest) element in the queue in O(1) time.
Remove an element from the queue in O(logN) time.

priority_queue<int> q; // Greater Value first, we can also put (-ve) value

q.push(2);q.push(3);q.push(8);

// q.top() finds the maximum element in the queue.

cout << q.top() << endl; // prints 8

q.pop(); // q.pop() removes the maximum element from the queue.

cout << q.top() << endl; // prints 3 now.

q.push(15);

cout << q.top() << endl; // prints 15

priority_queue<int, vector<int>, greater<int>> q; // Small value first

        

q.push(2);q.push(3);q.push(8);

// q.top() now finds the minimum element in the queue.

cout << q.top() << endl; // prints 2

q.pop(); // q.pop() also removes the minimum element now.

cout << q.top() << endl; // prints 3 now.

q.push(15);

cout << q.top() << endl; // prints 3

Related Problems:
Concert Ticket - CSES
Valid Parentheses(Leetcode)