C++ Coding Reference: is_sorted_until() and is_sorted()

We talked about sorting (unstable and stable) algorithms implemented in C++ STL. The STL algorithm header also provides the is_sorted_until() and is_sorted() which returns the first out-of-order element in iterator, and whether the container e.g. vector is sorted or not.

C++ is_sorted(): Test whether the container is sorted (in-order)

One easy implementation of the is_sorted() algorithm would be to do a linear scan and compare the current element and its next at a time, return false once it is out-of-order. Return true at the end.

template <class T>
bool isSorted(const vector<T>& arr) {
	for (int i = 0; i < arr.size() - 1; ++i) {
		if (arr[i] > arr[i + 1]) {
			return false;
		}
	}
	return true;
}

The algorithm runs at O(N), and it is straightforward to use, like this:

vector<int> nums({ 1, 2, 3, 4, 5});
isSorted<int>(nums); // true

To avoid re-inventing the wheel, we can use std::is_sorted() function from the C++ algorithm package. For example:

vector<int> nums({ 1, 2, 3, 4, 5});
std::is_sorted(begin(nums), end(nums)); // true

As you probably notice, the std::is_sorted() takes two necessary parameters – which are the iterators pointing to the start of the container and the one-position-beyond-the-end of the container. std::is_sorted() also takes an optional third parameter, which specifies the predicate function that can be used to test if two elements are in-order or not. For example, to check if the array is in reverse order, we can do this:

vector<int> nums({ 1, 2, 3, 4, 5});
std::is_sorted(begin(nums), end(nums), [](auto &a, auto &b) {
   return a > b;
}); // true

Alternatively, we can pass the reverse iterators rbegin() and rend().

If we look at the template definitions of std::is_sorted() in the algorithm header, we will notice that std::is_sorted() is based on std::is_sorted_until() which will be detailed in the next section.

template<class _FwdIt,
	class _Pr>
	_NODISCARD inline bool is_sorted(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// test if range is ordered by predicate
	_Adl_verify_range(_First, _Last);
	const auto _UFirst = _Get_unwrapped(_First);
	const auto _ULast = _Get_unwrapped(_Last);
	return (_STD is_sorted_until(_UFirst, _ULast, _Pass_fn(_Pred)) == _ULast);
	}

template<class _FwdIt>
	_NODISCARD inline bool is_sorted(_FwdIt _First, _FwdIt _Last)
	{	// test if range is ordered by operator<
	return (_STD is_sorted(_First, _Last, less<>()));
	}

#if _HAS_CXX17
template<class _ExPo,
	class _FwdIt,
	class _Pr,
	_Enable_if_execution_policy_t<_ExPo> = 0>
	_NODISCARD inline bool is_sorted(_ExPo&&, _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept
	{	// test if range is ordered by predicate
		// not parallelized at present, parallelism expected to be feasible in a future release
	return (_STD is_sorted(_First, _Last, _Pass_fn(_Pred)));
	}

template<class _ExPo,
	class _FwdIt,
	_Enable_if_execution_policy_t<_ExPo> = 0>
	_NODISCARD inline bool is_sorted(_ExPo&&, _FwdIt _First, _FwdIt _Last) noexcept
	{	// test if range is ordered by operator<
		// not parallelized at present, parallelism expected to be feasible in a future release
	return (_STD is_sorted(_First, _Last));
	}
#endif /* _HAS_CXX17 */

C++ is_sorted_until(): Find out the first element that is out of order

The std::is_sorted_until() has the same function signature as std::is_sorted(). It will return the first iterator that is out-of-order or the end() if the original container is in-order. Therefore, the is_sorted() can be simply calling is_sorted_until() to check if the return iterator is end() – beyond the last element of the array/vector.

In the following example, 7 is the first number that is out of order.

vector<int> nums({ 1, 2, 3, 4, 7, 5});
auto n = std::is_sorted_until(begin(nums), end(nums));

Then, iterator n will be pointing to 7 – if we de-reference it using *n we will get 7. Remember to check if the returned iterator is meaningful before de-reference it.

if (n != end(nums)) {
   // do something with *n
}

In algorithm header, the std::is_sorted_until() have some overloaded function signatures – all supporting the generics using template definitions.

// FUNCTION TEMPLATES is_sorted AND is_sorted_until
template<class _FwdIt,
	class _Pr>
	_NODISCARD inline _FwdIt is_sorted_until(const _FwdIt _First, _FwdIt _Last, _Pr _Pred)
	{	// find extent of range that is ordered by predicate
	_Adl_verify_range(_First, _Last);
	auto _UFirst = _Get_unwrapped(_First);
	auto _ULast = _Get_unwrapped(_Last);
	if (_UFirst != _ULast)
		{
		for (auto _UNext = _UFirst; ++_UNext != _ULast; ++_UFirst)
			{
			if (_DEBUG_LT_PRED(_Pred, *_UNext, *_UFirst))
				{
				_ULast = _UNext;
				break;
				}
			}
		}

	_Seek_wrapped(_Last, _ULast);
	return (_Last);
	}

template<class _FwdIt>
	_NODISCARD inline _FwdIt is_sorted_until(_FwdIt _First, _FwdIt _Last)
	{	// find extent of range that is ordered by operator<
	return (_STD is_sorted_until(_First, _Last, less<>()));
	}

#if _HAS_CXX17
template<class _ExPo,
	class _FwdIt,
	class _Pr,
	_Enable_if_execution_policy_t<_ExPo> = 0>
	_NODISCARD inline _FwdIt is_sorted_until(_ExPo&&, const _FwdIt _First, _FwdIt _Last, _Pr _Pred) noexcept
	{	// find extent of range that is ordered by predicate
		// not parallelized at present, parallelism expected to be feasible in a future release
	return (_STD is_sorted_until(_First, _Last, _Pass_fn(_Pred)));
	}

template<class _ExPo,
	class _FwdIt,
	_Enable_if_execution_policy_t<_ExPo> = 0>
	_NODISCARD inline _FwdIt is_sorted_until(_ExPo&&, _FwdIt _First, _FwdIt _Last) noexcept
	{	// find extent of range that is ordered by operator<
		// not parallelized at present, parallelism expected to be feasible in a future release
	return (_STD is_sorted_until(_First, _Last));
	}
#endif /* _HAS_CXX17 */

C/C++ Programming

• Understanding std::transform_reduce in Modern C++
• Implement a Lock Acquire and Release in C++
• Detecting Compile-time vs Runtime in C++: if consteval vs std::is_constant_evaluated()
• C++ Forward References: The Key to Perfect Forwarding
• Understanding dynamic_cast in C++: Safe Downcasting Explained
• C vs C++: Understanding the restrict Keyword and its Role in Optimization
• C++ Lvalue, Rvalue and Rvalue References
• C++ assert vs static_assert
• Why auto_ptr is Deprecated in C++?
• C++ What is the consteval? How is it different to const and constexpr?
• Tutorial on C++ std::move (Transfer Ownership)
• const vs constexpr in C++
• Tutorial on C++ Ranges
• Tutorial on C++ Smart Pointers
• Tutorial on C++ Future, Async and Promise
• The Memory Manager in C/C++: Heap vs Stack
• The String Memory Comparision Function memcmp() in C/C++
• Modern C++ Language Features
• Comparisions of push_back() and emplace_back() in C++ std::vector
• C++ Coding Reference: is_sorted_until() and is_sorted()
• C++ Coding Reference: iota() Setting Incrementing Values to Arrays or Vectors
• C++ Coding Reference: next_permutation() and prev_permutation()
• C++ Coding Reference: count() and count_if()
• C++ Code Reference: std::accumulate() and Examples
• C++ Coding Reference: sort() and stable_sort()
• The Next Permutation Algorithm in C++ std::next_permutation()

–EOF (The Ultimate Computing & Technology Blog) —