126 lines
21 KiB
HTML
126 lines
21 KiB
HTML
<!DOCTYPE html><html lang="en"><head><meta charset="utf-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="generator" content="rustdoc"><meta name="description" content="slotmap"><title>slotmap - Rust</title><script>if(window.location.protocol!=="file:")document.head.insertAdjacentHTML("beforeend","SourceSerif4-Regular-6b053e98.ttf.woff2,FiraSans-Regular-0fe48ade.woff2,FiraSans-Medium-e1aa3f0a.woff2,SourceCodePro-Regular-8badfe75.ttf.woff2,SourceCodePro-Semibold-aa29a496.ttf.woff2".split(",").map(f=>`<link rel="preload" as="font" type="font/woff2" crossorigin href="../static.files/${f}">`).join(""))</script><link rel="stylesheet" href="../static.files/normalize-9960930a.css"><link rel="stylesheet" href="../static.files/rustdoc-42caa33d.css"><meta name="rustdoc-vars" data-root-path="../" data-static-root-path="../static.files/" data-current-crate="slotmap" data-themes="" data-resource-suffix="" data-rustdoc-version="1.84.0 (9fc6b4312 2025-01-07)" data-channel="1.84.0" data-search-js="search-92e6798f.js" data-settings-js="settings-0f613d39.js" ><script src="../static.files/storage-59e33391.js"></script><script defer src="../crates.js"></script><script defer src="../static.files/main-5f194d8c.js"></script><noscript><link rel="stylesheet" href="../static.files/noscript-893ab5e7.css"></noscript><link rel="alternate icon" type="image/png" href="../static.files/favicon-32x32-6580c154.png"><link rel="icon" type="image/svg+xml" href="../static.files/favicon-044be391.svg"></head><body class="rustdoc mod crate"><!--[if lte IE 11]><div class="warning">This old browser is unsupported and will most likely display funky things.</div><![endif]--><nav class="mobile-topbar"><button class="sidebar-menu-toggle" title="show sidebar"></button></nav><nav class="sidebar"><div class="sidebar-crate"><h2><a href="../slotmap/index.html">slotmap</a><span class="version">1.0.7</span></h2></div><div class="sidebar-elems"><ul class="block"><li><a id="all-types" href="all.html">All Items</a></li></ul><section id="rustdoc-toc"><h3><a href="#">Sections</a></h3><ul class="block top-toc"><li><a href="#slotmap" title="slotmap">slotmap</a></li><li><a href="#examples" title="Examples">Examples</a></li><li><a href="#serialization-through-serde-no_std-support-and-unstable-features" title="Serialization through `serde`, `no_std` support and unstable features">Serialization through <code>serde</code>, <code>no_std</code> support and unstable features</a></li><li><a href="#why-not-index-a-vec-or-use-slab-stable-vec-etc" title="Why not index a `Vec`, or use `slab`, `stable-vec`, etc?">Why not index a <code>Vec</code>, or use <code>slab</code>, <code>stable-vec</code>, etc?</a></li><li><a href="#performance-characteristics-and-implementation-details" title="Performance characteristics and implementation details">Performance characteristics and implementation details</a></li><li><a href="#choosing-slotmap-hopslotmap-or-denseslotmap" title="Choosing `SlotMap`, `HopSlotMap` or `DenseSlotMap`">Choosing <code>SlotMap</code>, <code>HopSlotMap</code> or <code>DenseSlotMap</code></a></li><li><a href="#choosing-secondarymap-or-sparsesecondarymap" title="Choosing `SecondaryMap` or `SparseSecondaryMap`">Choosing <code>SecondaryMap</code> or <code>SparseSecondaryMap</code></a></li><li><a href="#custom-key-types" title="Custom key types">Custom key types</a></li></ul><h3><a href="#modules">Crate Items</a></h3><ul class="block"><li><a href="#modules" title="Modules">Modules</a></li><li><a href="#macros" title="Macros">Macros</a></li><li><a href="#structs" title="Structs">Structs</a></li><li><a href="#traits" title="Traits">Traits</a></li></ul></section><div id="rustdoc-modnav"></div></div></nav><div class="sidebar-resizer"></div><main><div class="width-limiter"><rustdoc-search></rustdoc-search><section id="main-content" class="content"><div class="main-heading"><h1>Crate <span>slotmap</span><button id="copy-path" title="Copy item path to clipboard">Copy item path</button></h1><rustdoc-toolbar></rustdoc-toolbar><span class="sub-heading"><a class="src" href="../src/slotmap/lib.rs.html#1-652">Source</a> </span></div><details class="toggle top-doc" open><summary class="hideme"><span>Expand description</span></summary><div class="docblock"><h2 id="slotmap"><a class="doc-anchor" href="#slotmap">§</a>slotmap</h2>
|
||
<p>This library provides a container with persistent unique keys to access
|
||
stored values, <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a>. Upon insertion a key is returned that can be
|
||
used to later access or remove the values. Insertion, removal and access all
|
||
take O(1) time with low overhead. Great for storing collections of objects
|
||
that need stable, safe references but have no clear ownership otherwise,
|
||
such as game entities or graph nodes.</p>
|
||
<p>The difference between a <a href="https://doc.rust-lang.org/1.84.0/alloc/collections/btree/map/struct.BTreeMap.html" title="struct alloc::collections::btree::map::BTreeMap"><code>BTreeMap</code></a> or <a href="https://doc.rust-lang.org/1.84.0/std/collections/hash/map/struct.HashMap.html" title="struct std::collections::hash::map::HashMap"><code>HashMap</code></a> and a slot map is
|
||
that the slot map generates and returns the key when inserting a value. A
|
||
key is always unique and will only refer to the value that was inserted.
|
||
A slot map’s main purpose is to simply own things in a safe and efficient
|
||
manner.</p>
|
||
<p>You can also create (multiple) secondary maps that can map the keys returned
|
||
by <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> to other values, to associate arbitrary data with objects
|
||
stored in slot maps, without hashing required - it’s direct indexing under
|
||
the hood.</p>
|
||
<p>The minimum required stable Rust version for this crate is 1.49.</p>
|
||
<h2 id="examples"><a class="doc-anchor" href="#examples">§</a>Examples</h2>
|
||
<div class="example-wrap"><pre class="rust rust-example-rendered"><code><span class="kw">let </span><span class="kw-2">mut </span>sm = SlotMap::new();
|
||
<span class="kw">let </span>foo = sm.insert(<span class="string">"foo"</span>); <span class="comment">// Key generated on insert.
|
||
</span><span class="kw">let </span>bar = sm.insert(<span class="string">"bar"</span>);
|
||
<span class="macro">assert_eq!</span>(sm[foo], <span class="string">"foo"</span>);
|
||
<span class="macro">assert_eq!</span>(sm[bar], <span class="string">"bar"</span>);
|
||
|
||
sm.remove(bar);
|
||
<span class="kw">let </span>reuse = sm.insert(<span class="string">"reuse"</span>); <span class="comment">// Space from bar reused.
|
||
</span><span class="macro">assert_eq!</span>(sm.contains_key(bar), <span class="bool-val">false</span>); <span class="comment">// After deletion a key stays invalid.
|
||
|
||
</span><span class="kw">let </span><span class="kw-2">mut </span>sec = SecondaryMap::new();
|
||
sec.insert(foo, <span class="string">"noun"</span>); <span class="comment">// We provide the key for secondary maps.
|
||
</span>sec.insert(reuse, <span class="string">"verb"</span>);
|
||
|
||
<span class="kw">for </span>(key, val) <span class="kw">in </span>sm {
|
||
<span class="macro">println!</span>(<span class="string">"{} is a {}"</span>, val, sec[key]);
|
||
}</code></pre></div>
|
||
<h2 id="serialization-through-serde-no_std-support-and-unstable-features"><a class="doc-anchor" href="#serialization-through-serde-no_std-support-and-unstable-features">§</a>Serialization through <a href="https://github.com/serde-rs/serde"><code>serde</code></a>, <a href="https://doc.rust-lang.org/1.7.0/book/no-stdlib.html"><code>no_std</code></a> support and unstable features</h2>
|
||
<p>Both keys and the slot maps have full (de)seralization support through
|
||
the <a href="https://github.com/serde-rs/serde"><code>serde</code></a> library. A key remains valid for a slot map even after one or
|
||
both have been serialized and deserialized! This makes storing or
|
||
transferring complicated referential structures and graphs a breeze. Care has
|
||
been taken such that deserializing keys and slot maps from untrusted sources
|
||
is safe. If you wish to use these features you must enable the <code>serde</code>
|
||
feature flag for <code>slotmap</code> in your <code>Cargo.toml</code>.</p>
|
||
<div class="example-wrap"><pre class="language-text"><code>slotmap = { version = "1.0", features = ["serde"] }</code></pre></div>
|
||
<p>This crate also supports <a href="https://doc.rust-lang.org/1.7.0/book/no-stdlib.html"><code>no_std</code></a> environments, but does require the
|
||
<a href="https://doc.rust-lang.org/1.84.0/alloc/index.html" title="mod alloc"><code>alloc</code></a> crate to be available. To enable this you have to disable the
|
||
<code>std</code> feature that is enabled by default:</p>
|
||
<div class="example-wrap"><pre class="language-text"><code>slotmap = { version = "1.0", default-features = false }</code></pre></div>
|
||
<p>Unfortunately <a href="struct.SparseSecondaryMap.html" title="struct slotmap::SparseSecondaryMap"><code>SparseSecondaryMap</code></a> is not available in <a href="https://doc.rust-lang.org/1.7.0/book/no-stdlib.html"><code>no_std</code></a>, because
|
||
it relies on <a href="https://doc.rust-lang.org/1.84.0/std/collections/hash/map/struct.HashMap.html" title="struct std::collections::hash::map::HashMap"><code>HashMap</code></a>. Finally the <code>unstable</code> feature can be defined to
|
||
enable the parts of <code>slotmap</code> that only work on nightly Rust.</p>
|
||
<h2 id="why-not-index-a-vec-or-use-slab-stable-vec-etc"><a class="doc-anchor" href="#why-not-index-a-vec-or-use-slab-stable-vec-etc">§</a>Why not index a <a href="https://doc.rust-lang.org/1.84.0/alloc/vec/struct.Vec.html" title="struct alloc::vec::Vec"><code>Vec</code></a>, or use <a href="https://crates.io/crates/slab"><code>slab</code></a>, <a href="https://crates.io/crates/stable-vec"><code>stable-vec</code></a>, etc?</h2>
|
||
<p>Those solutions either can not reclaim memory from deleted elements or
|
||
suffer from the ABA problem. The keys returned by <code>slotmap</code> are versioned.
|
||
This means that once a key is removed, it stays removed, even if the
|
||
physical storage inside the slotmap is reused for new elements. The key is a
|
||
permanently unique<sup>*</sup> reference to the inserted value. Despite
|
||
supporting versioning, a <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> is often not (much) slower than the
|
||
alternative, by internally using carefully checked unsafe code. Finally,
|
||
<code>slotmap</code> simply has a lot of features that make your life easy.</p>
|
||
<h2 id="performance-characteristics-and-implementation-details"><a class="doc-anchor" href="#performance-characteristics-and-implementation-details">§</a>Performance characteristics and implementation details</h2>
|
||
<p>Insertion, access and deletion is all O(1) with low overhead by storing the
|
||
elements inside a <a href="https://doc.rust-lang.org/1.84.0/alloc/vec/struct.Vec.html" title="struct alloc::vec::Vec"><code>Vec</code></a>. Unlike references or indices into a vector,
|
||
unless you remove a key it is never invalidated. Behind the scenes each
|
||
slot in the vector is a <code>(value, version)</code> tuple. After insertion the
|
||
returned key also contains a version. Only when the stored version and
|
||
version in a key match is a key valid. This allows us to reuse space in the
|
||
vector after deletion without letting removed keys point to spurious new
|
||
elements. <sup>*</sup>After 2<sup>31</sup> deletions and insertions to the
|
||
same underlying slot the version wraps around and such a spurious reference
|
||
could potentially occur. It is incredibly unlikely however, and in all
|
||
circumstances is the behavior safe. A slot map can hold up to
|
||
2<sup>32</sup> - 2 elements at a time.</p>
|
||
<p>The memory usage for each slot in <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> is <code>4 + max(sizeof(T), 4)</code>
|
||
rounded up to the alignment of <code>T</code>. Similarly it is <code>4 + max(sizeof(T), 12)</code>
|
||
for <a href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap"><code>HopSlotMap</code></a>. <a href="struct.DenseSlotMap.html" title="struct slotmap::DenseSlotMap"><code>DenseSlotMap</code></a> has an overhead of 8 bytes per element
|
||
and 8 bytes per slot.</p>
|
||
<h2 id="choosing-slotmap-hopslotmap-or-denseslotmap"><a class="doc-anchor" href="#choosing-slotmap-hopslotmap-or-denseslotmap">§</a>Choosing <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a>, <a href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap"><code>HopSlotMap</code></a> or <a href="struct.DenseSlotMap.html" title="struct slotmap::DenseSlotMap"><code>DenseSlotMap</code></a></h2>
|
||
<p>A <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> is the fastest for most operations, except iteration. It can
|
||
never shrink the size of its underlying storage, because it must remember
|
||
for each storage slot what the latest stored version was, even if the slot
|
||
is empty now. This means that iteration can be slow as it must iterate over
|
||
potentially a lot of empty slots.</p>
|
||
<p><a href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap"><code>HopSlotMap</code></a> solves this by maintaining more information on
|
||
insertion/removal, allowing it to iterate only over filled slots by ‘hopping
|
||
over’ contiguous blocks of vacant slots. This can give it significantly
|
||
better iteration speed. If you expect to iterate over all elements in a
|
||
<a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> a lot, and potentially have a lot of deleted elements, choose
|
||
<a href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap"><code>HopSlotMap</code></a>. The downside is that insertion and removal is roughly twice
|
||
as slow. Random access is the same speed for both.</p>
|
||
<p><a href="struct.DenseSlotMap.html" title="struct slotmap::DenseSlotMap"><code>DenseSlotMap</code></a> goes even further and stores all elements on a contiguous
|
||
block of memory. It uses two indirections per random access; the slots
|
||
contain indices used to access the contiguous memory. This means random
|
||
access is slower than both <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> and <a href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap"><code>HopSlotMap</code></a>, but iteration is
|
||
significantly faster, as fast as a normal <a href="https://doc.rust-lang.org/1.84.0/alloc/vec/struct.Vec.html" title="struct alloc::vec::Vec"><code>Vec</code></a>.</p>
|
||
<h2 id="choosing-secondarymap-or-sparsesecondarymap"><a class="doc-anchor" href="#choosing-secondarymap-or-sparsesecondarymap">§</a>Choosing <a href="struct.SecondaryMap.html" title="struct slotmap::SecondaryMap"><code>SecondaryMap</code></a> or <a href="struct.SparseSecondaryMap.html" title="struct slotmap::SparseSecondaryMap"><code>SparseSecondaryMap</code></a></h2>
|
||
<p>You want to associate extra data with objects stored in a slot map, so you
|
||
use (multiple) secondary maps to map keys to that data.</p>
|
||
<p>A <a href="struct.SecondaryMap.html" title="struct slotmap::SecondaryMap"><code>SecondaryMap</code></a> is simply a <a href="https://doc.rust-lang.org/1.84.0/alloc/vec/struct.Vec.html" title="struct alloc::vec::Vec"><code>Vec</code></a> of slots like slot map is, and
|
||
essentially provides all the same guarantees as <a href="struct.SlotMap.html" title="struct slotmap::SlotMap"><code>SlotMap</code></a> does for its
|
||
operations (with the exception that you provide the keys as produced by the
|
||
primary slot map). This does mean that even if you associate data to only
|
||
a single element from the primary slot map, you could need and have to
|
||
initialize as much memory as the original.</p>
|
||
<p>A <a href="struct.SparseSecondaryMap.html" title="struct slotmap::SparseSecondaryMap"><code>SparseSecondaryMap</code></a> is like a <a href="https://doc.rust-lang.org/1.84.0/std/collections/hash/map/struct.HashMap.html" title="struct std::collections::hash::map::HashMap"><code>HashMap</code></a> from keys to objects, however
|
||
it automatically removes outdated keys for slots that had their space
|
||
reused. You should use this variant if you expect to store some associated
|
||
data for only a small portion of the primary slot map.</p>
|
||
<h2 id="custom-key-types"><a class="doc-anchor" href="#custom-key-types">§</a>Custom key types</h2>
|
||
<p>If you have multiple slot maps it’s an error to use the key of one slot map
|
||
on another slot map. The result is safe, but unspecified, and can not be
|
||
detected at runtime, so it can lead to a hard to find bug.</p>
|
||
<p>To prevent this, slot maps allow you to specify what the type is of the key
|
||
they return. You can construct new key types using the <a href="macro.new_key_type.html" title="macro slotmap::new_key_type"><code>new_key_type!</code></a>
|
||
macro. The resulting type behaves exactly like <a href="struct.DefaultKey.html" title="struct slotmap::DefaultKey"><code>DefaultKey</code></a>, but is a
|
||
distinct type. So instead of simply using <code>SlotMap<DefaultKey, Player></code> you
|
||
would use:</p>
|
||
|
||
<div class="example-wrap"><pre class="rust rust-example-rendered"><code><span class="macro">new_key_type!</span> { <span class="kw">struct </span>PlayerKey; }
|
||
<span class="kw">let </span>sm: SlotMap<PlayerKey, Player> = SlotMap::with_key();</code></pre></div>
|
||
<p>You can write code generic over any key type using the <a href="trait.Key.html" title="trait slotmap::Key"><code>Key</code></a> trait.</p>
|
||
</div></details><h2 id="modules" class="section-header">Modules<a href="#modules" class="anchor">§</a></h2><ul class="item-table"><li><div class="item-name"><a class="mod" href="basic/index.html" title="mod slotmap::basic">basic</a></div><div class="desc docblock-short">Contains the slot map implementation.</div></li><li><div class="item-name"><a class="mod" href="dense/index.html" title="mod slotmap::dense">dense</a></div><div class="desc docblock-short">Contains the dense slot map implementation.</div></li><li><div class="item-name"><a class="mod" href="hop/index.html" title="mod slotmap::hop">hop</a></div><div class="desc docblock-short">Contains the faster iteration, slower insertion/removal slot map
|
||
implementation.</div></li><li><div class="item-name"><a class="mod" href="secondary/index.html" title="mod slotmap::secondary">secondary</a></div><div class="desc docblock-short">Contains the secondary map implementation.</div></li><li><div class="item-name"><a class="mod" href="sparse_secondary/index.html" title="mod slotmap::sparse_secondary">sparse_<wbr>secondary</a></div><div class="desc docblock-short">Contains the sparse secondary map implementation.</div></li></ul><h2 id="macros" class="section-header">Macros<a href="#macros" class="anchor">§</a></h2><ul class="item-table"><li><div class="item-name"><a class="macro" href="macro.new_key_type.html" title="macro slotmap::new_key_type">new_<wbr>key_<wbr>type</a></div><div class="desc docblock-short">A helper macro to create new key types. If you use a new key type for each
|
||
slot map you create you can entirely prevent using the wrong key on the
|
||
wrong slot map.</div></li></ul><h2 id="structs" class="section-header">Structs<a href="#structs" class="anchor">§</a></h2><ul class="item-table"><li><div class="item-name"><a class="struct" href="struct.DefaultKey.html" title="struct slotmap::DefaultKey">Default<wbr>Key</a></div><div class="desc docblock-short">The default slot map key type.</div></li><li><div class="item-name"><a class="struct" href="struct.DenseSlotMap.html" title="struct slotmap::DenseSlotMap">Dense<wbr>Slot<wbr>Map</a></div><div class="desc docblock-short">Dense slot map, storage with stable unique keys.</div></li><li><div class="item-name"><a class="struct" href="struct.HopSlotMap.html" title="struct slotmap::HopSlotMap">HopSlot<wbr>Map</a></div><div class="desc docblock-short">Hop slot map, storage with stable unique keys.</div></li><li><div class="item-name"><a class="struct" href="struct.KeyData.html" title="struct slotmap::KeyData">KeyData</a></div><div class="desc docblock-short">The actual data stored in a <a href="trait.Key.html" title="trait slotmap::Key"><code>Key</code></a>.</div></li><li><div class="item-name"><a class="struct" href="struct.SecondaryMap.html" title="struct slotmap::SecondaryMap">Secondary<wbr>Map</a></div><div class="desc docblock-short">Secondary map, associate data with previously stored elements in a slot map.</div></li><li><div class="item-name"><a class="struct" href="struct.SlotMap.html" title="struct slotmap::SlotMap">SlotMap</a></div><div class="desc docblock-short">Slot map, storage with stable unique keys.</div></li><li><div class="item-name"><a class="struct" href="struct.SparseSecondaryMap.html" title="struct slotmap::SparseSecondaryMap">Sparse<wbr>Secondary<wbr>Map</a></div><div class="desc docblock-short">Sparse secondary map, associate data with previously stored elements in a
|
||
slot map.</div></li></ul><h2 id="traits" class="section-header">Traits<a href="#traits" class="anchor">§</a></h2><ul class="item-table"><li><div class="item-name"><a class="trait" href="trait.Key.html" title="trait slotmap::Key">Key</a></div><div class="desc docblock-short">Key used to access stored values in a slot map.</div></li></ul></section></div></main></body></html> |