STL Algorithms

A practical reference of the <algorithm> and <numeric> functions you will actually reach for in interviews. Every entry includes a signature, what it does, complexity, at least one code example, and the common pitfalls.

All examples assume:

cpp

#include <bits/stdc++.h>
using namespace std;

Most algorithms take a pair of iterators [first, last) — a half-open range — and most return either an iterator or a transformed range. Remember that v.end() is one past the last element, not the last element itself.

Sorting & Searching

`sort`

Header: #include <algorithm>Complexity: O(n log n)

What it does

Sorts a range in place using a hybrid introsort (quicksort + heapsort + insertion sort). Ascending by default.

Signature and usage

cpp

vector<int> v = {3, 1, 4, 1, 5};

sort(v.begin(), v.end());                              // ascending
sort(v.begin(), v.end(), greater<int>());              // descending
sort(v.begin(), v.end(), [](int a, int b){ return a > b; });  // same

// Sorting pairs: lexicographic by default (first, then second)
vector<pair<int,int>> p = {{2,3}, {1,5}, {2,1}};
sort(p.begin(), p.end());                              // {1,5},{2,1},{2,3}

// Sort by second key
sort(p.begin(), p.end(),
     [](auto& a, auto& b){ return a.second < b.second; });

// Sorting custom structs
struct Point { int x, y; };
vector<Point> pts;
sort(pts.begin(), pts.end(),
     [](const Point& a, const Point& b){
         if (a.x != b.x) return a.x < b.x;
         return a.y < b.y;
     });

Common uses

Any problem that benefits from monotonic scans, two-pointer passes, or binary search downstream.
Interval problems (sort by start or end).
Greedy algorithms (sort by some weight).

Gotchas

Comparator must be a strict weak ordering. Using <= instead of < is undefined behavior and can crash on libstdc++ in release mode. Always return a < b, never return a <= b.
Comparator on floats with NaN violates strict weak ordering. Filter NaNs first.

Interview Tip

If you need both the sorted values and their original indices, build vector<pair<T,int>> with {value, originalIndex} and sort that.

`stable_sort`

Header: #include <algorithm>Complexity: O(n log n), with O(n) extra memory when available, else O(n log² n) in-place

What it does

Like sort, but preserves the relative order of elements that compare equal.

cpp

vector<pair<string,int>> people = {{"Alice",30},{"Bob",25},{"Carol",30}};
stable_sort(people.begin(), people.end(),
            [](auto& a, auto& b){ return a.second < b.second; });
// Alice and Carol both have age 30; Alice stays before Carol.

Interview Tip

Use stable_sort when sorting by a secondary key after a primary sort, to preserve the primary order among ties.

`partial_sort`

Header: #include <algorithm>Complexity: O(n log k)

What it does

Rearranges so that [first, middle) contains the smallest k = middle - first elements in sorted order. The rest is unspecified.

cpp

vector<int> v = {5, 2, 8, 1, 9, 3};
partial_sort(v.begin(), v.begin() + 3, v.end());
// v starts with: 1, 2, 3, then the rest in any order

Common uses

Top-k smallest (or largest with greater<>()).
Faster than a full sort when k << n.

`nth_element`

Header: #include <algorithm>Complexity: O(n) average, O(n²) worst

What it does

Partitions the range so that the element at nth is the one that would be there in a fully sorted range, everything before it is <= nth, and everything after it is >= nth. No further ordering guarantees.

cpp

vector<int> v = {5, 2, 8, 1, 9, 3, 7};
int k = 3;
nth_element(v.begin(), v.begin() + k, v.end());
cout << v[k];        // the (k+1)-th smallest, 0-indexed

Common uses

Kth smallest / largest in O(n) without sorting.
Median: nth_element at v.size()/2.

Gotchas

Worst-case O(n²). Modern libstdc++ uses introselect, which falls back to O(n log n), but don't bank on that for adversarial inputs without reading your stdlib.

`binary_search`

Header: #include <algorithm>Complexity: O(log n)

What it does

Returns bool — whether a value exists in a sorted range. Requires the range to be sorted.

cpp

vector<int> v = {1, 2, 4, 4, 5};
bool has4 = binary_search(v.begin(), v.end(), 4);   // true

Gotchas

Returns only a bool. If you need the position, use lower_bound instead.

Interview Tip

Almost always skip binary_search in favor of lower_bound — the latter gives you both presence and position in the same call.

`lower_bound`

Header: #include <algorithm>Complexity: O(log n) on random-access iterators; O(n) on forward iterators (like list)

What it does

Returns an iterator to the first element >= value in a sorted range.

cpp

vector<int> v = {1, 3, 3, 5, 7};

auto it = lower_bound(v.begin(), v.end(), 3);
int idx = it - v.begin();                          // 1

// Does 4 exist?
auto it2 = lower_bound(v.begin(), v.end(), 4);
bool has4 = (it2 != v.end() && *it2 == 4);         // false

// Smallest element > x: use upper_bound directly.
// Largest element <= x: lower_bound then step back, if possible.
auto it3 = lower_bound(v.begin(), v.end(), 4);
if (it3 != v.begin()) {
    int leq = *prev(it3);                          // 3
}

Common uses

Insertion point into a sorted vector.
Binary search with position: auto it = lower_bound(...); if (it != v.end() && *it == x) { ... }.
Replacing the "largest index i with a[i] <= x" pattern.

Gotchas

Must be sorted with the same comparator you pass to lower_bound. If you sorted descending, pass greater<int>().
On set/map, prefer the member s.lower_bound(x) over the free function — the member is O(log n), the free function on tree iterators is O(n).

`upper_bound`

Header: #include <algorithm>Complexity: O(log n)

What it does

Returns an iterator to the first element > value in a sorted range.

cpp

vector<int> v = {1, 3, 3, 5, 7};
auto it = upper_bound(v.begin(), v.end(), 3);      // points at 5

// Count occurrences of x in a sorted range:
int cnt = upper_bound(v.begin(), v.end(), 3)
        - lower_bound(v.begin(), v.end(), 3);      // 2

Interview Tip

upper_bound(x) - lower_bound(x) is the fastest way to count occurrences in a sorted vector — faster than count, which is O(n).

`equal_range`

Header: #include <algorithm>Complexity: O(log n)

What it does

Returns a pair (lower_bound, upper_bound) in one call — all elements equal to value.

cpp

vector<int> v = {1, 3, 3, 3, 5};
auto [lo, hi] = equal_range(v.begin(), v.end(), 3);
for (auto it = lo; it != hi; ++it) cout << *it << ' ';  // 3 3 3

Modifying Sequence Operations

`reverse`

Complexity: O(n)

cpp

vector<int> v = {1,2,3,4};
reverse(v.begin(), v.end());       // {4,3,2,1}

string s = "hello";
reverse(s.begin(), s.end());       // "olleh"

Reverses a range in place. Classic uses: palindrome checks, reversing a linked list (iteratively), reversing a portion of a string.

`rotate`

Complexity: O(n)

What it does

Shifts elements so that middle becomes the new first element. Returns the iterator to the element that was first before the rotation.

cpp

vector<int> v = {1,2,3,4,5};
rotate(v.begin(), v.begin() + 2, v.end());   // {3,4,5,1,2}

Interview Tip

Array rotation by k: rotate(v.begin(), v.begin() + k % v.size(), v.end()).

`swap`

Complexity: O(1) for primitives and types with O(1) move; O(n) for full-container swaps of some containers.

cpp

int a = 1, b = 2;
swap(a, b);

vector<int> x = {1,2,3}, y = {4,5};
swap(x, y);                        // O(1): swaps internal pointers

Interview tip: swap(a, b) is both cleaner and faster than a manual temp variable, and works on any STL container.

`fill`

Complexity: O(n)

cpp

vector<int> v(5);
fill(v.begin(), v.end(), 7);       // {7,7,7,7,7}

Use for initializing sub-ranges. fill_n(v.begin(), k, 7) fills k elements.

`iota`

Header: #include <numeric>Complexity: O(n)

What it does

Fills a range with sequentially increasing values: start, start+1, start+2, ...

cpp

vector<int> v(5);
iota(v.begin(), v.end(), 1);       // {1,2,3,4,5}

// Indirect sort — sort indices by the values they point to:
vector<int> a = {30, 10, 20};
vector<int> idx(a.size());
iota(idx.begin(), idx.end(), 0);                          // {0,1,2}
sort(idx.begin(), idx.end(),
     [&](int i, int j){ return a[i] < a[j]; });           // {1,2,0}

Interview Tip

Indirect sorting via iota + a comparator that looks up values is the clean way to rank items without moving them.

`copy` and `copy_if`

Complexity: O(n)

cpp

vector<int> src = {1,2,3,4};
vector<int> dst(4);
copy(src.begin(), src.end(), dst.begin());

vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens),
        [](int x){ return x % 2 == 0; });

Interview Tip

back_inserter(v) is the canonical way to copy into a vector when you don't know the final size.

`unique`

Complexity: O(n)

What it does

Collapses consecutive duplicates in place, returning an iterator to the new end. Does not shrink the container.

cpp

vector<int> v = {1,1,2,3,3,3,4};
auto nend = unique(v.begin(), v.end());        // {1,2,3,4,?,?,?}
v.erase(nend, v.end());                        // {1,2,3,4}

// To deduplicate unsorted input:
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());  // erase-unique idiom

Gotchas

Requires sorted input to remove all duplicates (not just adjacent ones).
unique doesn't actually erase anything — the container's size is unchanged until you call erase.

`remove` and `remove_if`

Complexity: O(n)

What it does

Moves all elements not equal to the value (or not satisfying the predicate) to the front, returning an iterator to the new end. Again, does not actually shrink.

cpp

vector<int> v = {1,2,3,2,1};
v.erase(remove(v.begin(), v.end(), 2), v.end());       // {1,3,1}

v.erase(remove_if(v.begin(), v.end(),
                  [](int x){ return x % 2 == 0; }),
        v.end());                                      // erase all evens

Interview Tip

The erase-remove idiom (v.erase(remove_if(...), v.end())) is the standard way to filter a vector in place.

`replace` and `replace_if`

Complexity: O(n)

cpp

vector<int> v = {1,2,3,2,4};
replace(v.begin(), v.end(), 2, 99);                    // {1,99,3,99,4}

replace_if(v.begin(), v.end(),
           [](int x){ return x > 50; }, 0);            // {1,0,3,0,4}

`transform`

Complexity: O(n)

What it does

Applies a function to each element in a range, writing the output to a (possibly same) destination range.

cpp

vector<int> v = {1,2,3,4};
vector<int> out(v.size());
transform(v.begin(), v.end(), out.begin(),
          [](int x){ return x * x; });               // {1,4,9,16}

// Two-range form: element-wise add
vector<int> a = {1,2,3}, b = {10,20,30}, sum(3);
transform(a.begin(), a.end(), b.begin(), sum.begin(),
          plus<int>());                              // {11,22,33}

// In-place uppercase
string s = "hello";
transform(s.begin(), s.end(), s.begin(),
          [](unsigned char c){ return toupper(c); }); // "HELLO"

Gotchas

toupper/tolower on char is UB for negative char values. Cast through unsigned char first (as above).

Counting, Finding, Min/Max

`count` / `count_if`

Complexity: O(n)

cpp

vector<int> v = {1,2,2,3,2};
int twos = count(v.begin(), v.end(), 2);                     // 3
int big  = count_if(v.begin(), v.end(),
                    [](int x){ return x > 1; });             // 4

For sorted input, upper_bound - lower_bound beats count (O(log n) vs O(n)).

`find` / `find_if`

Complexity: O(n)

cpp

vector<int> v = {1,2,3,4};
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) cout << "found at " << it - v.begin();

auto it2 = find_if(v.begin(), v.end(),
                   [](int x){ return x > 2; });

`find_first_of`

Complexity: O(n * m)

What it does

Finds the first position in [first1, last1) that matches any element in [first2, last2).

cpp

string s = "hello world";
string vowels = "aeiou";
auto it = find_first_of(s.begin(), s.end(), vowels.begin(), vowels.end());
// it points at 'e'

`adjacent_find`

Complexity: O(n)

Returns an iterator to the first pair of adjacent equal elements (or the first that satisfies a binary predicate).

cpp

vector<int> v = {1,2,3,3,4};
auto it = adjacent_find(v.begin(), v.end());     // points at first 3

`min_element` / `max_element`

Complexity: O(n)

cpp

vector<int> v = {3,1,4,1,5,9,2};
auto mn = min_element(v.begin(), v.end());           // iterator to 1
auto mx = max_element(v.begin(), v.end());           // iterator to 9
int maxVal = *mx;
int maxIdx = mx - v.begin();

// Custom comparator
auto longest = max_element(words.begin(), words.end(),
    [](auto& a, auto& b){ return a.size() < b.size(); });

Interview Tip

min_element / max_element return iterators, not values. Dereference to get the value; subtract .begin() to get the index.

`min`, `max`

Complexity: O(1) for two args; O(n) over initializer list of n items.

cpp

int a = min(3, 5);
int b = max({1, 4, 2, 7, 3});       // initializer list -> 7
int c = min({10, 2, 7}, greater<int>());  // custom comparator -> 10 (largest under "greater")

`minmax_element`

Complexity: O(n), with at most 3n/2 comparisons

Returns a pair of iterators {min, max} in a single pass.

cpp

vector<int> v = {3,1,4,1,5,9,2};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << *lo << ' ' << *hi;                          // 1 9

`all_of`, `any_of`, `none_of`

Complexity: O(n)

cpp

vector<int> v = {2,4,6};
bool allEven  = all_of(v.begin(), v.end(),  [](int x){ return x%2==0; }); // true
bool anyBig   = any_of(v.begin(), v.end(),  [](int x){ return x>5; });    // true
bool noneNeg  = none_of(v.begin(), v.end(), [](int x){ return x<0; });    // true

Short-circuit on the first hit/miss.

Numeric Algorithms

`accumulate`

Header: #include <numeric>Complexity: O(n)

What it does

Reduces a range to a single value using + (or a custom binary op).

cpp

vector<int> v = {1,2,3,4};
int sum = accumulate(v.begin(), v.end(), 0);                   // 10
long long sll = accumulate(v.begin(), v.end(), 0LL);           // avoid int overflow

// Product
long long prod = accumulate(v.begin(), v.end(), 1LL,
                            multiplies<long long>());          // 24

// Custom reduction: maximum
int mx = accumulate(v.begin(), v.end(), INT_MIN,
                    [](int a, int b){ return max(a, b); });

// Sum of squares as long long
long long ss = accumulate(v.begin(), v.end(), 0LL,
    [](long long acc, int x){ return acc + (long long)x * x; });

Gotchas

The initial value determines the accumulation type. accumulate(v.begin(), v.end(), 0) on a vector of ints returns an int and will overflow silently if the sum exceeds INT_MAX. Pass 0LL for long long, 0.0 for double.

Interview Tip

Whenever you sum a vector of ints in an interview, write 0LL unless you're sure the sum fits in int. Silent overflow is a very common bug.

`partial_sum`

Header: #include <numeric>Complexity: O(n)

What it does

Writes the running total (prefix sum) into an output range.

cpp

vector<int> v = {1,2,3,4};
vector<int> ps(v.size());
partial_sum(v.begin(), v.end(), ps.begin());         // {1,3,6,10}

// In place:
partial_sum(v.begin(), v.end(), v.begin());          // {1,3,6,10}

Interview Tip

Prefix sum problems: do this once, then range sum [l, r] becomes ps[r] - ps[l-1] in O(1).

`adjacent_difference`

Header: #include <numeric>Complexity: O(n)

Writes the differences between consecutive elements (first element copied as-is).

cpp

vector<int> ps = {1,3,6,10};
vector<int> diff(ps.size());
adjacent_difference(ps.begin(), ps.end(), diff.begin());  // {1,2,3,4}

Inverse of partial_sum. Handy to recover original data from a prefix sum.

`inner_product`

Header: #include <numeric>Complexity: O(n)

Dot product (or generalized fold over two ranges).

cpp

vector<int> a = {1,2,3}, b = {4,5,6};
int dot = inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4+2*5+3*6 = 32

// Custom ops: count positions where a[i] != b[i]
int diff = inner_product(a.begin(), a.end(), b.begin(),
                         0,
                         plus<int>(),
                         not_equal_to<int>());

Permutations

`next_permutation`

Complexity: O(n) per call, O(n · n!) for the full iteration

What it does

Rearranges the range into the next lexicographically greater permutation. Returns false and resets to the smallest permutation if already the largest.

cpp

vector<int> v = {1,2,3};
do {
    for (int x : v) cout << x;
    cout << ' ';
} while (next_permutation(v.begin(), v.end()));
// 123 132 213 231 312 321

Gotchas

Starts from the current permutation. To enumerate all permutations, sort the range first so you start at the smallest.
Works with duplicates — generates only distinct permutations.

Interview Tip

"Next greater number with same digits" is one next_permutation call on the digit string.

`prev_permutation`

Complexity: O(n) per call

Like next_permutation, but moves to the previous permutation.

cpp

vector<int> v = {3,2,1};
do {
    // ...
} while (prev_permutation(v.begin(), v.end()));

Heap Operations

Heap functions turn any random-access range into a heap managed in place. Useful when you already have a vector and don't want to convert to priority_queue.

`make_heap`

Complexity: O(n)

cpp

vector<int> v = {3,1,4,1,5,9,2};
make_heap(v.begin(), v.end());         // max-heap; v[0] is now 9

`push_heap`

Complexity: O(log n)

What it does

Assumes [first, last-1) is already a heap and the new element at last-1 needs to be sifted up.

cpp

v.push_back(7);                        // add to end
push_heap(v.begin(), v.end());         // restore heap

`pop_heap`

Complexity: O(log n)

Swaps the top with last-1 and re-heapifies [first, last-1). The popped element is now at the back of the range — pop it off yourself.

cpp

pop_heap(v.begin(), v.end());
int top = v.back();
v.pop_back();

`sort_heap`

Complexity: O(n log n)

Sorts a heap in place (turning a max-heap into ascending order).

cpp

make_heap(v.begin(), v.end());
sort_heap(v.begin(), v.end());          // ascending

Interview Tip

sort_heap after make_heap is a concrete way to show you understand heapsort. Practically, just call sort, which uses introsort (faster).

Partitioning

`partition`

Complexity: O(n)

What it does

Rearranges the range so that all elements satisfying a predicate come before those that don't. Returns an iterator to the first element of the "false" group. Relative order is not preserved.

cpp

vector<int> v = {1,2,3,4,5,6};
auto mid = partition(v.begin(), v.end(),
                     [](int x){ return x % 2 == 0; });
// v might now be: {6,2,4,3,5,1} — evens first
// mid points at the first odd element

`stable_partition`

Complexity: O(n log n) worst, O(n) with extra memory

Same as partition, but preserves the relative order within each group.

cpp

vector<int> v = {1,2,3,4,5,6};
stable_partition(v.begin(), v.end(),
                 [](int x){ return x % 2 == 0; });
// v is now exactly {2,4,6,1,3,5}

Cheat Sheet

Algorithm	Category	Complexity	Returns
`sort`	sort	O(n log n)	void
`stable_sort`	sort	O(n log n)	void
`partial_sort`	sort	O(n log k)	void
`nth_element`	partition	O(n) avg	void
`binary_search`	search	O(log n)	bool
`lower_bound`	search	O(log n)	iterator
`upper_bound`	search	O(log n)	iterator
`equal_range`	search	O(log n)	pair of iterators
`reverse`	modify	O(n)	void
`rotate`	modify	O(n)	iterator
`swap`	modify	O(1)	void
`fill`	modify	O(n)	void
`iota`	modify	O(n)	void
`copy` / `copy_if`	modify	O(n)	iterator to new end
`unique`	modify	O(n)	iterator to new end
`remove` / `remove_if`	modify	O(n)	iterator to new end
`replace` / `replace_if`	modify	O(n)	void
`transform`	modify	O(n)	iterator to new end
`count` / `count_if`	count	O(n)	integer
`find` / `find_if`	search	O(n)	iterator
`find_first_of`	search	O(n·m)	iterator
`adjacent_find`	search	O(n)	iterator
`min_element` / `max_element`	min/max	O(n)	iterator
`min` / `max`	min/max	O(1) or O(n)	value
`minmax_element`	min/max	O(n)	pair of iterators
`all_of` / `any_of` / `none_of`	predicate	O(n)	bool
`accumulate`	numeric	O(n)	value
`partial_sum`	numeric	O(n)	iterator
`adjacent_difference`	numeric	O(n)	iterator
`inner_product`	numeric	O(n)	value
`next_permutation`	permutation	O(n)	bool
`prev_permutation`	permutation	O(n)	bool
`make_heap`	heap	O(n)	void
`push_heap`	heap	O(log n)	void
`pop_heap`	heap	O(log n)	void
`sort_heap`	heap	O(n log n)	void
`partition`	partition	O(n)	iterator
`stable_partition`	partition	O(n log n)	iterator

Patterns to memorize

Dedupe a vector: sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
Filter in place: v.erase(remove_if(v.begin(), v.end(), pred), v.end());
Count in sorted range: upper_bound(...) - lower_bound(...)
Indirect sort: iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j){ return a[i] < a[j]; });
Prefix sum: partial_sum(v.begin(), v.end(), ps.begin());
All permutations: sort(v.begin(), v.end()); do { ... } while (next_permutation(v.begin(), v.end()));
Kth smallest in O(n): nth_element(v.begin(), v.begin() + k, v.end()); cout << v[k];
Long long sum: accumulate(v.begin(), v.end(), 0LL);

STL Algorithms ​

Sorting & Searching ​

sort ​

What it does ​

Signature and usage ​

Common uses ​

Gotchas ​

Interview Tip ​

stable_sort ​

What it does ​

Interview Tip ​

partial_sort ​

What it does ​

Common uses ​

nth_element ​

What it does ​

Common uses ​

Gotchas ​

binary_search ​

What it does ​

Gotchas ​

Interview Tip ​

lower_bound ​

What it does ​

Common uses ​

Gotchas ​

upper_bound ​

What it does ​

Interview Tip ​

equal_range ​

What it does ​

Modifying Sequence Operations ​

reverse ​

rotate ​

What it does ​

Interview Tip ​

swap ​

fill ​

iota ​

What it does ​

Interview Tip ​

copy and copy_if ​

Interview Tip ​

unique ​

What it does ​

Gotchas ​

remove and remove_if ​

What it does ​

Interview Tip ​

replace and replace_if ​

transform ​

What it does ​

Gotchas ​

Counting, Finding, Min/Max ​

count / count_if ​

find / find_if ​

find_first_of ​

What it does ​

adjacent_find ​

min_element / max_element ​

Interview Tip ​

min, max ​

minmax_element ​

all_of, any_of, none_of ​

Numeric Algorithms ​

accumulate ​

What it does ​

Gotchas ​

Interview Tip ​

partial_sum ​

What it does ​

Interview Tip ​

adjacent_difference ​

inner_product ​

Permutations ​

next_permutation ​

What it does ​

Gotchas ​

Interview Tip ​

prev_permutation ​

STL Algorithms

Sorting & Searching

`sort`

What it does

Signature and usage

Common uses

Gotchas

Interview Tip

`stable_sort`

What it does

Interview Tip

`partial_sort`

What it does

Common uses

`nth_element`

What it does

Common uses

Gotchas

`binary_search`

What it does

Gotchas

Interview Tip

`lower_bound`

What it does

Common uses

Gotchas

`upper_bound`

What it does

Interview Tip

`equal_range`

What it does

Modifying Sequence Operations

`reverse`

`rotate`

What it does

Interview Tip

`swap`

`fill`

`iota`

What it does

Interview Tip

`copy` and `copy_if`

Interview Tip

`unique`

What it does

Gotchas

`remove` and `remove_if`

What it does

Interview Tip

`replace` and `replace_if`

`transform`

What it does

Gotchas

Counting, Finding, Min/Max

`count` / `count_if`

`find` / `find_if`

`find_first_of`

What it does

`adjacent_find`

`min_element` / `max_element`

Interview Tip

`min`, `max`

`minmax_element`

`all_of`, `any_of`, `none_of`

Numeric Algorithms

`accumulate`

What it does

Gotchas

Interview Tip

`partial_sum`

What it does

Interview Tip

`adjacent_difference`

`inner_product`

Permutations

`next_permutation`

What it does

Gotchas

Interview Tip

`prev_permutation`