size() Vs empty() in vector - why empty() is preferred?

Question

While debugging something, I saw the STL vector::empty() implementation:

bool empty() const
     {return (size() == 0); }

I believe, whenever we are probing the emptiness of vector it is always recommended to use empty over size(). But seeing that implementation, I am wondering, what is the benefit of doing so? Instead, there is a function call overhead in calling empty as it internally calls size()==0.

I thought empty() may be helpful in case of list as size() doesn't guarantees the constant time in list. To verify my assumption, I checked the list implementation and surprisingly, found the same implementation in list as well,

return (size() == 0);

I am bit confused now. If empty internally uses size() then why should we prefer empty over size() ?

Answer 1

Because if you switch from std::vector to std::list or other container, it may be different.

For example some implementations of std::list::size take O(n) and not O(1).

Answer 2

Well, as you say, that's just an implementation detail. std::list can be implemented either with a stored size (constant-time size() but linear-time splice()), or without (constant-time splice() but linear-time size()). By choosing to use empty(), you avoid betting on an implementation detail, when you don't need to know the size.

Answer 3

You would need to write the condition out everytime you use size(). It's convenient to use empty(). This is of course, provided you don't switch containers. As others have pointed out, it is upto the implementation to use size() in empty() or not. However, the standard does gurantee that: empty() is a constant-time operation for all standard containers.

Answer 4

Following the standard, empty() should be preferred as it has constant time complexity regardless of the container type.

In C++03 standard, chapter 23.1, table 65: Container Requirements

Operation:   empty()
Return_type: convertible to bool
Semantics:   equivalent to size()==0
Complexity:  constant

It seems as if in your STL implementation, they took the semantics as the real implementation ignoring the complexity requirements, or size() is constant time in the implementation (stored field).

If size() is not constant time, contact your vendor about std::list<>::empty() not fulfilling the standard container requirements.

Answer 5

In addition to the reasons given above, it's also arguably clearer than foo.size() == 0 and/or !foo.size()

Answer 6

1st, using a function called empty() when you want to know if something is empty makes code more readable, and means you don't have to worry about implementation details. It also means that your code can more easily be adapted to other types of containers, with other characteristics.

2nd, that's just one STL implementation. My GNU C++ one looks like this:

bool
empty() const
{ return begin() == end(); }

This will eventually result in a pointer comparison, while using size() would result in a subtraction (in this implementation).

3rd, it's not very likely to incur the overhead of an extra function call, since the empty()-function is probably inlined (in both of the implementations).

Answer 7

Besides the readability point, which is very valid, what you experienced is simply the artifacts of one particular implementation, not the only possible one.

That is, there is no reason or requirement that empty() be implemented in terms of size() in both the vector and list case, or in deed any other container. If there are better performing alternatives, they should be used, unless the author(s) of the library are incompetent, or more reasonably, lazy.

As for the list and the O(1)-ness of size(), or the lack thereof, you should take into account that list may implement either size() as O(1) or splice(), but not both (thinking about the reason is an interesting exercise.) So in your case, the library you inspected may have implemented size() as O(1) (in which case splice() would be O(n)) and therefore could implement empty() in terms of size() without sacrificing performance, otherwise, that would be a really bad library.

Answer 8

empty() has O(1) implementations for ALL container classes. size() can only provide O(n) implementations for some containers; this is why empty() is preferred.