CODEWITHSUNDEEP
c++stlcontainersstl-algorithm
FelEnd
FelEnd

Reputation: 888

C++ STL: Passing an empty container to lower_bound

Is the behavior for passing an empty container to std::lower_bound defined?

I checked cppreference.com and an old version of the C++ standard that I found online, but couldn't find a definite answer.

The cppreference.com documentation for std::deque::erase has a sentence

The iterator first does not need to be dereferenceable if first==last: erasing an empty range is a no-op.

I miss something like this for std::lower_bound and other algorithms.

Upvotes: 8

Views: 2986

Answers (3)

Roman Odaisky
Roman Odaisky

Reputation: 2941

std::lower_bound answers the question, “Where (as in, just before what iterator value) is the first place that the given element can be inserted without violating the ordering?” If the [first, last) range given is empty, the only place to insert anything is just before last (equal to first), so that’s what lower_bound returns.

Upvotes: 2

Daniel Langr
Daniel Langr

Reputation: 23537

The Standard says:

Returns: The furthermost iterator i in the range [first, last] such that for every iterator j in the range [first, i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

Now:

  1. The range [first, last] for an empty container has a single member, namely the iterator returned by its member function end().
  2. i can therefore by only end().
  3. There is only one viable range [first, i), which is [end, end()).
  4. This range is empty, since there is no element that is greater or equal than end() and lower then end() at the same time.

Since there is no every iterator j, I guess the quoted sentence can be rewritten into:

Returns: The furthermost iterator i in the range [first, last].

Which implies that the only i that can be returned is end().

Upvotes: 4

Fureeish
Fureeish

Reputation: 13444

Cppreference on the return value of std::lower_bound(first, last):

"[it returns] Iterator pointing to the first element that is not less than value, or last if no such element is found.".

(emphasis mine)

In an empty range, there will be no elements that satisfy the criteria, so last will be returned.

Concluding from this, applying std::lower_bound (and similar) on the empty range is well-defined. It does nothing and returns last, which is equal to first.

Upvotes: 11

Related Questions