From 6cbbac922e43e50bd29d72ea74df20c2ebe8ceba Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Fri, 16 Apr 2021 16:14:25 +0200 Subject: Corrections in cmap. --- docs/cmap_api.md | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'docs/cmap_api.md') diff --git a/docs/cmap_api.md b/docs/cmap_api.md index f43afa44..5e8d4d26 100644 --- a/docs/cmap_api.md +++ b/docs/cmap_api.md @@ -1,10 +1,14 @@ # STC [cmap](../stc/cmap.h): Unordered Map ![Map](pics/map.jpg) -A **cmap** is an associative container that contains key-value pairs with unique keys. Search, insertion, -and removal of elements have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as closed hashing (aka open addressing) with linear probing, and without leaving tombstones on erase. - -***Iterator invalidation***: References and iterators are invalidated after erase. No iterators are invalidated after insert. +A **cmap** is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements +have average constant-time complexity. Internally, the elements are not sorted in any particular order, but organized into +buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual +elements, since once the hash is computed, it refers to the exact bucket the element is placed into. It is implemented as closed +hashing (aka open addressing) with linear probing, and without leaving tombstones on erase. + +***Iterator invalidation***: References and iterators are invalidated after erase. No iterators are invalidated after insert, +unless the hash-table need to be extended. The hash table size can be reserved prior to inserts if the total max size is known. The order of elements is preserved after erase and insert. This makes it possible to erase individual elements while iterating through the container by using the returned iterator from *erase_it()*, which references the next element. -- cgit v1.2.3