Does the C++ standard guarantee anything about algorithms operating on empty containers?

user_5101335 0
Viewed 69

For instance,

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<int> empty{};
  std::reverse(empty.begin(), empty.end());
  std::cout << "Sum: " << std::accumulate(empty.cbegin(), empty.cend(), 0) << std::endl;
  std::cout << empty.size();
}

builds and runs as I expect:

sum: 0
size: 0

Can I be guaranteed this behavior will happen on any standard-compliant compiler?

undefined-behavior std c++
1 Answers

Since standard library algorithms operate on iterator ranges, algorithms are guaranteed to be safe and valid on any valid iterator range passed to them. Now we only need to be concerned with what valid iterator range stands for.

Requirements on iterators forming an iterator range:

  • They have to refer to elements (or one past the last element) of the same container
  • It is possible to reach end by repeatedly incrementing begin. In other words, end must not precede begin.

After these requirements satisfied, we can think of any valid range as a left-inclusive range: [begin, end). So then the range have the following properties:

  • If being is equal to end, the range is empty
  • If begin isn't equal to end, there's at least one element in the range, and being refers to the first element
  • So, we can increment begin some number of times until begin == end (when this happens, the range is still valid)

It is these properties that provide support for the convenient usage of iterators. The <algorithms> internals are based on these properties as well.

We have to be aware that the compiler cannot reinforce these requirements, it is up to us to ensure the validity of passed range (sometimes there are quite a few factors to consider).

So, yes, begin == end is still a valid range, when passed to an algorithm, so the output we get is also expectedly valid.

user_146247290
Related