6

I am studying the complexity of various operations of the different STL containers. Through a different question on this site I have found this chart.

website link

enter image description here

One operation I noticed was missing form this chart was the size operation. I would suppose that if one knew the complexity of .begin and .end one could also calculate the complexity for size. But those are also missing.

I have found an answer similar to what I am looking for in this question, but this one is for Java so it does not cover all the STL containers and it only defines the big O of size for a few of the given datatypes.

Does anyone know the complexity for the .size operation of the various containers or could someone give me a pointer as to where I could find these complexities. Any help would be greatly appreciated.

Also, if my question is wrongly phrased and/or off-topic. Do not hesitate to suggest an edit.

Poseidaan
  • 291
  • 1
  • 9

1 Answers1

11

Since C++11, the complexity of the size member function is constant for all standard containers.

std::forward_list which is an implementation of the singly linked list data structure does not provide a size member function. The size can be calculated in linear time using the iterators.

Aside from standard C++ containers, all data structures can be augmented with a separately stored size variable to achieve such constant complexity at the cost of small constant overhead on insert and delete operations. Array is special in regard that it does not require any additional overhead assuming iterator to end is stored.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • 1
    Not constant complexity for all standard versions though. – Jarod42 Apr 23 '20 at 15:13
  • (Note that not all containers have a `size` member function; for `std::forward_list` you’d need to store it separately or calculate it linearly) – Daniel H Apr 23 '20 at 15:18