Tutorial :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() ?


Solution:1

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 guarantee that: empty() is a constant-time operation for all standard containers.


Solution:2

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).


Solution:3

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.


Solution: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.


Solution:5

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).


Solution:6

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.


Solution:7

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


Solution:8

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.


Solution:9

Prefer to use use empty() than size() because, each container might implement empty() implementation in a different way to get the constant time operation.

example:

vector implements as : bool empty() const { // test if sequence is empty return (size() == 0); }

list implements as :

        bool empty() const      {   // test if sequence is empty      return (_Mysize == 0);      }  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »