Why does std::list have a max size?

Question

If std::list is a linked list then why is there a limit on how many elements you can have? Each element is a link to a new node and there's no limit on how many pointers you can have.

Answer 1

The simple answer is because the standard says so:

23.2.1 Requirements for containers Table 96 — Container requirements p. 747 for N4296:

a.max_size(); size_type; distance(begin(),end()) for the largest possible container

This, most probably, comes from the fact that in c++ algorithms separated from the containers. Algorithms are written as templates, so they basically duck type code, they expect some contracts to be fulfilled (i.e. providing some API). There are algorithms written for all containers so they expect whatever is passed as a container to implement full API, even if sometimes a particular method does not have much theoretical sense it must be implemented.

That said, technically there is an upper bound anyway so it's good idea to use it in such cases. Funnily enough, it is practically impossible to hit the limit you get from std::list::max_size() (i.e. you would run OOM), yet alone the theoretical infinity.

Answer 2

there's no limit on how many pointers you can have

There's a limit on how many distinct pointer values there can possibly be, based on the size of a pointer. For example, if a pointer occupies 64 bits in a particular implementation, then max_size() could safely return 2⁶⁴-1. In fact it could be rather less than this, since each linked list node will be bigger than 1 byte.

Answer 3

If std::list is a linked list then why is there a limit on how many elements you can have?

Because the max_size() function is a requirement for all standard containers.

Each element is a link to a new node and there's no limit on how many pointers you can have.

Yes there is: the size must be representable by size_type, so a limit is that type's maximum value. There's probably no reason for it to be less than that.