The complexity of std::list::size() operation is O(N) while for other standard containers (vector, queue) and std::string it is O(1).

This is caused by splice() operation specific to lists that takes some range of elements from one list and inserts it to the specified position of another one.

This splicing is done with O(1) complexity and is extremely useful in some cases but it blocks all the opportunities for storing/knowing list length.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s