diff options
| author | Tyge Løvset <[email protected]> | 2021-04-16 16:14:25 +0200 |
|---|---|---|
| committer | Tyge Løvset <[email protected]> | 2021-04-16 16:14:25 +0200 |
| commit | 6cbbac922e43e50bd29d72ea74df20c2ebe8ceba (patch) | |
| tree | b2b74a13e2a0e7b65079331953b5057375853bf9 /docs | |
| parent | 25df7b52622b62a167d5fe7d50b7aa9e075ad814 (diff) | |
| download | STC-modified-6cbbac922e43e50bd29d72ea74df20c2ebe8ceba.tar.gz STC-modified-6cbbac922e43e50bd29d72ea74df20c2ebe8ceba.zip | |
Corrections in cmap.
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/cmap_api.md | 12 |
1 files changed, 8 insertions, 4 deletions
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  -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. |