]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
1 | indexmap |
2 | ======== | |
3 | ||
4 | |build_status|_ |crates|_ |docs|_ |rustc|_ | |
5 | ||
5869c6ff XL |
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 | |
8 | ||
3dfed10e XL |
9 | .. |crates| image:: https://img.shields.io/crates/v/indexmap.svg |
10 | .. _crates: https://crates.io/crates/indexmap | |
11 | ||
3dfed10e XL |
12 | .. |docs| image:: https://docs.rs/indexmap/badge.svg |
13 | .. _docs: https://docs.rs/indexmap | |
14 | ||
5869c6ff XL |
15 | .. |rustc| image:: https://img.shields.io/badge/rust-1.36%2B-orange.svg |
16 | .. _rustc: https://img.shields.io/badge/rust-1.36%2B-orange.svg | |
3dfed10e XL |
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 | ||
6a06907d XL |
69 | - 1.6.2 |
70 | ||
71 | - Fixed to match ``std`` behavior, ``OccupiedEntry::key`` now references the | |
72 | existing key in the map instead of the lookup key, by @cuviper in PR 170_. | |
73 | ||
74 | - The new ``Entry::or_insert_with_key`` matches Rust 1.50's ``Entry`` method, | |
75 | passing ``&K`` to the callback to create a value, by @cuviper in PR 175_. | |
76 | ||
77 | .. _170: https://github.com/bluss/indexmap/pull/170 | |
78 | .. _175: https://github.com/bluss/indexmap/pull/175 | |
79 | ||
5869c6ff XL |
80 | - 1.6.1 |
81 | ||
82 | - The new ``serde_seq`` module implements ``IndexMap`` serialization as a | |
83 | sequence to ensure order is preserved, by @cuviper in PR 158_. | |
84 | ||
85 | - New methods on maps and sets work like the ``Vec``/slice methods by the same name: | |
86 | ``truncate``, ``split_off``, ``first``, ``first_mut``, ``last``, ``last_mut``, and | |
87 | ``swap_indices``, by @cuviper in PR 160_. | |
88 | ||
89 | .. _158: https://github.com/bluss/indexmap/pull/158 | |
90 | .. _160: https://github.com/bluss/indexmap/pull/160 | |
91 | ||
1b1a35ee XL |
92 | - 1.6.0 |
93 | ||
94 | - **MSRV**: Rust 1.36 or later is now required. | |
95 | ||
96 | - The ``hashbrown`` dependency has been updated to version 0.9. | |
97 | ||
98 | - 1.5.2 | |
99 | ||
100 | - The new "std" feature will force the use of ``std`` for users that explicitly | |
101 | want the default ``S = RandomState``, bypassing the autodetection added in 1.3.0, | |
102 | by @cuviper in PR 145_. | |
103 | ||
104 | .. _145: https://github.com/bluss/indexmap/pull/145 | |
105 | ||
3dfed10e XL |
106 | - 1.5.1 |
107 | ||
108 | - Values can now be indexed by their ``usize`` position by @cuviper in PR 132_. | |
109 | ||
110 | - Some of the generic bounds have been relaxed to match ``std`` by @cuviper in PR 141_. | |
111 | ||
112 | - ``drain`` now accepts any ``R: RangeBounds<usize>`` by @cuviper in PR 142_. | |
113 | ||
114 | .. _132: https://github.com/bluss/indexmap/pull/132 | |
115 | .. _141: https://github.com/bluss/indexmap/pull/141 | |
116 | .. _142: https://github.com/bluss/indexmap/pull/142 | |
117 | ||
118 | - 1.5.0 | |
119 | ||
120 | - **MSRV**: Rust 1.32 or later is now required. | |
121 | ||
122 | - The inner hash table is now based on ``hashbrown`` by @cuviper in PR 131_. | |
123 | This also completes the method ``reserve`` and adds ``shrink_to_fit``. | |
124 | ||
125 | - Add new methods ``get_key_value``, ``remove_entry``, ``swap_remove_entry``, | |
126 | and ``shift_remove_entry``, by @cuviper in PR 136_ | |
127 | ||
128 | - ``Clone::clone_from`` reuses allocations by @cuviper in PR 125_ | |
129 | ||
130 | - Add new method ``reverse`` by @linclelinkpart5 in PR 128_ | |
131 | ||
132 | .. _125: https://github.com/bluss/indexmap/pull/125 | |
133 | .. _128: https://github.com/bluss/indexmap/pull/128 | |
134 | .. _131: https://github.com/bluss/indexmap/pull/131 | |
135 | .. _136: https://github.com/bluss/indexmap/pull/136 | |
136 | ||
137 | - 1.4.0 | |
138 | ||
139 | - Add new method ``get_index_of`` by @Thermatrix in PR 115_ and 120_ | |
140 | ||
141 | - Fix build script rebuild-if-changed configuration to use "build.rs"; | |
142 | fixes issue 123_. Fix by @cuviper. | |
143 | ||
144 | - Dev-dependencies (rand and quickcheck) have been updated. The crate's tests | |
145 | now run using Rust 1.32 or later (MSRV for building the crate has not changed). | |
146 | by @kjeremy and @bluss | |
147 | ||
148 | .. _123: https://github.com/bluss/indexmap/issues/123 | |
149 | .. _115: https://github.com/bluss/indexmap/pull/115 | |
150 | .. _120: https://github.com/bluss/indexmap/pull/120 | |
151 | ||
152 | - 1.3.2 | |
153 | ||
154 | - Maintenance update to regenerate the published `Cargo.toml`. | |
155 | ||
156 | - 1.3.1 | |
157 | ||
158 | - Maintenance update for formatting and ``autocfg`` 1.0. | |
159 | ||
160 | - 1.3.0 | |
161 | ||
162 | - The deprecation messages in the previous version have been removed. | |
163 | (The methods have not otherwise changed.) Docs for removal methods have been | |
164 | improved. | |
165 | - From Rust 1.36, this crate supports being built **without std**, requiring | |
166 | ``alloc`` instead. This is enabled automatically when it is detected that | |
167 | ``std`` is not available. There is no crate feature to enable/disable to | |
168 | trigger this. The new build-dep ``autocfg`` enables this. | |
169 | ||
170 | - 1.2.0 | |
171 | ||
172 | - Plain ``.remove()`` now has a deprecation message, it informs the user | |
173 | about picking one of the removal functions ``swap_remove`` and ``shift_remove`` | |
174 | which have different performance and order semantics. | |
175 | Plain ``.remove()`` will not be removed, the warning message and method | |
176 | will remain until further. | |
177 | ||
178 | - Add new method ``shift_remove`` for order preserving removal on the map, | |
179 | and ``shift_take`` for the corresponding operation on the set. | |
180 | ||
181 | - Add methods ``swap_remove``, ``swap_remove_entry`` to ``Entry``. | |
182 | ||
183 | - Fix indexset/indexmap to support full paths, like ``indexmap::indexmap!()`` | |
184 | ||
185 | - Internal improvements: fix warnings, deprecations and style lints | |
186 | ||
187 | - 1.1.0 | |
188 | ||
189 | - Added optional feature `"rayon"` that adds parallel iterator support | |
190 | to `IndexMap` and `IndexSet` using Rayon. This includes all the regular | |
191 | iterators in parallel versions, and parallel sort. | |
192 | ||
193 | - Implemented ``Clone`` for ``map::{Iter, Keys, Values}`` and | |
194 | ``set::{Difference, Intersection, Iter, SymmetricDifference, Union}`` | |
195 | ||
196 | - Implemented ``Debug`` for ``map::{Entry, IntoIter, Iter, Keys, Values}`` and | |
197 | ``set::{Difference, Intersection, IntoIter, Iter, SymmetricDifference, Union}`` | |
198 | ||
199 | - Serde trait ``IntoDeserializer`` are implemented for ``IndexMap`` and ``IndexSet``. | |
200 | ||
201 | - Minimum Rust version requirement increased to Rust 1.30 for development builds. | |
202 | ||
203 | - 1.0.2 | |
204 | ||
205 | - The new methods ``IndexMap::insert_full`` and ``IndexSet::insert_full`` are | |
206 | both like ``insert`` with the index included in the return value. | |
207 | ||
208 | - The new method ``Entry::and_modify`` can be used to modify occupied | |
209 | entries, matching the new methods of ``std`` maps in Rust 1.26. | |
210 | ||
211 | - The new method ``Entry::or_default`` inserts a default value in unoccupied | |
212 | entries, matching the new methods of ``std`` maps in Rust 1.28. | |
213 | ||
214 | - 1.0.1 | |
215 | ||
216 | - Document Rust version policy for the crate (see rustdoc) | |
217 | ||
218 | - 1.0.0 | |
219 | ||
220 | - This is the 1.0 release for ``indexmap``! (the crate and datastructure | |
221 | formerly known as “ordermap”) | |
222 | - ``OccupiedEntry::insert`` changed its signature, to use ``&mut self`` for | |
223 | the method receiver, matching the equivalent method for a standard | |
224 | ``HashMap``. Thanks to @dtolnay for finding this bug. | |
225 | - The deprecated old names from ordermap were removed: ``OrderMap``, | |
226 | ``OrderSet``, ``ordermap!{}``, ``orderset!{}``. Use the new ``IndexMap`` | |
227 | etc names instead. | |
228 | ||
229 | - 0.4.1 | |
230 | ||
231 | - Renamed crate to ``indexmap``; the ``ordermap`` crate is now deprecated | |
232 | and the types ``OrderMap/Set`` now have a deprecation notice. | |
233 | ||
234 | - 0.4.0 | |
235 | ||
236 | - This is the last release series for this ``ordermap`` under that name, | |
237 | because the crate is **going to be renamed** to ``indexmap`` (with types | |
238 | ``IndexMap``, ``IndexSet``) and no change in functionality! | |
239 | - The map and its associated structs moved into the ``map`` submodule of the | |
240 | crate, so that the map and set are symmetric | |
241 | ||
242 | + The iterators, ``Entry`` and other structs are now under ``ordermap::map::`` | |
243 | ||
244 | - Internally refactored ``OrderMap<K, V, S>`` so that all the main algorithms | |
245 | (insertion, lookup, removal etc) that don't use the ``S`` parameter (the | |
246 | hasher) are compiled without depending on ``S``, which reduces generics bloat. | |
247 | ||
248 | - ``Entry<K, V>`` no longer has a type parameter ``S``, which is just like | |
249 | the standard ``HashMap``'s entry. | |
250 | ||
251 | - Minimum Rust version requirement increased to Rust 1.18 | |
252 | ||
253 | - 0.3.5 | |
254 | ||
255 | - Documentation improvements | |
256 | ||
257 | - 0.3.4 | |
258 | ||
259 | - The ``.retain()`` methods for ``OrderMap`` and ``OrderSet`` now | |
260 | traverse the elements in order, and the retained elements **keep their order** | |
261 | - Added new methods ``.sort_by()``, ``.sort_keys()`` to ``OrderMap`` and | |
262 | ``.sort_by()``, ``.sort()`` to ``OrderSet``. These methods allow you to | |
263 | sort the maps in place efficiently. | |
264 | ||
265 | - 0.3.3 | |
266 | ||
267 | - Document insertion behaviour better by @lucab | |
268 | - Updated dependences (no feature changes) by @ignatenkobrain | |
269 | ||
270 | - 0.3.2 | |
271 | ||
272 | - Add ``OrderSet`` by @cuviper! | |
273 | - ``OrderMap::drain`` is now (too) a double ended iterator. | |
274 | ||
275 | - 0.3.1 | |
276 | ||
277 | - In all ordermap iterators, forward the ``collect`` method to the underlying | |
278 | iterator as well. | |
279 | - Add crates.io categories. | |
280 | ||
281 | - 0.3.0 | |
282 | ||
283 | - The methods ``get_pair``, ``get_pair_index`` were both replaced by | |
284 | ``get_full`` (and the same for the mutable case). | |
285 | - Method ``swap_remove_pair`` replaced by ``swap_remove_full``. | |
286 | - Add trait ``MutableKeys`` for opt-in mutable key access. Mutable key access | |
287 | is only possible through the methods of this extension trait. | |
288 | - Add new trait ``Equivalent`` for key equivalence. This extends the | |
289 | ``Borrow`` trait mechanism for ``OrderMap::get`` in a backwards compatible | |
290 | way, just some minor type inference related issues may become apparent. | |
291 | See `#10`__ for more information. | |
292 | - Implement ``Extend<(&K, &V)>`` by @xfix. | |
293 | ||
294 | __ https://github.com/bluss/ordermap/pull/10 | |
295 | ||
296 | - 0.2.13 | |
297 | ||
298 | - Fix deserialization to support custom hashers by @Techcable. | |
299 | - Add methods ``.index()`` on the entry types by @garro95. | |
300 | ||
301 | - 0.2.12 | |
302 | ||
303 | - Add methods ``.with_hasher()``, ``.hasher()``. | |
304 | ||
305 | - 0.2.11 | |
306 | ||
307 | - Support ``ExactSizeIterator`` for the iterators. By @Binero. | |
308 | - Use ``Box<[Pos]>`` internally, saving a word in the ``OrderMap`` struct. | |
309 | - Serde support, with crate feature ``"serde-1"``. By @xfix. | |
310 | ||
311 | - 0.2.10 | |
312 | ||
313 | - Add iterator ``.drain(..)`` by @stevej. | |
314 | ||
315 | - 0.2.9 | |
316 | ||
317 | - Add method ``.is_empty()`` by @overvenus. | |
318 | - Implement ``PartialEq, Eq`` by @overvenus. | |
319 | - Add method ``.sorted_by()``. | |
320 | ||
321 | - 0.2.8 | |
322 | ||
323 | - Add iterators ``.values()`` and ``.values_mut()``. | |
324 | - Fix compatibility with 32-bit platforms. | |
325 | ||
326 | - 0.2.7 | |
327 | ||
328 | - Add ``.retain()``. | |
329 | ||
330 | - 0.2.6 | |
331 | ||
332 | - Add ``OccupiedEntry::remove_entry`` and other minor entry methods, | |
333 | so that it now has all the features of ``HashMap``'s entries. | |
334 | ||
335 | - 0.2.5 | |
336 | ||
337 | - Improved ``.pop()`` slightly. | |
338 | ||
339 | - 0.2.4 | |
340 | ||
341 | - Improved performance of ``.insert()`` (`#3`__) by @pczarn. | |
342 | ||
343 | __ https://github.com/bluss/ordermap/pull/3 | |
344 | ||
345 | - 0.2.3 | |
346 | ||
347 | - Generalize ``Entry`` for now, so that it works on hashmaps with non-default | |
348 | hasher. However, there's a lingering compat issue since libstd ``HashMap`` | |
349 | does not parameterize its entries by the hasher (``S`` typarm). | |
350 | - Special case some iterator methods like ``.nth()``. | |
351 | ||
352 | - 0.2.2 | |
353 | ||
354 | - Disable the verbose ``Debug`` impl by default. | |
355 | ||
356 | - 0.2.1 | |
357 | ||
358 | - Fix doc links and clarify docs. | |
359 | ||
360 | - 0.2.0 | |
361 | ||
362 | - Add more ``HashMap`` methods & compat with its API. | |
363 | - Experimental support for ``.entry()`` (the simplest parts of the API). | |
364 | - Add ``.reserve()`` (placeholder impl). | |
365 | - Add ``.remove()`` as synonym for ``.swap_remove()``. | |
366 | - Changed ``.insert()`` to swap value if the entry already exists, and | |
367 | return ``Option``. | |
368 | - Experimental support as an *indexed* hash map! Added methods | |
369 | ``.get_index()``, ``.get_index_mut()``, ``.swap_remove_index()``, | |
370 | ``.get_pair_index()``, ``.get_pair_index_mut()``. | |
371 | ||
372 | - 0.1.2 | |
373 | ||
374 | - Implement the 32/32 split idea for ``Pos`` which improves cache utilization | |
375 | and lookup performance. | |
376 | ||
377 | - 0.1.1 | |
378 | ||
379 | - Initial release. |