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.

Sign up for GitHub

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

Jump to bottom

Keep track of number of elements for efficient len() #32

Closed
jonhoo opened this issue Apr 12, 2017 · 1 comment
Closed

Keep track of number of elements for efficient len() #32

jonhoo opened this issue Apr 12, 2017 · 1 comment

Comments

@jonhoo
Copy link
Contributor

jonhoo commented Apr 12, 2017

Currently, VecMap::len() takes O(highest index) time to compute every time (same goes for VecMap::is_empty(). It'd be nice if VecMap instead kept track of the number of Some it has, and just use this value in len() and is_empty(). It would add a usize to the VecMap struct, but this seems negligible compared to the performance gains of doing so. I'll submit a PR shortly which you can merge if you feel like this would be a useful addition :)
@jonhoo
Copy link
Contributor Author

jonhoo commented Apr 12, 2017

Looking at this, it seems like this could be used to speed up other operations too. For example, VecMap::iter() can now cheaply return an ExactSizeIterator.

jonhoo added a commit to jonhoo/vec-map that referenced this issue Apr 12, 2017
@jonhoo
Keep track of number of set elements in map
c4bd78a 
This allows much more efficient versions of len() and is_empty(), and
also enables ExactSizeIterator to be implemented to VecMap's iterators.

Fixes contain-rs#32
jonhoo added a commit to jonhoo/vec-map that referenced this issue Apr 12, 2017
@jonhoo
Keep track of number of set elements in map
2896861 
This allows much more efficient versions of len() and is_empty(), and
also enables ExactSizeIterator to be implemented for VecMap's iterators.

Fixes contain-rs#32
jonhoo added a commit to jonhoo/vec-map that referenced this issue Apr 13, 2017
@jonhoo
Keep track of number of set elements in map
55f10e9 
This allows much more efficient versions of len() and is_empty(), and
also enables ExactSizeIterator to be implemented for VecMap's iterators.

Fixes contain-rs#32
@jonhoo jonhoo mentioned this issue Apr 13, 2017
Merged
@Gankra Gankra closed this as completed in #33 May 7, 2017
camsteffen pushed a commit to camsteffen/vec-map that referenced this issue May 14, 2017
@jonhoo @camsteffen
Keep track of number of set elements in map
98e7ae2 
This allows much more efficient versions of len() and is_empty(), and
also enables ExactSizeIterator to be implemented for VecMap's iterators.

Fixes contain-rs#32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@jonhoo