Comments (5)
Short answer: It's not safe.
Long answer: Because it's unsafe, we should find a way to guard against that if that's possible. For instance, Java would throw ConcurrentModificationException in that case. However, the iterator should provide a safe Remove() method. That might be tricky to implement in some structures, especially trees and structures using trees, where balancing takes place after deletion. That balancing logic would "shuffle" the elements around and a possible side effect would be duplicate iteration, i.e. iterating over an element that was already visited. However, for simpler structures, such as lists and stacks, this should be possible. Note that gods' HashMap doesn't even have an iterator, since Go randomizes the iteration.
from gods.
Would it be possible for an iterators Remove()
to do a sort of "lazy delete" on a RBTree for instance? Which let the tree get a bit unbalanced and violate the RB properties, with the assumption that the next real remove/insert would start to repair it. I've know I've heard of some binary trees that only balance on inserts and never on remove, so it might be a good trade off if it doesn't add much/any complexity to the implementation
from gods.
Somehow I feel uneasy with the idea of violating the RB properties. Not that it doesn't make sense, it certainly does make sense when optimizing for a particular problem. However, I can not assume a particular problem and have to try to make this library as "generic" as possible for a wide range of problems.
After giving some thought, I realized that there might be a way of implementing the iterator.Remove() function without breaking the RB properties or the iteration. The idea is for the iterator to flag the current element as deleted. Also the iterator, in case of deletion, should store the deleted key, so that it can descend from the root and find (O(log n)) the next/previous element (bigger/less than that deleted key). That trade off (having to internally store extra information and search complexity after deletion) is probably worth the extra functionality.
I'll give that a try just to check that I haven't missed something and add that functionality then to all iterable structures (if possible).
from gods.
Removing the element that the iterator has currently selected is actually not as tricky as it might seem, provided the iterators visit elements in-order (ascending or descending). While the tree does indeed shuffle elements or subtrees around while deleting, it always keeps the elements strictly ordered. Therefore, an iterator that visits elements in-order is guaranteed not to skip elements or visit elements twice.
(That is also what Java's iterators do; they allow removal of the currently selected element, but throw ConcurrentModificationException if the tree is modified directly between calls of the iterator's methods)
One possibility is to keep a reference to the next element in the iterator's data structure. That way, the iterator can delete the current element, but still continue where it left off, and it also enables the iterator to tell whether the iteration is complete or not by just checking whether 'next' is a null reference.
Initialization is to find the first (least or greatest value) element and store the reference in 'next'.
Iteration is to copy 'next' to 'current', store the next element in 'next' and return 'current'.
Deletion is to drop 'current' from the tree if 'current' is not a null reference and then set 'current' to null; iteration continues in-order as usual.
from gods.
Closing for now until I find more time to implement this
from gods.
Related Issues (20)
- priorityqueue question HOT 1
- What scenarios will this project be imported HOT 4
- Coverity Scan - Explicit null dereferenced HOT 1
- hashbidimaps Values() returns keys HOT 2
- Why not replace "%+v" to json.Marshal in utils.ToString
- Does it make sense to add goroutine / thread safe data structures for all the existing data structures? HOT 1
- arraylist.List should not maintain size HOT 1
- Add a Ordered linked HOT 2
- Hey! I am interested in translating this project into Portuguese, Brazil. Can I contribute? HOT 1
- I would like to know how to delete a node data while treemap loop read. I want to know where is my code wrong? HOT 2
- Add to Go official wiki? HOT 3
- generic upgrade request HOT 3
- RedBlackTree: Iterators become invalid after removing an element. HOT 2
- DS which can give element if present or next greater if not present, elements should be stored in sorted order HOT 2
- LinkedHashMap Sort? HOT 3
- Multiset support HOT 1
- deque support
- hashset should support NewWith Comparator
- Add method of Set lack info about the insert take place or not
- treeset:The names of each element are not equal, why is second_8 disappearing? HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from gods.