.begin() - Returns an iterator pointing to the start of the container
.end() - Returns an iterator pointing to the address next to the last element in the container
.empty() - Returns whether the container is empty
.clear() - Clear all contents present inside the container
.size() - Returns number of items present inside the container (absent in forward_list)
.max_size() - Returns theoretical maximum number of elements that the container can hold
.swap(other) - Swap content of current container with other container of same type
.resize(n) , resize(n,val) - Resize container to contain n elements. Can also pass default value val to set newly created elements as
The emplace member functions (like emplace_back, emplace_front, emplace_front, emplace etc.) perform insertions slightly faster than regular push or insert functions as they construct the new element in-place (instead of constructing the element and then copying it to that place). These are particularly useful for bulky composite types where copying is expensive. They take single list of variadic arguments required for that composite object
Adaptors for Sequence Containers
They provide a wrapper interface for sequential containers. These are:
Supports O(1)insertion/deletion if location specified (only links get updated)
Operations at the start are O(1) and O(N) elsewhere.
Random access NOT present. Only the start i.e. head accessible
Uni-directional access to only forward adjacent element: next(pos)
Element Access: .front() to access first element in the list
Iterators: .before_begin()
Returns an iterator pointing to a placeholder element before the first element in the list
Trying to access it results in undefined behaviour
Incrementing this iterator gives .begin()
Generally used with .insert_after() , .emplace_after() , .erase_after() etc.
The list goes in only one direction i.e. forward. So, we can only do itr++ , but NOTitr-- (where itr is an iterator pointing to some element in the list)
Capacity: Note that .size() function is NOT provided
Modifiers:
.pop_front() - Remove first element from the list
.push_front(item) , .emplace_front(item) - Insert element item at start of the list
.insert_after() - Insertion takes O(1) per entry in these operations
.insert_after(pos,item) - Insert element item after the position pos
.insert_after(pos,count,item) - Insert count copies of item after position pos
.insert(pos,start,end) - Insert all elements within [start,end) after position pos
.emplace_after(pos,...args) - Construct element in-place after position pos
forward_list Demo
forward_list
voidprintList(forward_list<int>&ll){
if(ll.empty()){
cout <<"List is empty";
}else{
for(auto&num : ll) cout << num <<" -> ";
}
cout << endl;
}
intmain(){
forward_list<int> ll{7,1,3,5};
printList(ll); // 7 -> 1 -> 3 -> 5 ->
cout <<"First element: "<<ll.front()<< endl; // First element: 7
Operations at the start and end are O(1), but O(N) elsewhere
Random access is supported in O(1) time
How is deque different from vector or list :
Unlike vector, the elements are not stored contiguously
Indexed access to deque must perform two pointer dereferences, compared to only one in indexed access of vector
Expansion is cheaper than expansion of vector because it does not involve copying existing elements to new memory location
See this answer for difference between deque and list
Most implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping. They can also expand/contract as needed on both ends. They also have a large minimal memory cost for allocating the individual arrays
Element Access:
.at(idx) - Access element at idx index, with bounds-checking
[idx] - Access element at idx index
.front() - Access first element
.back() - Access last element
Iterators: .begin() , .end() , .rbegin(), .rend()
Capacity: .size() available. Also, .shrink_to_fit() to free-up unused space
Modifiers:
.push_front(item) , .emplace_front(item) - Insert element item at start of the list
.push_back(item) , .emplace_back(item) - Insert element item at end of the list
.pop_front() - Remove first element from the list
.pop_back() - Remove last element from the list
.insert() : Inserting element(s) at given position
.insert(pos,item) - Insert element item at position pos
.insert(pos,count,item) - Insert count copies of item at position pos
.insert(pos,start,end) - Insert all elements within [start,end) at position pos
.emplace(pos,...items) - Construct element in-place at position pos
The stack adaptor provides a Stack data structure wrapper to the container, which has the property of Last-in First-out i.e. LIFO (also called first-in last-out)
Supports operations ONLY at the top of Stack, which take O(1) time each
It’s defined as:
template<
classT,
class Container = deque<T>
>classstack;
Declaration: stack<Type> stk;
Element Access: .top() returns reference to first i.e. top-most element
Capacity: .size() , .empty()
Iterators: NONE provided
Modifiers:
.pop() - Remove element present at the top
.push(val) - Insert element at the top
.emplace(...args) - Construct element in-place at the top
The queue adaptor provides a Queue data structure wrapper to the container, which has the property of First-in First-out i.e. FIFO (also called last-in last-out)
Insertion occurs at the back and Deletion at the front, both taking O(1) time
It’s defined as:
template<
classT,
class Container = deque<T>
>classqueue;
Declaration: queue<Type> q;
Element Access:
.front() - returns reference to first i.e. starting element
.back() - returns reference to last i.e. ending element
Capacity: .size() , .empty()
Iterators: NONE provided
Modifiers:
.pop() - Remove the first i.e. starting element
.push(val) - Insert element at the end
.emplace(...args) - Construct element in-place at the end
The priority_queue adaptor provides a Heap data structure wrapper to the container
Fast lookup of highest-priority element in O(1) time
Insertion/Deletions take upto O(logN) time
It’s defined as:
template<
classT,
class Container = vector<T>,
class Compare = less<typenameContainer::value_type>
>classpriority_queue;
The default ordering is to keep the lexicographically larger element at the top i.e. a Max-heap, but you can also provide a custom Compare function to determine the ordering