LATEST POSTS

Coverage Problem in Mobile Robotics

Visual SLAM - An Introduction

Simulataneous Localization and Mapping - An Introduction

Motion Planning in Robotics

Sampling-based Motion Planning

The Standard Template Library in C++ is a large native library in C++ that provides in-built data structures and algorithms. It is a collection of containers, iterations and algorithms. STL is templated and thus supports multiple variants of data types like vectors, lists, deque, arrays, heaps and sets. This article talks about the general algorithms for searching, sorting and queries applicable to these containers.

This list of algorithms is not exhaustive yet contains the most common and# useful C++ native algorithms in the STL library. Any of these algorithms can be written again though the efficiency of the same would atmost be comparable to the same available in the STL libraries.

**NOTE: **

`vector.begin(), vector.end()`

can also be replaced by `std::begin(vector)`

and `std::end(vector)`

respectively as `std::begin(vector)`

was only introduced in C++ 11 to allow easy coding for generic templated structures that support C-style arrays (that do not have methods like `.begin()`

) as well as STL containers.

Heaps are special tree-based data structures following one particular heap condition: node values down the tree are sctricty ascending(min heap) or strictly descending (max heap), i.e. parent-child relationship is monotonic. A heap is not completely sorted but partially ordered binary tree and thus knowing the priority for the element, a heap can serve for efficient data manipulation and accessibility.

The Standard Template Library in C++ allows for a heap data structure and which has a priority queue as the base container. The algorithms provide the functions necessary to use the features of a heap.

* Algorithms for Heaps*

**⇒** Create a heap from vector of numbers

```
std::make_heap(vector.begin(), vector.end())
```

**⇒** Add contents to a heap (it handles the pushing of numbers and arranges them in the heap based on the comparison)

```
std::push_heap(vector.begin(), vector.end())
```

**⇒** Pop out the highest number

```
std::pop_heap(vector.begin(), vector.end())
```

**⇒** Reverse the order of the heap (Applicable to other containers as well )

```
std::reverse(vector.begin(), vector.end())
```

**⇒** Sort the elements of the heap in ascending order and the range is no longer a heap

```
std::sort_heap(vector.begin(), vector.end())
```

Sorting the information stored in containers based on conditions is one of the most common things to do while dealing with any data. As simple as ranking students on the scores obtained means first arranging the scores in descending order.

The Standard Template Library in C++ provides in-built implementations for different kinds of sorting operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

* Algorithms for Sorting*

**⇒** Sorting of numbers in ascending order. If function is provided then it is used for sorting comparison. If fucntion returns **true**, then first element ordered before second.

```
std::sort(vector.begin(), vector.end(), function)
```

**⇒** Sorting of numbers in ascending order. If function is provided then it is used for sorting comparison. If fucntion returns **true**, then first element ordered before second.

**Different from **

```
std::stable_sort(vector.begin(), vector.end(), function)
```

```
std::partial_sort(vector.begin(), middle, vector.end())
```

```
std::nth_element(vector.begin(), nth_element, vector.end())
```

Elements of a container are required to be shuffled in different orders as per need.

The Standard Template Library in C++ provides in-built implementations for different kinds of permutation/re-arranging operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

* Algorithms for Permutations*

**⇒** Reverse the order of elements in the container

```
std::reverse(vector.begin(), vector.end())
```

**⇒** Create a new copy of the container to a

with reversed order of elements**new_vector**

```
std::reverse_copy(vector.begin(), vector.end(), new_vector.begin())
```

**⇒** Rotate the container about the middle element such that the middle element becomes the first element of the new rotated vector. Possible applications are found in insertion sort or order reshuffling

```
std::rotate(vector.begin(), vector.middle(), vector.end())
```

**⇒** Reshuffle the elements of the container based on using the `std::rand`

as the random seed generator function

```
std::random_shuffle(vector.begin(), vector.end())
```

**⇒** Reshuffle the elements of the container based on a seed obtained via URBG (Uniform Random Bit Generator). More efficient that the `std::random_shuffle`

```
std::shuffle(vector.begin(), vector.end(), random_number_generator)
```

**⇒** Rearrange the elements of the container into a permutation higher up in the lexicographical order.

```
std::next_premutation(vector.begin(), vector.end())
```

**⇒** Rearrange the elements of the container into a permutation lower down in the lexicographical order.

```
std::prev_premutation(vector.begin(), vector.end())
```

Several queries about the features of containers are made, either for one single container or multiple ones.

The Standard Template Library in C++ provides in-built implementations for several such querying operations. The templated nature of the library allows for the same algorithm to be applicable to all kinds of containers offered by C++.

* Algorithms for Querying Containers*

**⇒** Counts the number of occurences of the `value`

in the container

```
std::count(vector.begin(), vector.end(), value)
```

**⇒** Compute the sum of the contents of the container and store it to the value `init`

. If binary method `function`

is provided, then the method is used for accumulation.

```
std::accumulate(vector.begin(), vector.end(), init)
```

std::accumulate(vector.begin(), vector.end(), init, function)

**⇒** Compute the partial sum of the contents of the container iteratively and store the it to container with `result`

interator as the beginning. If binary method `function`

is provided, then the method is used for the partial operation.

```
std::partial_sum(vector.begin(), vector.end(), result)
```

std::partial_sum(vector.begin(), vector.end(), result, function)

**⇒** Checks for all the elements of the container returning `true`

for the given unary operator.

If all elements return `true`

, the function returns `true`

else returns `false`

. It returns `false`

for an empty range.

```
std::all_of(vector.begin(), vector.end(), unary_function)
```

**⇒** Checks for all the elements of the container returning `true`

for the given unary operator.

If at least one of the elements return `true`

, the function returns `true`

else returns `false`

. It returns `false`

for an empty range.

```
std::any_of(vector.begin(), vector.end(), unary_function)
```

**⇒** Checks for all the elements of the container returning `true`

for the given unary operator.

If none of the elements return `true`

, the function returns `true`

else returns `false`

. It returns `true`

for an empty range.

```
std::none_of(vector.begin(), vector.end(), unary_function)
```

*
IF YOU LIKED THE ARTICLE, DON'T FORGET TO LEAVE A REACTION OR A COMMENT!
*