about summary refs log tree commit diff
path: root/src/libstd/collections/mod.rs
AgeCommit message (Collapse)AuthorLines
2016-06-17Add short summaries to btree modulesOliver Middleton-2/+4
Also improve hash_map and hash_set module short summaries.
2016-04-22Implement `append` for b-trees.Johannes Oertel-6/+4
The algorithm implemented here is linear in the size of the two b-trees. It firsts creates a `MergeIter` from the two b-trees and then builds a new b-tree by pushing key-value pairs from the `MergeIter` into nodes at the right heights. Three functions for stealing have been added to the implementation of `Handle` as well as a getter for the height of a `NodeRef`. The docs have been updated with performance information about `BTreeMap::append` and the remark about B has been removed now that it is the same for all instances of `BTreeMap`.
2016-03-12std: Clean out deprecated APIsAlex Crichton-10/+0
Removes all unstable and deprecated APIs prior to the 1.8 release. All APIs that are deprecated in the 1.8 release are sticking around for the rest of this cycle. Some notable changes are: * The `dynamic_lib` module was moved into `rustc_back` as the compiler still relies on a few bits and pieces. * The `DebugTuple` formatter now special-cases an empty struct name with only one field to append a trailing comma.
2016-02-15clarify how insert() doesn't update keysJack O'Connor-3/+6
The first time I read the docs for `insert()`, I thought it was saying it didn't update existing *values*, and I was confused. Reword the docs to make it clear that `insert()` does update values.
2016-01-26std: Stabilize custom hasher support in HashMapAlex Crichton-0/+2
This commit implements the stabilization of the custom hasher support intended for 1.7 but left out due to some last-minute questions that needed some decisions. A summary of the actions done in this PR are: Stable * `std::hash::BuildHasher` * `BuildHasher::Hasher` * `BuildHasher::build_hasher` * `std::hash::BuildHasherDefault` * `HashMap::with_hasher` * `HashMap::with_capacity_and_hasher` * `HashSet::with_hasher` * `HashSet::with_capacity_and_hasher` * `std::collections::hash_map::RandomState` * `RandomState::new` Deprecated * `std::collections::hash_state` * `std::collections::hash_state::HashState` - this trait was also moved into `std::hash` with a reexport here to ensure that we can have a blanket impl to prevent immediate breakage on nightly. Note that this is unstable in both location. * `HashMap::with_hash_state` - renamed * `HashMap::with_capacity_and_hash_state` - renamed * `HashSet::with_hash_state` - renamed * `HashSet::with_capacity_and_hash_state` - renamed Closes #27713
2015-11-18Add missing annotations and some testsVadim Petrochenkov-1/+9
2015-10-25Remove key duplication from `BTreeMap` example in `collections`Tobias Bucher-4/+4
2015-10-22Document replacement behavior in some collectionsSteve Klabnik-0/+46
{BTree,Hash}{Map,Set} will not update their key if it already exists, which can matter with more complex keys. This behavior is now documented. Fixes #26888
2015-08-25collections doc: remove mention of BitVec, BitSet, VecMapGeorg Brandl-28/+6
These have been removed and should not be documented here.
2015-08-15std: Add issues to all unstable featuresAlex Crichton-1/+2
2015-08-12Remove all unstable deprecated functionalityAlex Crichton-4/+4
This commit removes all unstable and deprecated functions in the standard library. A release was recently cut (1.3) which makes this a good time for some spring cleaning of the deprecated functions.
2015-06-18Auto merge of #26192 - alexcrichton:features-clean, r=aturonbors-1/+1
This commit shards the all-encompassing `core`, `std_misc`, `collections`, and `alloc` features into finer-grained components that are much more easily opted into and tracked. This reflects the effort to push forward current unstable APIs to either stabilization or removal. Keeping track of unstable features on a much more fine-grained basis will enable the library subteam to quickly analyze a feature and help prioritize internally about what APIs should be stabilized. A few assorted APIs were deprecated along the way, but otherwise this change is just changing the feature name associated with each API. Soon we will have a dashboard for keeping track of all the unstable APIs in the standard library, and I'll also start making issues for each unstable API after performing a first-pass for stabilization.
2015-06-17std: Split the `std_misc` featureAlex Crichton-1/+1
2015-06-17collections: fix a couple of typosIvan Ukhov-3/+3
2015-06-10Removed many pointless calls to *iter() and iter_mut()Joshua Landau-3/+4
2015-05-09Squeeze the last bits of `task`s in documentation in favor of `thread`Barosl Lee-1/+1
An automated script was run against the `.rs` and `.md` files, subsituting every occurrence of `task` with `thread`. In the `.rs` files, only the texts in the comment blocks were affected.
2015-04-07std: Deny most warnings in doctestsAlex Crichton-155/+180
Allow a few specific ones but otherwise this helps ensure that our examples are squeaky clean! Closes #18199
2015-03-27default => or_insert per RFCAlexis Beingessner-2/+2
2015-03-26update everything to use Entry defaultsAlexis-8/+2
2015-03-23Add #![feature] attributes to doctestsBrian Anderson-0/+2
2015-03-02Added note that method names in tables may differ from actual collectionsDavid Mally-1/+2
2015-03-02Fixed references to set & take ; minor wording & syntax fixesDavid Mally-5/+5
2015-02-21Remove last traces of BitV and BitVSet from documentationFlorian Hartwig-4/+4
2015-02-18Implement RFC 580Aaron Turon-21/+21
This commit implements RFC 580 by renaming: * DList -> LinkedList * Bitv -> BitVec * BitvSet -> BitSet * RingBuf -> VecDeque More details are in [the RFC](https://github.com/rust-lang/rfcs/pull/580) [breaking-change]
2015-02-13more int and cloned cleanup in collectionsAlexis-3/+3
2015-02-07fix outdated docsAlexis-1/+1
Conflicts: src/libstd/collections/mod.rs
2015-02-07fix outdated docsAlexis-9/+9
Conflicts: src/libstd/collections/mod.rs
2015-02-06More libcollections fixesManish Goregaokar-3/+3
2015-02-04Fix for misspelled comments.Joseph Crail-1/+1
The spelling corrections were made in both documentation comments and regular comments.
2015-01-25Merge remote-tracking branch 'rust-lang/master'Brian Anderson-2/+52
Conflicts: mk/tests.mk src/liballoc/arc.rs src/liballoc/boxed.rs src/liballoc/rc.rs src/libcollections/bit.rs src/libcollections/btree/map.rs src/libcollections/btree/set.rs src/libcollections/dlist.rs src/libcollections/ring_buf.rs src/libcollections/slice.rs src/libcollections/str.rs src/libcollections/string.rs src/libcollections/vec.rs src/libcollections/vec_map.rs src/libcore/any.rs src/libcore/array.rs src/libcore/borrow.rs src/libcore/error.rs src/libcore/fmt/mod.rs src/libcore/iter.rs src/libcore/marker.rs src/libcore/ops.rs src/libcore/result.rs src/libcore/slice.rs src/libcore/str/mod.rs src/libregex/lib.rs src/libregex/re.rs src/librustc/lint/builtin.rs src/libstd/collections/hash/map.rs src/libstd/collections/hash/set.rs src/libstd/sync/mpsc/mod.rs src/libstd/sync/mutex.rs src/libstd/sync/poison.rs src/libstd/sync/rwlock.rs src/libsyntax/feature_gate.rs src/libsyntax/test.rs
2015-01-23grandfathered -> rust1Brian Anderson-3/+3
2015-01-23Set unstable feature names appropriatelyBrian Anderson-1/+1
* `core` - for the core crate * `hash` - hashing * `io` - io * `path` - path * `alloc` - alloc crate * `rand` - rand crate * `collections` - collections crate * `std_misc` - other parts of std * `test` - test crate * `rustc_private` - everything else
2015-01-22Rollup merge of #21217 - Gankro:docadoca, r=steveklabnikSteve Klabnik-2/+52
Not sure on what *exactly* should be said here, but I think this is the most important bit. This PR also establishes conventions for describing performance minimally. I suggest to describe preformance for individual methods we use a `# Performance` heading. Not sure if we should have ``` # Performance: O(1) details details ``` or ``` # Performance: O(1) details details ``` Since I think most methods don't need discussion, the former seems more resonable. But it's kind of weird to have info "in" the heading. r? @steveklabnik
2015-01-21Remove 'since' from unstable attributesBrian Anderson-1/+1
2015-01-21Add 'feature' and 'since' to stability attributesBrian Anderson-4/+4
2015-01-19Implement range and range_mut for BTreePiotr Czarnecki-0/+1
Simplify BTree's iterators, too.
2015-01-15add a section on performance to collection docsAlexis-2/+52
2015-01-07std: Stabilize the std::hash moduleAlex Crichton-0/+7
This commit aims to prepare the `std::hash` module for alpha by formalizing its current interface whileholding off on adding `#[stable]` to the new APIs. The current usage with the `HashMap` and `HashSet` types is also reconciled by separating out composable parts of the design. The primary goal of this slight redesign is to separate the concepts of a hasher's state from a hashing algorithm itself. The primary change of this commit is to separate the `Hasher` trait into a `Hasher` and a `HashState` trait. Conceptually the old `Hasher` trait was actually just a factory for various states, but hashing had very little control over how these states were used. Additionally the old `Hasher` trait was actually fairly unrelated to hashing. This commit redesigns the existing `Hasher` trait to match what the notion of a `Hasher` normally implies with the following definition: trait Hasher { type Output; fn reset(&mut self); fn finish(&self) -> Output; } This `Hasher` trait emphasizes that hashing algorithms may produce outputs other than a `u64`, so the output type is made generic. Other than that, however, very little is assumed about a particular hasher. It is left up to implementors to provide specific methods or trait implementations to feed data into a hasher. The corresponding `Hash` trait becomes: trait Hash<H: Hasher> { fn hash(&self, &mut H); } The old default of `SipState` was removed from this trait as it's not something that we're willing to stabilize until the end of time, but the type parameter is always required to implement `Hasher`. Note that the type parameter `H` remains on the trait to enable multidispatch for specialization of hashing for particular hashers. Note that `Writer` is not mentioned in either of `Hash` or `Hasher`, it is simply used as part `derive` and the implementations for all primitive types. With these definitions, the old `Hasher` trait is realized as a new `HashState` trait in the `collections::hash_state` module as an unstable addition for now. The current definition looks like: trait HashState { type Hasher: Hasher; fn hasher(&self) -> Hasher; } The purpose of this trait is to emphasize that the one piece of functionality for implementors is that new instances of `Hasher` can be created. This conceptually represents the two keys from which more instances of a `SipHasher` can be created, and a `HashState` is what's stored in a `HashMap`, not a `Hasher`. Implementors of custom hash algorithms should implement the `Hasher` trait, and only hash algorithms intended for use in hash maps need to implement or worry about the `HashState` trait. The entire module and `HashState` infrastructure remains `#[unstable]` due to it being recently redesigned, but some other stability decision made for the `std::hash` module are: * The `Writer` trait remains `#[experimental]` as it's intended to be replaced with an `io::Writer` (more details soon). * The top-level `hash` function is `#[unstable]` as it is intended to be generic over the hashing algorithm instead of hardwired to `SipHasher` * The inner `sip` module is now private as its one export, `SipHasher` is reexported in the `hash` module. And finally, a few changes were made to the default parameters on `HashMap`. * The `RandomSipHasher` default type parameter was renamed to `RandomState`. This renaming emphasizes that it is not a hasher, but rather just state to generate hashers. It also moves away from the name "sip" as it may not always be implemented as `SipHasher`. This type lives in the `std::collections::hash_map` module as `#[unstable]` * The associated `Hasher` type of `RandomState` is creatively called... `Hasher`! This concrete structure lives next to `RandomState` as an implemenation of the "default hashing algorithm" used for a `HashMap`. Under the hood this is currently implemented as `SipHasher`, but it draws an explicit interface for now and allows us to modify the implementation over time if necessary. There are many breaking changes outlined above, and as a result this commit is a: [breaking-change]
2015-01-06[breaking change] Revert Entry behaviour to take keys by value.Dylan Ede-2/+2
2015-01-05Stabilize collection modulesAaron Turon-1/+3
The earlier collections stabilization did not cover the modules themselves. This commit marks as stable those modules whose types have been stabilized.
2015-01-04[breaking change] Update entry API as part of RFC 509.Ben Foppa-5/+5
2015-01-03Remove deprecated functionalityAlex Crichton-8/+0
This removes a large array of deprecated functionality, regardless of how recently it was deprecated. The purpose of this commit is to clean out the standard libraries and compiler for the upcoming alpha release. Some notable compiler changes were to enable warnings for all now-deprecated command line arguments (previously the deprecated versions were silently accepted) as well as removing deriving(Zero) entirely (the trait was removed). The distribution no longer contains the libtime or libregex_macros crates. Both of these have been deprecated for some time and are available externally.
2014-12-18remove TreeMap, TreeSet, TrieMap, TrieSet, LruCache. deprecate EnumSet's std ↵Alexis Beingessner-26/+13
re-export
2014-11-06Implement low-hanging fruit of collection conventionsAlexis Beingessner-1/+1
* Renames/deprecates the simplest and most obvious methods * Adds FIXME(conventions)s for outstanding work * Marks "handled" methods as unstable NOTE: the semantics of reserve and reserve_exact have changed! Other methods have had their semantics changed as well, but in a way that should obviously not typecheck if used incorrectly. Lots of work and breakage to come, but this handles most of the core APIs and most eggregious breakage. Future changes should *mostly* focus on niche collections, APIs, or simply back-compat additions. [breaking-change]
2014-11-02refactor libcollections as part of collection reformAlexis Beingessner-14/+27
* Moves multi-collection files into their own directory, and splits them into seperate files * Changes exports so that each collection has its own module * Adds underscores to public modules and filenames to match standard naming conventions (that is, treemap::{TreeMap, TreeSet} => tree_map::TreeMap, tree_set::TreeSet) * Renames PriorityQueue to BinaryHeap * Renames SmallIntMap to VecMap * Miscellanious fallout fixes [breaking-change]
2014-11-01collections: Remove all collections traitsAlex Crichton-2/+0
As part of the collections reform RFC, this commit removes all collections traits in favor of inherent methods on collections themselves. All methods should continue to be available on all collections. This is a breaking change with all of the collections traits being removed and no longer being in the prelude. In order to update old code you should move the trait implementations to inherent implementations directly on the type itself. Note that some traits had default methods which will also need to be implemented to maintain backwards compatibility. [breaking-change] cc #18424
2014-10-06library-level docs for collectionsAlexis Beingessner-3/+317
2014-09-27complete btree rewriteAlexis Beingessner-1/+1
Replaces BTree with BTreeMap and BTreeSet, which are completely new implementations. BTreeMap's internal Node representation is particularly inefficient at the moment to make this first implementation easy to reason about and fairly safe. Both collections are also currently missing some of the tooling specific to sorted collections, which is planned as future work pending reform of these APIs. General implementation issues are discussed with TODOs internally Perf results on x86_64 Linux: test treemap::bench::find_rand_100 ... bench: 76 ns/iter (+/- 4) test treemap::bench::find_rand_10_000 ... bench: 163 ns/iter (+/- 6) test treemap::bench::find_seq_100 ... bench: 77 ns/iter (+/- 3) test treemap::bench::find_seq_10_000 ... bench: 115 ns/iter (+/- 1) test treemap::bench::insert_rand_100 ... bench: 111 ns/iter (+/- 1) test treemap::bench::insert_rand_10_000 ... bench: 996 ns/iter (+/- 18) test treemap::bench::insert_seq_100 ... bench: 486 ns/iter (+/- 20) test treemap::bench::insert_seq_10_000 ... bench: 800 ns/iter (+/- 15) test btree::map::bench::find_rand_100 ... bench: 74 ns/iter (+/- 4) test btree::map::bench::find_rand_10_000 ... bench: 153 ns/iter (+/- 5) test btree::map::bench::find_seq_100 ... bench: 82 ns/iter (+/- 1) test btree::map::bench::find_seq_10_000 ... bench: 108 ns/iter (+/- 0) test btree::map::bench::insert_rand_100 ... bench: 220 ns/iter (+/- 1) test btree::map::bench::insert_rand_10_000 ... bench: 620 ns/iter (+/- 16) test btree::map::bench::insert_seq_100 ... bench: 411 ns/iter (+/- 12) test btree::map::bench::insert_seq_10_000 ... bench: 534 ns/iter (+/- 14) BTreeMap still has a lot of room for optimization, but it's already beating out TreeMap on most access patterns. [breaking-change]
2014-07-23collections: Move push/pop to MutableSeqBrian Anderson-1/+1
Implement for Vec, DList, RingBuf. Add MutableSeq to the prelude. Since the collections traits are in the prelude most consumers of these methods will continue to work without change. [breaking-change]
2014-06-30libstd: set baseline stability levels.Aaron Turon-0/+2
Earlier commits have established a baseline of `experimental` stability for all crates under the facade (so their contents are considered experimental within libstd). Since `experimental` is `allow` by default, we should use the same baseline stability for libstd itself. This commit adds `experimental` tags to all of the modules defined in `std`, and `unstable` to `std` itself.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 21:14:31 +0000