vendor/indexmap/README.rst

   1 indexmap
   2 ========
   3
   4 |build_status|_ |crates|_ |docs|_ |rustc|_
   5
   6 .. |crates| image:: https://img.shields.io/crates/v/indexmap.svg
   7 .. _crates: https://crates.io/crates/indexmap
   8
   9 .. |build_status| image:: https://travis-ci.org/bluss/indexmap.svg
  10 .. _build_status: https://travis-ci.org/bluss/indexmap
  11
  12 .. |docs| image:: https://docs.rs/indexmap/badge.svg
  13 .. _docs: https://docs.rs/indexmap
  14
  15 .. |rustc| image:: https://img.shields.io/badge/rust-1.32%2B-orange.svg
  16 .. _rustc: https://img.shields.io/badge/rust-1.32%2B-orange.svg
  17
  18 A pure-Rust hash table which preserves (in a limited sense) insertion order.
  19
  20 This crate implements compact map and set data-structures,
  21 where the iteration order of the keys is independent from their hash or
  22 value. It preserves insertion order (except after removals), and it
  23 allows lookup of entries by either hash table key or numerical index.
  24
  25 Note: this crate was originally released under the name ``ordermap``,
  26 but it was renamed to ``indexmap`` to better reflect its features.
  27
  28 Background
  29 ==========
  30
  31 This was inspired by Python 3.6's new dict implementation (which remembers
  32 the insertion order and is fast to iterate, and is compact in memory).
  33
  34 Some of those features were translated to Rust, and some were not. The result
  35 was indexmap, a hash table that has following properties:
  36
  37 - Order is **independent of hash function** and hash values of keys.
  38 - Fast to iterate.
  39 - Indexed in compact space.
  40 - Preserves insertion order **as long** as you don't call ``.remove()``.
  41 - Uses hashbrown for the inner table, just like Rust's libstd ``HashMap`` does.
  42
  43 Performance
  44 -----------
  45
  46 ``IndexMap`` derives a couple of performance facts directly from how it is constructed,
  47 which is roughly:
  48
  49   A raw hash table of key-value indices, and a vector of key-value pairs.
  50
  51 - Iteration is very fast since it is on the dense key-values.
  52 - Removal is fast since it moves memory areas only in the table,
  53   and uses a single swap in the vector.
  54 - Lookup is fast-ish because the initial 7-bit hash lookup uses SIMD, and indices are
  55   densely stored. Lookup also is slow-ish since the actual key-value pairs are stored
  56   separately. (Visible when cpu caches size is limiting.)
  57
  58 - In practice, ``IndexMap`` has been tested out as the hashmap in rustc in PR45282_ and
  59   the performance was roughly on par across the whole workload.
  60 - If you want the properties of ``IndexMap``, or its strongest performance points
  61   fits your workload, it might be the best hash table implementation.
  62
  63 .. _PR45282: https://github.com/rust-lang/rust/pull/45282
  64
  65
  66 Recent Changes
  67 ==============
  68
  69 - 1.5.1
  70
  71   - Values can now be indexed by their ``usize`` position by @cuviper in PR 132_.
  72
  73   - Some of the generic bounds have been relaxed to match ``std`` by @cuviper in PR 141_.
  74
  75   - ``drain`` now accepts any ``R: RangeBounds<usize>`` by @cuviper in PR 142_.
  76
  77 .. _132: https://github.com/bluss/indexmap/pull/132
  78 .. _141: https://github.com/bluss/indexmap/pull/141
  79 .. _142: https://github.com/bluss/indexmap/pull/142
  80
  81 - 1.5.0
  82
  83   - **MSRV**: Rust 1.32 or later is now required.
  84
  85   - The inner hash table is now based on ``hashbrown`` by @cuviper in PR 131_.
  86     This also completes the method ``reserve`` and adds ``shrink_to_fit``.
  87
  88   - Add new methods ``get_key_value``, ``remove_entry``, ``swap_remove_entry``,
  89     and ``shift_remove_entry``, by @cuviper in PR 136_
  90
  91   - ``Clone::clone_from`` reuses allocations by @cuviper in PR 125_
  92
  93   - Add new method ``reverse`` by @linclelinkpart5 in PR 128_
  94
  95 .. _125: https://github.com/bluss/indexmap/pull/125
  96 .. _128: https://github.com/bluss/indexmap/pull/128
  97 .. _131: https://github.com/bluss/indexmap/pull/131
  98 .. _136: https://github.com/bluss/indexmap/pull/136
  99
 100 - 1.4.0
 101
 102   - Add new method ``get_index_of`` by @Thermatrix in PR 115_ and 120_
 103
 104   - Fix build script rebuild-if-changed configuration to use "build.rs";
 105     fixes issue 123_. Fix by @cuviper.
 106
 107   - Dev-dependencies (rand and quickcheck) have been updated. The crate's tests
 108     now run using Rust 1.32 or later (MSRV for building the crate has not changed).
 109     by @kjeremy and @bluss
 110
 111 .. _123: https://github.com/bluss/indexmap/issues/123
 112 .. _115: https://github.com/bluss/indexmap/pull/115
 113 .. _120: https://github.com/bluss/indexmap/pull/120
 114
 115 - 1.3.2
 116
 117   - Maintenance update to regenerate the published `Cargo.toml`.
 118
 119 - 1.3.1
 120
 121   - Maintenance update for formatting and ``autocfg`` 1.0.
 122
 123 - 1.3.0
 124
 125   - The deprecation messages in the previous version have been removed.
 126     (The methods have not otherwise changed.) Docs for removal methods have been
 127     improved.
 128   - From Rust 1.36, this crate supports being built **without std**, requiring
 129     ``alloc`` instead. This is enabled automatically when it is detected that
 130     ``std`` is not available. There is no crate feature to enable/disable to
 131     trigger this. The new build-dep ``autocfg`` enables this.
 132
 133 - 1.2.0
 134
 135   - Plain ``.remove()`` now has a deprecation message, it informs the user
 136     about picking one of the removal functions ``swap_remove`` and ``shift_remove``
 137     which have different performance and order semantics.
 138     Plain ``.remove()`` will not be removed, the warning message and method
 139     will remain until further.
 140
 141   - Add new method ``shift_remove`` for order preserving removal on the map,
 142     and ``shift_take`` for the corresponding operation on the set.
 143
 144   - Add methods ``swap_remove``, ``swap_remove_entry`` to ``Entry``.
 145
 146   - Fix indexset/indexmap to support full paths, like ``indexmap::indexmap!()``
 147
 148   - Internal improvements: fix warnings, deprecations and style lints
 149
 150 - 1.1.0
 151
 152   - Added optional feature `"rayon"` that adds parallel iterator support
 153     to `IndexMap` and `IndexSet` using Rayon. This includes all the regular
 154     iterators in parallel versions, and parallel sort.
 155
 156   - Implemented ``Clone`` for ``map::{Iter, Keys, Values}`` and
 157     ``set::{Difference, Intersection, Iter, SymmetricDifference, Union}``
 158
 159   - Implemented ``Debug`` for ``map::{Entry, IntoIter, Iter, Keys, Values}`` and
 160     ``set::{Difference, Intersection, IntoIter, Iter, SymmetricDifference, Union}``
 161
 162   - Serde trait ``IntoDeserializer`` are implemented for ``IndexMap`` and ``IndexSet``.
 163
 164   - Minimum Rust version requirement increased to Rust 1.30 for development builds.
 165
 166 - 1.0.2
 167
 168   - The new methods ``IndexMap::insert_full`` and ``IndexSet::insert_full`` are
 169     both like ``insert`` with the index included in the return value.
 170
 171   - The new method ``Entry::and_modify`` can be used to modify occupied
 172     entries, matching the new methods of ``std`` maps in Rust 1.26.
 173
 174   - The new method ``Entry::or_default`` inserts a default value in unoccupied
 175     entries, matching the new methods of ``std`` maps in Rust 1.28.
 176
 177 - 1.0.1
 178
 179   - Document Rust version policy for the crate (see rustdoc)
 180
 181 - 1.0.0
 182
 183   - This is the 1.0 release for ``indexmap``! (the crate and datastructure
 184     formerly known as “ordermap”)
 185   - ``OccupiedEntry::insert`` changed its signature, to use ``&mut self`` for
 186     the method receiver, matching the equivalent method for a standard
 187     ``HashMap``.  Thanks to @dtolnay for finding this bug.
 188   - The deprecated old names from ordermap were removed: ``OrderMap``,
 189     ``OrderSet``, ``ordermap!{}``, ``orderset!{}``. Use the new ``IndexMap``
 190     etc names instead.
 191
 192 - 0.4.1
 193
 194   - Renamed crate to ``indexmap``; the ``ordermap`` crate is now deprecated
 195     and the types ``OrderMap/Set`` now have a deprecation notice.
 196
 197 - 0.4.0
 198
 199   - This is the last release series for this ``ordermap`` under that name,
 200     because the crate is **going to be renamed** to ``indexmap`` (with types
 201     ``IndexMap``, ``IndexSet``) and no change in functionality!
 202   - The map and its associated structs moved into the ``map`` submodule of the
 203     crate, so that the map and set are symmetric
 204
 205     + The iterators, ``Entry`` and other structs are now under ``ordermap::map::``
 206
 207   - Internally refactored ``OrderMap<K, V, S>`` so that all the main algorithms
 208     (insertion, lookup, removal etc) that don't use the ``S`` parameter (the
 209     hasher) are compiled without depending on ``S``, which reduces generics bloat.
 210
 211   - ``Entry<K, V>`` no longer has a type parameter ``S``, which is just like
 212     the standard ``HashMap``'s entry.
 213
 214   - Minimum Rust version requirement increased to Rust 1.18
 215
 216 - 0.3.5
 217
 218   - Documentation improvements
 219
 220 - 0.3.4
 221
 222   - The ``.retain()`` methods for ``OrderMap`` and ``OrderSet`` now
 223     traverse the elements in order, and the retained elements **keep their order**
 224   - Added new methods ``.sort_by()``, ``.sort_keys()`` to ``OrderMap`` and
 225     ``.sort_by()``, ``.sort()`` to ``OrderSet``. These methods allow you to
 226     sort the maps in place efficiently.
 227
 228 - 0.3.3
 229
 230   - Document insertion behaviour better by @lucab
 231   - Updated dependences (no feature changes) by @ignatenkobrain
 232
 233 - 0.3.2
 234
 235   - Add ``OrderSet`` by @cuviper!
 236   - ``OrderMap::drain`` is now (too) a double ended iterator.
 237
 238 - 0.3.1
 239
 240   - In all ordermap iterators, forward the ``collect`` method to the underlying
 241     iterator as well.
 242   - Add crates.io categories.
 243
 244 - 0.3.0
 245
 246   - The methods ``get_pair``, ``get_pair_index`` were both replaced by
 247     ``get_full`` (and the same for the mutable case).
 248   - Method ``swap_remove_pair`` replaced by ``swap_remove_full``.
 249   - Add trait ``MutableKeys`` for opt-in mutable key access. Mutable key access
 250     is only possible through the methods of this extension trait.
 251   - Add new trait ``Equivalent`` for key equivalence. This extends the
 252     ``Borrow`` trait mechanism for ``OrderMap::get`` in a backwards compatible
 253     way, just some minor type inference related issues may become apparent.
 254     See `#10`__ for more information.
 255   - Implement ``Extend<(&K, &V)>`` by @xfix.
 256
 257 __ https://github.com/bluss/ordermap/pull/10
 258
 259 - 0.2.13
 260
 261   - Fix deserialization to support custom hashers by @Techcable.
 262   - Add methods ``.index()`` on the entry types by @garro95.
 263
 264 - 0.2.12
 265
 266   - Add methods ``.with_hasher()``, ``.hasher()``.
 267
 268 - 0.2.11
 269
 270   - Support ``ExactSizeIterator`` for the iterators. By @Binero.
 271   - Use ``Box<[Pos]>`` internally, saving a word in the ``OrderMap`` struct.
 272   - Serde support, with crate feature ``"serde-1"``. By @xfix.
 273
 274 - 0.2.10
 275
 276   - Add iterator ``.drain(..)`` by @stevej.
 277
 278 - 0.2.9
 279
 280   - Add method ``.is_empty()`` by @overvenus.
 281   - Implement ``PartialEq, Eq`` by @overvenus.
 282   - Add method ``.sorted_by()``.
 283
 284 - 0.2.8
 285
 286   - Add iterators ``.values()`` and ``.values_mut()``.
 287   - Fix compatibility with 32-bit platforms.
 288
 289 - 0.2.7
 290
 291   - Add ``.retain()``.
 292
 293 - 0.2.6
 294
 295   - Add ``OccupiedEntry::remove_entry`` and other minor entry methods,
 296     so that it now has all the features of ``HashMap``'s entries.
 297
 298 - 0.2.5
 299
 300   - Improved ``.pop()`` slightly.
 301
 302 - 0.2.4
 303
 304   - Improved performance of ``.insert()`` (`#3`__) by @pczarn.
 305
 306 __ https://github.com/bluss/ordermap/pull/3
 307
 308 - 0.2.3
 309
 310   - Generalize ``Entry`` for now, so that it works on hashmaps with non-default
 311     hasher. However, there's a lingering compat issue since libstd ``HashMap``
 312     does not parameterize its entries by the hasher (``S`` typarm).
 313   - Special case some iterator methods like ``.nth()``.
 314
 315 - 0.2.2
 316
 317   - Disable the verbose ``Debug`` impl by default.
 318
 319 - 0.2.1
 320
 321   - Fix doc links and clarify docs.
 322
 323 - 0.2.0
 324
 325   - Add more ``HashMap`` methods & compat with its API.
 326   - Experimental support for ``.entry()`` (the simplest parts of the API).
 327   - Add ``.reserve()`` (placeholder impl).
 328   - Add ``.remove()`` as synonym for ``.swap_remove()``.
 329   - Changed ``.insert()`` to swap value if the entry already exists, and
 330     return ``Option``.
 331   - Experimental support as an *indexed* hash map! Added methods
 332     ``.get_index()``, ``.get_index_mut()``, ``.swap_remove_index()``,
 333     ``.get_pair_index()``, ``.get_pair_index_mut()``.
 334
 335 - 0.1.2
 336
 337   - Implement the 32/32 split idea for ``Pos`` which improves cache utilization
 338     and lookup performance.
 339
 340 - 0.1.1
 341
 342   - Initial release.