Skip to main content

algorithm Header

tip

Functions in <algorithm> library​

Non-modifying sequence operations​

find()​

caution

Time Complexity is :~ O(n)​

if sequence container is sorted used binary_search and lower_bound as they both have O(log n) Time Complexity

when you operate on un-sorted sequence container or need the location of the item you searched for you must use find() If you want to search associative containers like set, map or their unordered_set, unordered_map must use consider their builtin methods like set::find

info

find() returns an Iterator rather than the item itself. So, we MUST do :~ it -v.begin() to get the Index No. as Integer.​

  • if it == v.end(); then the key/target doesn't exist
/* Input is:
56 545 63 45 96 522 85
*/
vector<int> v;
int tmp;

// initialising the vector "v"
while (cin >> tmp)
{
    v.emplace_back(tmp);
}

int key = 45;   // element to be "found"    `

// Finding the "Index" of the "key" in the vector "v" and assigning the index to ~ [ INTERATOR "it" ]
auto it = find(v.begin(), v.end(), key); // auto is used as  "it" is an "ITERATOR" and Iterators have "NO TYPES"

// assigning the "Index No." of  key to "index"
if (it != v.end()) {    // if the Iterator "it" has gone to the the "last Index" (v.end()) of the vector, then the "element" in not present
    int index = (it - v.begin());
    cout << index << endl; // prints  3
} else {
    cout << "Element NOT Present";
}

```cpp {title="index as Iterator"}
    auto ind = find(dq.begin(), dq.end(), el);
    cerr << "it.. " << ind - dq.begin() << " "; // printing index using Iterator
    cerr << dq.at(ind - dq.begin()) << endl;        // element at index iterator 'ind'
    dq.erase(ind);       // `__.erase` takes Itergator valu
```


```cpp {title="index as integer"}
    int indo = find(dq.begin(), dq.end(), el) - dq.begin();
    cerr << ".. " << indo << endl;  // printing index using integer
    cerr << dq.at(indo) << endll;   // element at index 'indo'
    dq.erase(dq.begin() + indo);    // `__.erase` takes Itergator value
```

> Refer: https://en.cppreference.com/w/cpp/algorithm/find

```cpp

```

- Also Available:~ `find_if` `find_if_not` `ranges::find` `ranges::find_if` `ranges::find_if_not`

count() - number of occurances / frequency​

  • count(v.begin(), v.end(), target);

counts the number of occurances of that element. Refer: https://en.cppreference.com/w/cpp/algorithm/count

Modifying sequence operations​

reverse()​

caution

Time Complexity: O(n/2) ↠ Exactly (last - first)/2 swaps.

info

// vec.begin(), vec.end()

reverse(v.at(j).begin(), v.at(j).end());
// v.at(j) is a ROW of 2D vector "v"

remove()​

caution

Returns: iterator pointing to the 1st element's index which was removed .. this iterator is same as container.begin() + 1stElementRemovedIndexNo)

Taking iterator from remove() in str.erase()​

    str.erase(remove(str.begin(), str.end(), ' '), str.end());

:::

replace()​

// Input is [ 10 20 30 40 50 60 ]
replace(v.begin(), v.end(), 30, 3333);  // replace "30" with "3333"

// Output is: [ 10 20 3333 40 50 60 ]

swap()​

rotate()​

info
// 4 3 2 1 6 5
rotate(v.at(j).begin(), v.at(j).begin() + index, v.at(j).end());
// v.at(j) is a Row of 2D vector "v"

// Output: 1 6 5 4 3 2
  • v.at(j).begin() + index is the index from wh ich we have to rotate

rotate_copy()​

transform()​


unique()​

info
  • unique() converts all diplicate elements into the first occurance of the element

stringName.erase(unique(stringName.begin(), stringName.end()), end());​

  • unique() MUST always used with end() because unique() add unknown iterators at the end of the string, Hence, unique() must only be used until end() iterator.

  • Here, "unique(s.begin(), s.end())" ⏩ , string "s" becomes "dehlorw*****"

  • Here, "s.end()" is used after 'unique()' inside "erase()" ⏩ because , all unknowns "*" gets removed and 'only last iteratorof the VALID string' "s" becomes ⇒ "dehlorw"

// Input is:  "helloWoroldd"
string s;
cin >> s;
transform(s.begin(), s.end(), s.begin(), ::tolower);

sort(s.begin(), s.end());   // s = "ddloroWolleH"

s.erase(unique(s.begin(), s.end()), s.end());   // 👉 removes all the diplicate elements except "first occurance of the element"
//👆 Here, "unique(s.begin(), s.end())" ⏩ , string "s" becomes "dehlorw*****"
//👆 Here, "s.end()" is used after 'unique()' inside "erase()" ⏩ because , all unknowns "*" gets removed and 'only last iteratorof the VALID string' "s" becomes -> "dehlorw"


cout << s;  // 👉  Prints  "dehlorw"

unique_copy()​

Sorting operations​

sort()​

sort(v.begin(), v.end());

user-defined explicit function with sort()​

https://www.codeproject.com/Articles/38381/STL-Sort-Comparison-Function

sorting can be done by adding an extra parameter called as Comparison Funtion which is a user-defined explicit function to the sort():

NEVER return with '=', '<=', '>=', '==' in CompareFunction

using (compareFunction) for sorting in Descending order of column[0]
static bool compareFunction(vector<int> v1, vector<int> v2)
{
    return v1[0] > v2[0];
    // NEVER return with  '=', '<=', '>=', '==' in CompareFunction
}

main()
{
    vector<vector<int>> ans = {{1, 2}, {2, 3}, {99, 100}};

    sort(ans.begin(), ans.end(), compareFunction);

    // ...........
}
/* Output:

99 100
2 3
1 2
*/

is_sorted()​

Binary search operations (on sorted ranges)​

binary_search(), must not be used with Associative Containers​

  • if sequence container is not sorted used find()but it has O(n) Time Complexity

  • if associative container use their in-built functions such as set::find() and others

    :::caution

Notably, std::set and std::multiset iterators are not random access i.e. they cannot be accessed by any Index no. as they don't have any Index No., and so their member functions std::set::lower_bound (resp. std::multiset::lower_bound) should be preferred.

:::

caution

Time Complexity is :~ O(log n)​

caution
  • binary_search() returns BOOLEAN TYPE true or false

binary_search() from STL should only be used with <vector>, <deque>, <forward_list>, <list>.

  • binary_search() becomes O(n) when used with set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, unordered_multimap.
  • All these Associative Containers have O(log n) alternative of binary_search() ⏩ find() for IndexNo. and contains() for true or false ; lower_bound() ⏩ own lower_bound() ; upper_bound() ⏩ own upper_bound() ; equal_range() ⏩ own equal_range()

So, binary_search() should only be used with Sequence Containers


lower_bound()​

for set or map use their individual in-bullt funtions like set::find(), set::count and others.

caution

💣💣 Must sort(..) the vector, deque container before using lower_bound or upper_bound 💣💣

Time Complexity is :~ O(log n)​

Returns: Iterator pointing to first element equal to or greater than key, or end().

  • If element/key is present This function returns the first element of a subsequence of elements that matches the given key.

  • If element not present it returns an iterator pointing to the first element that has a greater value than given key or end() if no such element exists.

info

lower_bound(v.begin(), v.end(), key) - v.begin()

  • Must be like this -> lower_bound(v.begin(), v.end(), key)- v.begin() because lower_bound() returns iterator and hence, we MUST subtract v.begin() from the lower_bound()
if (!binary_search(v.begin(), v.end(), key))   // if element is not present return -1
    return -1;
}
else
{
    return (lower_bound(v.begin(), v.end(), key) - v.begin());     // "lower_bound()" returns `iterator` and hence, we MUST `subtract` `v.begin()` from the `lower_bound()`
}

index and element of lower_bound​

vector<int> v = {55, 900, 99, 23, 3, 4};
int key = 23;

sort(v.begin(), v.end());

auto l_b = lower_bound(v.begin(), v.end(), key);
cerr << "lower_bound index is__" << (l_b - v.begin()) << " "
        << ", the element is__" << (*l_b) << endl;


/*
Output:

' lower_bound index is__2 , the element is__23 '

*/

to get the element from lower_bound then use *lowboundIteratorName ◀️​

vector<int> v = {55, 900, 99, 23, 3, 4};

auto l_b = lower_bound(v.begin(), v.end(), key);
cerr << "lower_bound element is___" << (*l_b) << endl;

cerr << "lower_bound index is___" << (l_b - v.begin()) << endl;

upper_bound()​

for set or map use their individual in-bullt

caution

💣💣 Must sort(..) the vector, deque container before using lower_bound or upper_bound 💣💣

Time Complexity is :~ O(log n)​

Returns: Iterator pointing to the first element greater than key, or end().

  • end() if no elements are greater than key.

upper_bound(v.begin(), v.end(), key) - v.begin()

info

index and element of upper_bound​

vector<int> v = {55, 900, 99, 23, 3, 4};
int key = 23;

sort(v.begin(), v.end());

auto u_b = upper_bound(v.begin(), v.end(), key);
cerr << "upper_bound index is__" << (u_b - v.begin()) << " "
        << ", the element is__" << (*u_b) << endl

/*
Output:

' upper_bound index is__3 , the element is__55 '

*/

to get the element from upper_bound then use *upboundIteratorName ◀️​

vector<int> v = {55, 900, 99, 23, 3, 4};

auto u_b = upper_bound(v.begin(), v.end(), key);
cerr << "upper_bound element is___" << (*u_b) << endl;

cerr << "upper_bound index is___" << (u_b - v.begin()) << endl;

equal_range()​

Minimum/maximum operations​

max()​

max(34, 2)
// returns 34

max({}) for more than 2 numbers​

max({1, 2, 3434, 344})

// returns "3434"

min()​

min(34, 2)

// returns 2

min({}) for more than 2 numbers​

min({1, 2, 3434, 344})

// returns "1"

*max_element()​

caution

Time Complexity is :~ O(n)​

/* Input is
56 545 63 45 96 522 85
*/
vector<int> v;

int temp;
while (cin >> temp)
{
    v.emplace_back(temp);
}

int mx = *max_element(v.begin(), v.end());

cout << mx << endl; // prints  545

*min_element()​

caution

Time Complexity is :~ O(n)​

/* Input is
56 545 63 45 96 522 85
*/
vector<int> v;

int temp;
while (cin >> temp)
{
    v.emplace_back(temp);
}

int mx = *max_element(v.begin(), v.end());

cout << mx << endl; // prints  45

minmax()​

minmax_element()​

Comparison operations​

equal()​

lexicographical_compare()​

lexicographical_compare_three_way()​

Numeric operations​

accumulate()​

partial_sum()​

Set operations (on sorted ranges)​

includes()​

set_intersection()​

Resultant container is set ⏩ set_intersection(firstSet.begin(), firstSet.end(), secondSet.begin(), secondSet.end(), inserter(resultSET, resultSET.begin());​

Resultant container is vector ⏩ set_intersection(firstSet.begin(), firstSet.end(), secondSet.begin(), secondSet.end(), back_inserter(resultVECTORname));​

caution

Time Complexity: O(n)​

More Precisely:- O(n + m)

info
  • Resultant container is set tmp
// va = [ 1 2 3 4 6 9 12 18 36  ]
// vb = [ 1 2 3 6 9 18 27 54  ]

set<ll> tmp;    // declaring empty set

set_intersection(av.begin(), av.end(), bv.begin(), bv.end(), inserter(tmp, tmp.begin()));   // inserting all common values of 'set' "av" & "bv" in 'set' "tmp"
// tmp becomes  [ 1 2 3 6 9 18  ]   ;   'tmp' returns the intersection of "av" & "bv"

cout << *tmp.rbegin() << endl;  // 👉 returns the "last" element of the 'set', "*" gives the value at that particular iterator '*tmp.rbegin()'
  • Resultant container is vector v
// va = [ 1 2 3 4 6 9 12 18 36  ]
// vb = [ 1 2 3 6 9 18 27 54  ]

vector<ll> v;    // declaring empty set

set_intersection(av.begin(), av.end(), bv.begin(), bv.end(), back_inserter(v));   // inserting all common values of 'set' "av" & "bv" in 'set' "tmp"
// tmp becomes  [ 1 2 3 6 9 18  ]   ;   'tmp' returns the intersection of "av" & "bv"

cout << *max_element(v.begin(), v.end()) << endl;  // 👉 returns the "max" element of the 'vector'

set_union()​

set_difference()​

set_symmetric_difference()​

Heap operations​

is_heap()​

is_heap_until()​

....

Permutation operations​

is_permutation()​

next_permutation()​

prev_permutation()​

C library​

qsort()​

bsearch()​

Parameters of the algorithm functions​

Comparison function​

caution

Comparison function is user-defined explicit function parameter to funtions like:sort()` and others

returns bool​