CODEWITHSUNDEEP
c++stlsetstd
kiran
kiran

Reputation: 37

why STL set size complexity is O(1), how is it calculated?

A set is internally maintained as a balanced binary tree. The complexity to calculate the size of set is O(1). How the size is calculated, does it maintain any variable to store the size.

Upvotes: 1

Views: 1505

Answers (2)

alcedine
alcedine

Reputation: 949

The specification states only that all sets (actually, all containers) have a size() member function that takes constant time. Other than that, the implementers of your particular version of the standard library may have done it however they wished, as long as it's O(1).

In practice, the size may well be stored in a member variable that gets updated as items are inserted or removed; PiotrNycz' implementers have done just that.

Upvotes: 3

PiotrNycz
PiotrNycz

Reputation: 24347

When you RTFS - you can see that yes - the member variables counting nodes in RB-Tree, which is base for stl-set is there.

E.g. see https://www.sgi.com/tech/stl/stl_tree.h :

size_type _M_node_count; // keeps track of size of tree

size_type size() const { return _M_node_count; }

template <class _Key, class _Value, class _KeyOfValue, 
          class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
  ::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
  // ...
  ++_M_node_count;
  return iterator(__z);
}

Upvotes: 0

Related Questions