Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Bug with iterators

Revision en1, by noobinho, 2019-09-04 17:34:06

I want a list of balanced binary search trees so that I can answer queries for insert, delete and median in each tree. Based on this post I coded the following:

struct Tree{
	multiset<int> ms;
	multiset<int>::iterator med_it;
	int med_idx;

int Ceil(int a, int b){
	return (a+1)/b;

void initializeTree(Tree (&tree), int el){
	(tree.med_it) = (tree.ms).begin();
	(tree.med_idx) = 1;

void TreeInsert(Tree (&tree), int el){

	if(el < *(tree.med_it)) (tree.med_idx)++;

	int idx = Ceil((tree.ms).size(),2);

	if(tree.med_idx < idx) (tree.med_it)++;
	else if(tree.med_idx > idx) (tree.med_it)--;

	tree.med_idx = idx;

void TreeDelete(Tree (&tree), int el){
	multiset<int>::iterator aux;

	int idx = Ceil((int)(tree.ms).size() - 1,2);

	if(el == *(tree.med_it)){
		aux = (tree.med_it);

		if((tree.med_idx) == idx) aux++;
		else aux--;

		(tree.med_it) = aux;
		aux = (tree.ms).find(el);

		if(el < *(tree.med_it)) (tree.med_idx)--;

		if((tree.med_idx) < idx) (tree.med_it)++;
		else if((tree.med_idx) > idx) (tree.med_it)--;

	(tree.med_idx) = idx; 

int TreeMerge(Tree (&tree1), Tree (&tree2)){
	multiset<int>::iterator it;

	if((tree1.ms).size() >= (tree2.ms).size()){
		for(it = (tree2.ms).begin(); it != (tree2.ms).end(); it++) TreeInsert(tree1, *it);
		return 1;
		for(it = (tree1.ms).begin(); it != (tree1.ms).end(); it++) TreeInsert(tree2, *it);
		return 2;

I tested all the functions and they seem to work well. But then I created a list L to be my list and inserted some trees on it to test the functions on the members of the list. The following code shows that:

Tree tree1, tree2;


list<Tree> L;


Then I acessed the members of the list with list::iterator as shown in the code below:

list<Tree>::iterator L_cur = L.begin(), L_next = L.begin();

So I applied the functions to *L_cur and *L_next and the med_it pointer got some bug. For example, when running the code below:

int merge = TreeMerge(*L_cur,*L_next);

When I access the content of the L_cur and L_next pointers all seems to work as expected except for the med_it pointer of the tree in L_cur, which continues pointing to 9 instead of 4.

When I run the same function with two Tree objects it seems to work well, as shown in the code below:

Tree tree1, tree2;


int merge = TreeMerge(tree1,tree2);

Why it occurs?


  Rev. Lang. By When Δ Comment
en1 English noobinho 2019-09-04 17:34:06 2907 Initial revision (published)