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

Adding SmallSet #220

Open
dhardy opened this issue May 4, 2020 · 4 comments
Open

Adding SmallSet #220

dhardy opened this issue May 4, 2020 · 4 comments

Comments

@dhardy
Copy link

dhardy commented May 4, 2020

Can I suggest adding a SmallSet implemented over SmallVec?

This already exists as an independent crate, but that crate is rather outdated. Since only 200-300 lines of code are required (incl. tests) and it is desirable to keep the version in sync with this crate, it seems sensible to integrate the functionality here?

If you like, I can make a PR, based either off rust-smallset or this ArraySet impl (my code, a little more general API, specialised for the case without an optional backing Vec since this can reduce type size).

(Actually, potentially both ArraySet and SmallSet could be added.)

@mbrubeck
Copy link
Collaborator

mbrubeck commented May 5, 2020

I'm considering this. If the size of the code is a small as your estimate, then seems worthwhile. But I worry that this would eventually grow to include all the methods provided by types like std::collections::HashSet, and then it would add a lot more code to this crate.

For example, the smallset crate currently lacks get, take, replace, drain, retain, intersection, union, difference, symmetric_difference, IntoIterator, FromIterator, Debug, Display, PartialEq, Extend, and more. In addition to the code size, there's also the maintenance work of reviewing patches and feature requests to add all the APIs that people want.

Also, I think that keeping a separate crate in sync with this one should be much easier these days, because we plan to make breaking changes very rarely compared to the pre-1.0 releases.

@dhardy
Copy link
Author

dhardy commented May 6, 2020

All very good points. I'll let you decide how to proceed.

On my part, I would be happy to put in some effort, but probably not maintain such a crate myself.

hbina pushed a commit to hbina/smolset that referenced this issue Aug 18, 2020
Partially implemented some of the easier functions from here
servo/rust-smallvec#220 (comment)
@hbina
Copy link

hbina commented Aug 19, 2020

@dhardy as part of the learning process, I have implemented what @mbrubeck suggested

For example, the smallset crate currently lacks get, take, replace, drain, retain, intersection, union, difference, symmetric_difference, IntoIterator, FromIterator, Debug, Display, PartialEq, Extend, and more. In addition to the code size, there's also the maintenance work of reviewing patches and feature requests to add all the APIs that people want.

here: cfallin/rust-smallset#1. What do you think? I think some of the code can be better, for instance, I think I am allocating quite a lot when creating intermediate iterators (Drain, SymmetricDifference, ...)

hbina pushed a commit to hbina/smolset that referenced this issue Aug 19, 2020
Partially implemented some of the easier functions from here
servo/rust-smallvec#220 (comment)

Implemented `PartialEq` for SmallSet

Added tests for `replace`.

nitpick from Intellij Rust

SmallSet is now a wrapper over enum of SmallVec and HashSet

Insertion now moves to a heap allocated HashSet when capacity.

Fixed compilation error from previous commit

Might want to merge this two later.

Cleared now changes to stack.

Implemented drain

Moved tests and updated them.
hbina pushed a commit to hbina/smolset that referenced this issue Aug 19, 2020
Implemented some helper functions

Partially implemented some of the easier functions from here
servo/rust-smallvec#220 (comment)

Implemented `PartialEq` for SmallSet

Added tests for `replace`.

nitpick from Intellij Rust

SmallSet is now a wrapper over enum of SmallVec and HashSet

Insertion now moves to a heap allocated HashSet when capacity.

Fixed compilation error from previous commit

Might want to merge this two later.

Cleared now changes to stack.

Implemented drain

Moved tests and updated them.

Updated tests.
hbina pushed a commit to hbina/smolset that referenced this issue Aug 19, 2020
Implemented some helper functions

Partially implemented some of the easier functions from here
servo/rust-smallvec#220 (comment)

Implemented `PartialEq` for SmallSet

Added tests for `replace`.

nitpick from Intellij Rust

SmallSet is now a wrapper over enum of SmallVec and HashSet

Insertion now moves to a heap allocated HashSet when capacity.

Fixed compilation error from previous commit

Might want to merge this two later.

Cleared now changes to stack.

Implemented drain

Moved tests and updated them.

Updated tests.

Fixed set equality.
@mbrubeck
Copy link
Collaborator

mbrubeck commented Nov 1, 2020

The vec-collections crate also offers Set and Map types based on ordered SmallVecs.

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