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

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

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：
Hands Up and Step Slowly Away from the Keyboard: Why Good Execut
How to Improve Bad Blog Posts
5 Things That Bloggers Use in Their Craft
How To Increase Your Ecommerce Sales Using Social Media
Keyword Rank Tracking: What Newbie Bloggers Need to Know
Why Digital Products are the Key to Success for Bloggers
Why You Should Consider Alternative Domain Name Extensions for y
How to Create a Successful WordPress Site
How to Launch an E-Course the Right Way as a Blogger
Is Malaysia finally cleaning up corruption? I think not.
Share：Facebook Twitter
Comment list
Comment add