noobinho's blog

Bug with iterators
By noobinho, history, 5 years ago, In English

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.ms).insert(el);
	(tree.med_it) = (tree.ms).begin();
	(tree.med_idx) = 1;
}

void TreeInsert(Tree (&tree), int el){
	(tree.ms).insert(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.ms).erase((tree.med_it));
		(tree.med_it) = aux;
	}
	else{
		aux = (tree.ms).find(el);
		(tree.ms).erase(aux);

		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;
	}
	else{
		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;

initializeTree(tree1,9);
initializeTree(tree2,4);

list<Tree> L;

L.push_back(tree1);
L.push_back(tree2);

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();
L_next++;

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;

initializeTree(tree1,9);
initializeTree(tree2,4);

int merge = TreeMerge(tree1,tree2);

Why it occurs?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm not pretty sure (not compiler) but your $$$Tree$$$ is just a struct without explicitly defined copy/move constructor. That means your iterator will be copied too during push_back, which uses copy constructor.

Order of actions:

  1. Create tree1 with ms1 and iterator
  2. Create tree2 with ms2 and iterator
  3. list.push_back(tree1) -> tree1_copy.med_it points at element in ms1, tree1_copy.ms1_copy is empty
  4. list.push_back(tree2) -> tree2_copy.med_it points at element in ms2, tree2_copy.ms2_copy is empty
  5. TreeMerge(tree1_copy, tree2_copy) — correct result since no usage of med_it.
  6. TreeDelete would affect ms1, not ms1_copy.
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks for answer. I run it here and tree1_copy.ms1_copy and tree2_copy.ms2_copy don't seem to be empty. As you can see, the problem is only with the med_it pointer. How could I correct it to run as expected?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, my mistake: copy of nonempty multiset is nonempty too.
      There are a lot of options:

      • Simplest as I see is not create any copy of Tree: create empty trees within list and call initializeTree for list elements:
      list<Tree> L;
L.push_back(Tree());
L.push_back(Tree());
initializeTree(*L.begin(), 9);
initializeTree(*L.rbegin(), 4);
int merge = TreeMerge(*L.begin(), *L.rbegin());

      And you should mark copy/move constructors of Tree as delete. Then compiler permit any move/copy.

      • If you know that tree1 and tree2 would never used further you can define move constructor Tree(Tree&& other) : ms(move(other.ms)), med_it(move(other.med_it)), med_idx(move(other.med_idx)) {} and do:
      Tree tree1, tree2;
initializeTree(tree1, 9);
initializeTree(tree2, 4);
list<Tree> L;
L.emplace_back(move(tree1));
L.emplace_back(move(tree2));
int merge = TreeMerge(*L.begin(), *L.rbegin());
      • Third option is define correct copy constructor. Since you already have med_idx, then you can initialize med_it as ms.begin() + med_idx. Tree(const Tree& other) : ms(other.ms) { med_idx = other.med_idx; med_it = next(ms.begin(), med_idx); } then no edit of your code is needed.
      → Reply