STD set in memory

Question

From what I've read,the set is implemented using trees(I expect Binary Search Trees).As far as I know,tree's elements aren't stored in a contignuos way,since they are created using new. This is how you can iterate over one set.

for (auto it = myset.begin() ; it != myset.end() ; it++)
//or
for (auto it : myset)

In the first method , how will the "it++" work if the elements in a tree are not stored in a contignuos way?

Show us the `for` loop, so that we see what you're doing and can be explained. — PaulMcKenzie, Apr 14 '21 at 12:43
The "how to get to next element" logic is hidden in the `set::set::iterator` class. It may be implemented differently in different standard library implementations. — Yksisarvinen, Apr 14 '21 at 12:47
What I mean is,if the set is a tree,when doing for(auto it=set.begin();it!=set.end();it++) ,the ++ shouldn't work because a tree's elements aren't stored contignuosly. — cosmin-andrei paraschiv, Apr 14 '21 at 12:47
@cosmin-andreiparaschiv there is more than one way to use a `for` loop to iterate over a `std::set` - please post some code so we can answer the right question. — Richard Critten, Apr 14 '21 at 12:49
@cosmin-andreiparaschiv *the ++ shouldn't work* -- The `++` is overloaded to work with the set's iterator. — PaulMcKenzie, Apr 14 '21 at 12:52
`iterator` is not necessary a pointer, and for `std::set`, it isn't. `operator ++` is overloaded to work as intended. — Jarod42, Apr 14 '21 at 12:52
So the iterator is not necessarly a pointer?Didn't know that — cosmin-andrei paraschiv, Apr 14 '21 at 12:55
@Jarod42 Since the begin() function returns an adress in the memory , I thought my it variable is definetly a pointer — cosmin-andrei paraschiv, Apr 14 '21 at 12:56
Another one: [How are iterators and pointers related?](https://stackoverflow.com/q/2728190/580083). — Daniel Langr, Apr 14 '21 at 12:56
`++it` is roughly equivalent to something like simplified `it.node = it.node->next;`. — Jarod42, Apr 14 '21 at 12:59
*Since the begin() function returns an address in the memory* -- The `begin()` returns whatever it needs to return. It could be a pointer, but it could be an entire object that has `++` overloaded. — PaulMcKenzie, Apr 14 '21 at 13:02
second loop is understood incorrectly. In `for(auto x : container )` an `x` is a copy of element from `container`. — Swift - Friday Pie, Apr 14 '21 at 13:46

Fairyteller · Accepted Answer · 2021-04-14T13:13:37.880

For loop has no direct relation to containers, it just allows you to do some block of code several times while condition is met.

Common application for For loop is to adjust some number sequentially and use it to access some element in contiguous array by that number as index (offsetting from the beginning).

As you've mentioned it does not work with data not aligned contiguously, but "For" loop is not limited to just updating indices. Iterator is a pattern of object that encapsulates logic of container traversal. Container provides methods for iterator obtaining and then iterator provides methods to move through container content in some direction.

With that you can use "for" loop (which is not bound to just updating indices!) with iterators to iterate through set elements

for (auto iterator = my_set.begin(); iterator != my_set.end(); iterator++)
// do something with element through iterator

C++11 "range-based for" feature just allows you to have a compact form for the same logic:

for (auto iterator : my_set)
// do something with element through iterator

Internally set forward iterator just moves through tree nodes in specific order, handling all the logic of next node selection, moving from left to right in binary search tree.

You can imagine that set::begin() returns an iterator that internally stores an address of the first node in set (leftmost leaf for forward iterator). Iterator::operator++ is implemented in a way to update iterator to reference next node in sorted order.

Informal logic of next item selection from iterator point of view: If my node has left child - it is less than my element so I do not need to visit it. Right node is bigger than my element so it is the next element. If my node has no right child - i need to move up to find next element. I need to know whether I go up from left direction or right. If I am moving up from the left subtree - then value of parent node is next ordered value. If I am moving from the right subtree - I visited this node already and I need to recursively continue my ascension while I will find that I approached node from left subtree. If no such node found - that means that I've just pointed to last element so now I should invalidate internal reference to highlight that iterator reached the end of container.

Ohh.So the "iterator++" traverses the tree in-order to get it sorted? — cosmin-andrei paraschiv, Apr 14 '21 at 12:58
No, set stores the whole tree already in sorted manner, using binary tree search partitioning, so that for every node - first (left) child is lesser (in terms of sorting) and second (right) child is bigger (again in terms of sorting, it could be applicable to anything that has > < operators). Iterator++ just selects next node knowing this rules of its structure — Fairyteller, Apr 14 '21 at 13:03
Yes , in a binary search tree , you need to traverse it in-order to print the elements in a sorted way — cosmin-andrei paraschiv, Apr 14 '21 at 13:18
Yes, so iterator traverses set's internal BST tree in sorted order, just print elements through iterator while adjusting it with ++ in the loop. But just in order to name things with correct names: please note that iterator does not sort the set, set is always sorted by design, because all methods that could change it are implemented in a way that maintains internal sorted order. Iterator just handles traversal through this set in sorted manner. — Fairyteller, Apr 14 '21 at 13:21

STD set in memory

1 Answers1