4 |build_status|_ |crates|_ |docs|_ |rustc|_
6 .. |build_status| image:: https://github.com/bluss/indexmap/workflows/Continuous%20integration/badge.svg?branch=master
7 .. _build_status: https://github.com/bluss/indexmap/actions
9 .. |crates| image:: https://img.shields.io/crates/v/indexmap.svg
10 .. _crates: https://crates.io/crates/indexmap
12 .. |docs| image:: https://docs.rs/indexmap/badge.svg
13 .. _docs: https://docs.rs/indexmap
15 .. |rustc| image:: https://img.shields.io/badge/rust-1.49%2B-orange.svg
16 .. _rustc: https://img.shields.io/badge/rust-1.49%2B-orange.svg
18 A pure-Rust hash table which preserves (in a limited sense) insertion order.
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.
25 Note: this crate was originally released under the name ``ordermap``,
26 but it was renamed to ``indexmap`` to better reflect its features.
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).
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:
37 - Order is **independent of hash function** and hash values of keys.
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.
46 ``IndexMap`` derives a couple of performance facts directly from how it is constructed,
49 A raw hash table of key-value indices, and a vector of key-value pairs.
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.)
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.
63 .. _PR45282: https://github.com/rust-lang/rust/pull/45282
71 - **MSRV**: Rust 1.49 or later is now required.
73 - The ``hashbrown`` dependency has been updated to version 0.11.
77 - Fixed to match ``std`` behavior, ``OccupiedEntry::key`` now references the
78 existing key in the map instead of the lookup key, by @cuviper in PR 170_.
80 - The new ``Entry::or_insert_with_key`` matches Rust 1.50's ``Entry`` method,
81 passing ``&K`` to the callback to create a value, by @cuviper in PR 175_.
83 .. _170: https://github.com/bluss/indexmap/pull/170
84 .. _175: https://github.com/bluss/indexmap/pull/175
88 - The new ``serde_seq`` module implements ``IndexMap`` serialization as a
89 sequence to ensure order is preserved, by @cuviper in PR 158_.
91 - New methods on maps and sets work like the ``Vec``/slice methods by the same name:
92 ``truncate``, ``split_off``, ``first``, ``first_mut``, ``last``, ``last_mut``, and
93 ``swap_indices``, by @cuviper in PR 160_.
95 .. _158: https://github.com/bluss/indexmap/pull/158
96 .. _160: https://github.com/bluss/indexmap/pull/160
100 - **MSRV**: Rust 1.36 or later is now required.
102 - The ``hashbrown`` dependency has been updated to version 0.9.
106 - The new "std" feature will force the use of ``std`` for users that explicitly
107 want the default ``S = RandomState``, bypassing the autodetection added in 1.3.0,
108 by @cuviper in PR 145_.
110 .. _145: https://github.com/bluss/indexmap/pull/145
114 - Values can now be indexed by their ``usize`` position by @cuviper in PR 132_.
116 - Some of the generic bounds have been relaxed to match ``std`` by @cuviper in PR 141_.
118 - ``drain`` now accepts any ``R: RangeBounds<usize>`` by @cuviper in PR 142_.
120 .. _132: https://github.com/bluss/indexmap/pull/132
121 .. _141: https://github.com/bluss/indexmap/pull/141
122 .. _142: https://github.com/bluss/indexmap/pull/142
126 - **MSRV**: Rust 1.32 or later is now required.
128 - The inner hash table is now based on ``hashbrown`` by @cuviper in PR 131_.
129 This also completes the method ``reserve`` and adds ``shrink_to_fit``.
131 - Add new methods ``get_key_value``, ``remove_entry``, ``swap_remove_entry``,
132 and ``shift_remove_entry``, by @cuviper in PR 136_
134 - ``Clone::clone_from`` reuses allocations by @cuviper in PR 125_
136 - Add new method ``reverse`` by @linclelinkpart5 in PR 128_
138 .. _125: https://github.com/bluss/indexmap/pull/125
139 .. _128: https://github.com/bluss/indexmap/pull/128
140 .. _131: https://github.com/bluss/indexmap/pull/131
141 .. _136: https://github.com/bluss/indexmap/pull/136
145 - Add new method ``get_index_of`` by @Thermatrix in PR 115_ and 120_
147 - Fix build script rebuild-if-changed configuration to use "build.rs";
148 fixes issue 123_. Fix by @cuviper.
150 - Dev-dependencies (rand and quickcheck) have been updated. The crate's tests
151 now run using Rust 1.32 or later (MSRV for building the crate has not changed).
152 by @kjeremy and @bluss
154 .. _123: https://github.com/bluss/indexmap/issues/123
155 .. _115: https://github.com/bluss/indexmap/pull/115
156 .. _120: https://github.com/bluss/indexmap/pull/120
160 - Maintenance update to regenerate the published `Cargo.toml`.
164 - Maintenance update for formatting and ``autocfg`` 1.0.
168 - The deprecation messages in the previous version have been removed.
169 (The methods have not otherwise changed.) Docs for removal methods have been
171 - From Rust 1.36, this crate supports being built **without std**, requiring
172 ``alloc`` instead. This is enabled automatically when it is detected that
173 ``std`` is not available. There is no crate feature to enable/disable to
174 trigger this. The new build-dep ``autocfg`` enables this.
178 - Plain ``.remove()`` now has a deprecation message, it informs the user
179 about picking one of the removal functions ``swap_remove`` and ``shift_remove``
180 which have different performance and order semantics.
181 Plain ``.remove()`` will not be removed, the warning message and method
182 will remain until further.
184 - Add new method ``shift_remove`` for order preserving removal on the map,
185 and ``shift_take`` for the corresponding operation on the set.
187 - Add methods ``swap_remove``, ``swap_remove_entry`` to ``Entry``.
189 - Fix indexset/indexmap to support full paths, like ``indexmap::indexmap!()``
191 - Internal improvements: fix warnings, deprecations and style lints
195 - Added optional feature `"rayon"` that adds parallel iterator support
196 to `IndexMap` and `IndexSet` using Rayon. This includes all the regular
197 iterators in parallel versions, and parallel sort.
199 - Implemented ``Clone`` for ``map::{Iter, Keys, Values}`` and
200 ``set::{Difference, Intersection, Iter, SymmetricDifference, Union}``
202 - Implemented ``Debug`` for ``map::{Entry, IntoIter, Iter, Keys, Values}`` and
203 ``set::{Difference, Intersection, IntoIter, Iter, SymmetricDifference, Union}``
205 - Serde trait ``IntoDeserializer`` are implemented for ``IndexMap`` and ``IndexSet``.
207 - Minimum Rust version requirement increased to Rust 1.30 for development builds.
211 - The new methods ``IndexMap::insert_full`` and ``IndexSet::insert_full`` are
212 both like ``insert`` with the index included in the return value.
214 - The new method ``Entry::and_modify`` can be used to modify occupied
215 entries, matching the new methods of ``std`` maps in Rust 1.26.
217 - The new method ``Entry::or_default`` inserts a default value in unoccupied
218 entries, matching the new methods of ``std`` maps in Rust 1.28.
222 - Document Rust version policy for the crate (see rustdoc)
226 - This is the 1.0 release for ``indexmap``! (the crate and datastructure
227 formerly known as “ordermap”)
228 - ``OccupiedEntry::insert`` changed its signature, to use ``&mut self`` for
229 the method receiver, matching the equivalent method for a standard
230 ``HashMap``. Thanks to @dtolnay for finding this bug.
231 - The deprecated old names from ordermap were removed: ``OrderMap``,
232 ``OrderSet``, ``ordermap!{}``, ``orderset!{}``. Use the new ``IndexMap``
237 - Renamed crate to ``indexmap``; the ``ordermap`` crate is now deprecated
238 and the types ``OrderMap/Set`` now have a deprecation notice.
242 - This is the last release series for this ``ordermap`` under that name,
243 because the crate is **going to be renamed** to ``indexmap`` (with types
244 ``IndexMap``, ``IndexSet``) and no change in functionality!
245 - The map and its associated structs moved into the ``map`` submodule of the
246 crate, so that the map and set are symmetric
248 + The iterators, ``Entry`` and other structs are now under ``ordermap::map::``
250 - Internally refactored ``OrderMap<K, V, S>`` so that all the main algorithms
251 (insertion, lookup, removal etc) that don't use the ``S`` parameter (the
252 hasher) are compiled without depending on ``S``, which reduces generics bloat.
254 - ``Entry<K, V>`` no longer has a type parameter ``S``, which is just like
255 the standard ``HashMap``'s entry.
257 - Minimum Rust version requirement increased to Rust 1.18
261 - Documentation improvements
265 - The ``.retain()`` methods for ``OrderMap`` and ``OrderSet`` now
266 traverse the elements in order, and the retained elements **keep their order**
267 - Added new methods ``.sort_by()``, ``.sort_keys()`` to ``OrderMap`` and
268 ``.sort_by()``, ``.sort()`` to ``OrderSet``. These methods allow you to
269 sort the maps in place efficiently.
273 - Document insertion behaviour better by @lucab
274 - Updated dependences (no feature changes) by @ignatenkobrain
278 - Add ``OrderSet`` by @cuviper!
279 - ``OrderMap::drain`` is now (too) a double ended iterator.
283 - In all ordermap iterators, forward the ``collect`` method to the underlying
285 - Add crates.io categories.
289 - The methods ``get_pair``, ``get_pair_index`` were both replaced by
290 ``get_full`` (and the same for the mutable case).
291 - Method ``swap_remove_pair`` replaced by ``swap_remove_full``.
292 - Add trait ``MutableKeys`` for opt-in mutable key access. Mutable key access
293 is only possible through the methods of this extension trait.
294 - Add new trait ``Equivalent`` for key equivalence. This extends the
295 ``Borrow`` trait mechanism for ``OrderMap::get`` in a backwards compatible
296 way, just some minor type inference related issues may become apparent.
297 See `#10`__ for more information.
298 - Implement ``Extend<(&K, &V)>`` by @xfix.
300 __ https://github.com/bluss/ordermap/pull/10
304 - Fix deserialization to support custom hashers by @Techcable.
305 - Add methods ``.index()`` on the entry types by @garro95.
309 - Add methods ``.with_hasher()``, ``.hasher()``.
313 - Support ``ExactSizeIterator`` for the iterators. By @Binero.
314 - Use ``Box<[Pos]>`` internally, saving a word in the ``OrderMap`` struct.
315 - Serde support, with crate feature ``"serde-1"``. By @xfix.
319 - Add iterator ``.drain(..)`` by @stevej.
323 - Add method ``.is_empty()`` by @overvenus.
324 - Implement ``PartialEq, Eq`` by @overvenus.
325 - Add method ``.sorted_by()``.
329 - Add iterators ``.values()`` and ``.values_mut()``.
330 - Fix compatibility with 32-bit platforms.
338 - Add ``OccupiedEntry::remove_entry`` and other minor entry methods,
339 so that it now has all the features of ``HashMap``'s entries.
343 - Improved ``.pop()`` slightly.
347 - Improved performance of ``.insert()`` (`#3`__) by @pczarn.
349 __ https://github.com/bluss/ordermap/pull/3
353 - Generalize ``Entry`` for now, so that it works on hashmaps with non-default
354 hasher. However, there's a lingering compat issue since libstd ``HashMap``
355 does not parameterize its entries by the hasher (``S`` typarm).
356 - Special case some iterator methods like ``.nth()``.
360 - Disable the verbose ``Debug`` impl by default.
364 - Fix doc links and clarify docs.
368 - Add more ``HashMap`` methods & compat with its API.
369 - Experimental support for ``.entry()`` (the simplest parts of the API).
370 - Add ``.reserve()`` (placeholder impl).
371 - Add ``.remove()`` as synonym for ``.swap_remove()``.
372 - Changed ``.insert()`` to swap value if the entry already exists, and
374 - Experimental support as an *indexed* hash map! Added methods
375 ``.get_index()``, ``.get_index_mut()``, ``.swap_remove_index()``,
376 ``.get_pair_index()``, ``.get_pair_index_mut()``.
380 - Implement the 32/32 split idea for ``Pos`` which improves cache utilization
381 and lookup performance.