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

  • Time：2020-09-17 14:37:27
  • Class：Weblog
  • Read：29

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.

1
2
3
4
5
6
7
8
9

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;
}
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:

1
2

vector<int> nums({ 1, 2, 3, 4, 5});
isSorted<int>(nums); // true
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:

1
2

vector<int> nums({ 1, 2, 3, 4, 5});
std::is_sorted(begin(nums), end(nums)); // true
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:

1
2
3
4

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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 */
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.

1
2

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

1
2
3

if (n != end(nums)) {
   // do something with *n
}
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

// 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 */
// 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 */

–EOF (The Ultimate Computing & Technology Blog) —

Recommend：
How to Balance a Binary Search Tree using Recursive Inorder Trav
Finding the Lucky Numbers in a Matrix
Factory Design Pattern in Object Oriented Design Programming
Algorithm to Find Minimum Removals to Make Valid Parentheses
Greedy Algorithm to Validate Stack Sequences
Why is Web Hosting Important for Bloggers?
How to Write More Local Content (and Why You Should)
8 Ways To Monetize Your Blog Without Driving Away Visitors/Users
5 Ways Bloggers Can Find Marketing Inspiration
5 Helpful Sales Enablement Blogs For Empowering Salespeople
Share：Facebook Twitter
Comment list
Comment add