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 <img src="https://i.stack.imgur.com/d1jQc.png" alt="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.

Since C++11, the complexity of the <code>size</code> member function is constant for all standard containers. <code>std::forward_list</code> which is an implementation of the singly linked list data structure does not provide a <code>size</code> 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.

What are the time complexities for size?

Tags:

c++

big-o

time-complexity

data-structures

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.

767

asked Apr 23 '20 15:04

Poseidaan

1 Answers

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.

answered Nov 20 '22 06:11

eerorika

Related questions
                            
                                C++: Instantiate many templates in library
                            
                                Declare a variable of a class without creating an instance of it
                            
                                Named Default Arguments in pybind11
                            
                                Using enable_if on virtual functions
                            
                                Do logical operators affect each other in a if statement?
                            
                                Is it a missed optimization, when a compile-time known reference takes space in a non-aggregate struct?
                            
                                C++ multi level inheritance with virtual functions [duplicate]
                            
                                Is there a way to shorten a long switch() statement?
                            
                                C++ identifier is undefined
                            
                                Can C++ compilers optimize calls to at()?
                            
                                std::unordered_map constructor with initializer_list and size compiles in main, but not in class definition
                            
                                Difference between SFINAE and tag dispatch
                            
                                Way to declare a large variable depending on a condition
                            
                                Why does std::atomic<std::string> give trivially copyable error? [duplicate]
                            
                                why can C++ "fill" initialize a variable-sized array?
                            
                                C++ initialize variable with lambda
                            
                                Is there any performance difference in just reading an atomic variable compared to a normal variable?
                            
                                How to compare two preprocessor macros with the same name?
                            
                                Calling member function without creating object in C++
                            
                                How do I install libraries for <stropts.h>?

Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!

Donate Us With