What Are the Complexity Guarantees of the Standard Containers

What are the complexity guarantees of the standard containers?

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.

size() complexity of STL containers in G++: which containers are O(n)?

It may change depending on the version of the standard library.

For GCC recent versions (atleast up to 4.6.2) List and ones based off of List are not constant time, but implemented as { return std::distance(begin(), end()); }.

MSVC standard library keeps track of size as it changes and just returns its value (which makes splice() O(n) because it has to count when it splices).

From my /usr/include/c++/4.6.2/bits/stl_list.h :

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

vector, set, deque, and map are constant time. ,

this is std::deque's

  size_type
  size() const
  { return this->_M_impl._M_finish - this->_M_impl._M_start; }

queue and stack are actually container adapters and depend on the underlying container, which can be specified. However the default is deque, which is constant.

Time complexity of queue in C++

Both push() (which internally calls push_back() on the underlying container) and pop()(which internally calls pop_front() on the underlying container) provided by std::queue in C++ STL have a constant O(1) time complexity since they only insert at the end of queue or pop from the front of it. You can check http://www.cplusplus.com/reference/queue/queue/ to find out more about other methods and their time complexities.

C++ std::unordered_map complexity

Regardless of how they're implemented, standard containers provide iterators that meet the iterator requirements. Incrementing an iterator is required to be constant time, so iterating through all the elements of any standard container is O(N).

Are there any standard-layout guarantees for STL-containers?

No, there are no guarantees.

The C++11 Standard explicitly mentions when a class must have standard layout (e.g. the mutex class, the atomic_flag class, etc.).

The word "layout" does not appear in the whole Clause 23 (Containers Library). I believe this is sufficient to assume that no guarantees are given.

STL like container with O(1) performance

In practice, it may be sufficient to use array (vector) and defer costs of inserts and deletes.

Delete element by marking it as deleted, insert element into bin at desired position and remember offset for larger indices.

Inserts and deletes will O(1) plus O(N) cleanup at convenient time; lookup will be O(1) average, O(number of changes since last cleanup) worst case.

Ordered versus unordered containers in C++

Assume that you have both a comparator and a hash function, and therefore you have a free choice between the two. Assume also that you can avoid any single-element operations that are linear in one container but not the other (John Zwinck in a comment makes the excellent point that unordered erase is documented worst-case linear in the size of the container but in practice has been implemented slower even than that).

Then, the main criterion is whether you need to iterate the container in sorted order. If so, then you would expect to use the ordered container. If not, then you would expect to use the unordered container.

As a secondary possibility, the interfaces of the two are sufficiently similar that you might easily test performance of your actual application with both, and choose the faster. It's not a difficult coding task to iterate an unordered container in sorted order, provided that it won't be modified while you're doing it.

Of course there are pitfalls associated with profiling -- your tests might fail to use realistic data. And even if they're OK, your users might fail to use realistic data ;-) For most cases there's nothing better. For specific situations like real-time guarantees, you need to know a lot more about the implementation you're using than the standard tells you (and for that reason you might not use standard containers at all).

The reason I say that performance testing is secondary in this case is just that you could, if you had unlimited development time, profile every possible different way to write your program and pick the best. Since you don't have unlimited development time you primarily choose how to write your code using heuristics. Having chosen something that works and mostly isn't awful, you profile to identify hot code and then choose between plausible-seeming options for that code.

Where can I find all the exception guarantees for the Standard Containers and Algorithms?

Reading the standard can be scary (let's come back to the standard), but Bjarne Stroustrup has written a really nice appendix on this subject in his book 'The C++ Programming Language'. He posted this appendix at

http://www.stroustrup.com/3rd_safe0.html , at
http://www.stroustrup.com/3rd_safe.pdf

It's pretty long and detailed (and well written). You may for example find section E.4 interesting, quote:

E.4 Standard Container Guarantees

If a library operation itself throws an exception, it can – and does –
make sure that the objects on which it operates are left in a
well-defined state. For example, at() throwing out_of_range for a
vector (§16.3.3) is not a problem with exception safety for the vector
. The writer of at() has no problem making sure that a vector is in a
well-defined state before throwing.

In addition, section E.4.1 states

In addition to the basic guarantee, the standard library offers the
strong guarantee for a few operations that insert or remove elements.

have a look at page 956. It contains a table of guarantees for various operations for vector, deque, list and map.
In summary, all operations on those containers are either nothrow or strong, except for N - element insert into map which offers the basic guarantees.

Note: the above text is old and does not address C++11, but should still be correct enough for most aims and purposes.

When it comes to C++11...

the standard first states, about the containers
array, deque, forward_list, list, vector, map, set, unordered_map, unordered_set, queue,stack:
at

23.2.1/10:

Unless otherwise specified (see 23.2.4.1, 23.2.5.1, 23.3.3.4, and
23.3.6.5) all container types defined in this Clause meet the following additional requirements:

— if an exception is thrown by an insert() or emplace() function while
inserting a single element, that function has no effects.

— if an exception is thrown by a push_back() or push_front() function,
that function has no effects.

— no erase(), clear(), pop_back() or pop_front() function throws an
exception.

— no copy constructor or assignment operator of a returned iterator
throws an exception.

— no swap() function throws an exception.

— no swap() function invalidates any references, pointers, or
iterators referring to the elements of the containers being swapped.

The quirks pointed out in the respective sections referred to above (each called Exception safety guarantees) are mostly about special against-the-wall cases like when dealing with exceptions from the contained types' hashing, comparison operations as well as throwing swap and throwing move operations.

---

Related Topics