Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

RedBlackTree: Iterators become invalid after removing an element. #223

Open
981377660LMT opened this issue Mar 21, 2023 · 2 comments
Open

Comments

@981377660LMT
Copy link

981377660LMT commented Mar 21, 2023

package main

import (
	"fmt"

	"github.com/emirpasic/gods/trees/redblacktree"
)

func main() {
	tree := redblacktree.NewWithIntComparator()
	tree.Put(1, struct{}{})
	tree.Put(2, struct{}{})
	tree.Put(3, struct{}{})
	it1 := tree.Iterator()
	it2 := tree.Iterator()
	it1.Next()
	it2.Next()
	it2.Next()
	fmt.Println(it1.Key()) // 1 
	tree.Remove(2)
	fmt.Println(it1.Key()) // 1 
	it1.Next()
	fmt.Println(it1.Key()) 
        //  need to be 3 here
        // panic: runtime error: invalid memory address or nil pointer dereference
}

I think that after removing an element, the iterators of the other elements need to be unaffected.

@amoyraku
Copy link

You can not remove elements while you are using a iterator. You will make the iterator become invalid, then any operation on the iterator will cause a problem.

@PapaCharlie
Copy link
Collaborator

FWIW, when you use an iterator over a collection in Java, the returned iterator supports deleting the most recently returned element. Might be an acceptable way to support deletion during iteration?
https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html#remove--

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants