The complexity of each STL algorithm is specified using big O notation. STL algorithms are created with performance in mind. Therefore, they do not allocate memory nor have a time complexity higher than O(n log n). Algorithms that do not fit these criteria are not included even if they are fairly common operations.
Note the exception of std::stable_sort() , std::inplace_merge(), and std::stable_partition() . Many STL implementations tend to temporarily allocate memory during these operation.
For example, an algorithm which tests whether a non-sorted range contains duplicates. One option is to implement it by iterating through the range and search the rest of the range for a duplicate. This will result ...
