bebosudo / advanced-programming Goto Github PK

Hello @asartori86!
Me and @bebosudo were thinking about a good implementation of iterators for the binary search tree class. We thought about many different possibilities, each with its pros and cons.

In particular we ended up dividing the implementations into two main categories:

• the ones that "duplicate" the structure so that, even if the tree is modified after the instantiation, the output of the iterator stays the same
• the ones that work "online" and, if the structure is altered, they adapt accordingly and give data always consistent with the modified structure

For example, consider the following code:

// insertion of number from 1 to 20 into the tree...

for (IteratorClass it = tree.begin(); it->key() < 10; it++) { cout<<it; }

tree.erase(15);

for (; it != tree.end(); it++) { cout<<it;  }

in the first case would print all the numbers from 1 to 20, since the tree nodes have been copied elsewhere at the iterator initialization;
in the second case it would print numbers from 1 to 20, 15 excluded, when using the second method.

Both of the approaches presents a trade-off of the kind flexibility vs memory-frugality.
Would it be possible to have your opinion about that?
Thank you in advance for your time!