C++ STL

Shaila Nasrin
4 min readSep 7, 2019

--

In this post I’m not doing in depth discussion on how these standard libraries works behind the scene. I will just show what they do and how to use them.

Sort

  • sort: It orders the elements from beginning to end in O(nlogn) complexity. By default it the elements in ascending order for numeric values and lexicographical ascending for string values. (* P.S. print() is not a stl, I have written the method to print the vector. you can see that in the source code I have provided in the end of the post)
Use of sort to sort values ascending or descending order
  • stable_sort: Similar sort, stable sort orders the elements from beginning to end in O(nlogn) complexity. By default it the elements in ascending order for numeric values and lexicographical ascending for string values. The difference between sort and stable_sort is, if the the elements are equivalent then stable_sort guaranties to keep their same order.
Use of stable_sort

Reverse

  • reverse: It reverses the elements from first iterator to last iterator in O(n) complexity.
Use of reverse
  • reverse_copy: Similar to reverse, reverse_copy reverses the elements from first iterator to last iterator in O(n) complexity but it makes a copy of the reversed elements to the result iterator.

Rotate

  • rotate: It shifts the elements in from first to last iterator in O(n) complexity in such a way that the middle elements becomes the first element.
  • rotate_copy: Similar to rotate, rotate_copy shifts the elements in from first to last iterator in O(n) complexity in such a way that the middle elements becomes the first element but it copies the rotated elements to the result iterator.

Any of

  • any_of: It returns true if any of the element in the range returns true for the unary predicate( C++ function returning a boolean and takes one argument). This runs in O(n) complexity.

All of

  • all_of: Similar to any_of, it returns true if all of the element in the range returns true for the unary predicate( C++ function returning a boolean and takes one argument). This runs in O(n) complexity.

None of

  • none_of: It returns true if none of the element in the range returns true for the unary predicate( C++ function returning a boolean and takes one argument). This runs in O(n) complexity.

Partial Sum

  • partial_sum: partial_sum returns a resulting array where every element is the sum of all its previous elements from start iterator to end iterator in O(n) complexity. By default it does summation but you can also pass in binary operator to do multiplication or division.

IOTA

  • iota: It fills the range from start to end with sequentially increasing values starting with the given value. It runs in O(n) time.

Adjacent Find

  • adjacent_find: It searches the array from start to end iterator for the first occurrence of two consecutive and returns the first of its iterator otherwise returns last if no such pair found. It runs in O(n) time. By default it returns the index of first occurrence of two consecutive equal values but we can pass binary predicate to do other things with this method.

Count

  • count: It returns number of elements that are equal to the given value in the range from start to end iterator in O(n) time.
  • count_it: It returns number of elements for which predicate is true in the range from start to end iterator in O(n) time.

Partition

  • partition: It rearranges the elements from the range from start to end iterator in such a way that all the elements for which unary predicate is true comes in front of the array and all the elements for which predicate is false is put after them in O(n) complexity and the iterator returns the first element of the second group.
  • stable_partition: Similar to partition, it rearranges the elements from the range from start to end iterator in such a way that all the elements for which unary predicate is true comes in front of the array and all the elements for which predicate is false is put after them in O(n) complexity and the iterator returns the first element of the second group. But it maintains the order of each group of elements.

Maximum & Minimum

  • max: It returns the largest of two values.It runs in O(1) complexity.
  • min: It returns the smallest of two values.It runs in O(1) complexity.
  • minmax: It returns a pair with the smallest element as the first element and the largest element as the second element. It runs in O(n) complexity.
  • min_element: It returns the smallest element from the range of start and end iterator.It runs in O(n) complexity.
  • max_element: It returns the largest element from the range of start and end iterator.It runs in O(n) complexity.
  • minmax_element: It returns pair of iterator of the values of the smallest and the largest element from the range of start and end iterator.It runs in O(n) complexity.

Source code for all the stl methods mentioned above.

--

--