Why do we have std::string::npos but no std::vector::npos?

Question

I would like to use -1 to indicate a size that has not yet been computed:

std::vector<std::size_t> sizes(nResults, -1);

and I was wondering why isn't there a more expressive way:

std::vector<std::size_t> sizes(nResults, std::vector<std::size_t>::npos);

Answer 1

It basically comes down to a fairly simple fact: std::string includes searching capability, and that leads to a requirement for telling the caller that a search failed. std::string::npos fulfills that requirement.

std::vector doesn't have any searching capability of its own, so it has no need for telling a caller that a search has failed. Therefore, it has no need for an equivalent of std::string::npos.

The standard algorithms do include searching, so they do need to be able to tell a caller that a search has failed. They work with iterators, not directly with collections, so they use a special iterator (one that should never be dereferenced) for this purpose. As it happens, std::vector::end() returns an iterator suitable for the purpose, so that's used--but this is more or less incidental. It would be done without (for example) any direct involvement by std::vector at all.

Answer 2

From cppreference:

std::size_t is the unsigned integer type of the result of the sizeof operator as well as the sizeof operator and the alignof operator (since C++11)....

...std::size_t can store the maximum size of a theoretically possible object of any type...

size_t is unsigned, and can't represent -1. In reality if you were to attempt to set your sizes to -1, you would actually be setting them to the maximum value representable by a size_t.

Therefore you should not use size_t to represent values which include the possible size of a type in addition to a value indicating that no size has been computed, because any value outside the set of possible sizes can not be represented by a size_t.

You should use a different type which is capable of expressing all of the possible values you wish to represent. Here is one possibility:

struct possibly_computed_size_type
{
    size_t size;
    bool is_computed;
};

Of course, you'll probably want a more expressive solution than this, but the point is that at least possibly_computed_size_type is capable of storing all of the possible values we wish to express.

One possibility is to use an optional type. An optional type can represent the range of values of a type, and an additional value meaning 'the object has no value'. The boost library provides such a type.

The standard library also provides an optional type as an experimental feature. Here is an example I created using this type: http://ideone.com/4J0yfe