How does C++ associative containers iterator increment work?

user_5701640 0
Viewed 89

For such C++ STLs associative containers like std::set, std::multiset, std::map or std::multimap iterators.

How iteratorName++/iteratorName-- works?

Does each element have 2 pointers for the very less/more than itself? If so, how does it keep such information?

Does it take O(1), amortized or logarithmic time?

And aside question, how begin() method works? Is it considered with each insertion/removal?

associative set iterator stl c++
1 Answers

How does C++ associative containers iterator increment work?

The C++ language doesn't specify how the containers are implemented.

In practice, the sorted associative containers are implemented as red-black trees. I'll show one implementation as an example. Libstdc++ map iterator contains a pointer to a tree node. Here is how increment is implemented (modified by me for readability):

// modified from libstdc++
// license: lgpl
rb_tree_increment(rb_tree_node_base* x)
{
    if (x->right != 0) 
    {
        x = x->right;
        while (x->left != 0)
            x = x->left;
    }
    else 
    {
        rb_tree_node_base* y = x->parent;
        while (x == y->right) 
        {
            x = y;
            y = y->parent;
        }
        if (x->right != y)
            x = y;
    }
    return x;
}

Does it take O(1), amortized or logarithmic time?

All iterator operations are required to be amortized O(1). The worst case non-amortized complexity of the shown implementation is logarithmic.

how begin() method works?

As you've now learned that you can just read the implementation, I'll leave this as an exercise to the reader to find out.

user_20793030
Related