What are the complexity guarantees of the standard containers?

by

I found the nice resource Standard C++ Containers. Probably this is what you all looking for.

VECTOR

Constructors

vector<T> v;              Make an empty vector.                                     O(1)
vector<T> v(n);           Make a vector with N elements.                            O(n)
vector<T> v(n, value);    Make a vector with N elements, initialized to value.      O(n)
vector<T> v(begin, end);  Make a vector and copy the elements from begin to end.    O(n)

Accessors

v[i]          Return (or set) the I'th element.                        O(1)
v.at(i)       Return (or set) the I'th element, with bounds checking.  O(1)
v.size()      Return current number of elements.                       O(1)
v.empty()     Return true if vector is empty.                          O(1)
v.begin()     Return random access iterator to start.                  O(1)
v.end()       Return random access iterator to end.                    O(1)
v.front()     Return the first element.                                O(1)
v.back()      Return the last element.                                 O(1)
v.capacity()  Return maximum number of elements.                       O(1)

Modifiers

v.push_back(value)         Add value to end.                                                O(1) (amortized)
v.insert(iterator, value)  Insert value at the position indexed by iterator.                O(n)
v.pop_back()               Remove value from end.                                           O(1)
v.assign(begin, end)       Clear the container and copy in the elements from begin to end.  O(n)
v.erase(iterator)          Erase value indexed by iterator.                                 O(n)
v.erase(begin, end)        Erase the elements from begin to end.                            O(n)

For other containers, refer to the page.

More Related Contents:

  1. How can I use std::maps with user-defined types as key?
  2. Why use iterators instead of array indices?
  3. Why isn’t vector a STL container?
  4. Is list::size() really O(n)?
  5. Heterogeneous containers in C++
  6. Copy map values to vector in STL [duplicate]
  7. What is an iterator’s default value?
  8. Why does storing references (not pointers) in containers in C++ not work?
  9. Template class with template container
  10. How can std::make_heap be implemented while making at most 3N comparisons?
  11. What is the right approach when using STL container for median calculation?
  12. Do STL iterators guarantee validity after collection was changed?
  13. General use cases for C++ containers
  14. What’s the time complexity of iterating through a std::set/std::map?
  15. In which scenario do I use a particular STL container?
  16. What happens if you call erase() on a map element while iterating from begin to end?
  17. Floating point keys in std:map
  18. Is the size of std::array defined by standard
  19. Difference between erase and remove
  20. Why is the C++ initializer_list behavior for std::vector and std::array different?
  21. Sorting a vector in descending order
  22. std::map emplace without copying value
  23. C++ Double Address Operator? (&&)
  24. how portable is end iterator decrement?
  25. Can raw pointers be used instead of iterators with STL algorithms for containers with linear storage?
  26. STL remove doesn’t work as expected?
  27. std::back_inserter for a std::set?
  28. “Proper” way to store binary data with C++/STL
  29. C++ template function compiles in header but not implementation
  30. Insert into an STL queue using std::copy

Leave a Comment