Subject: [Boost-commit] svn:boost r74378 - trunk/libs/unordered/doc
Date: 2011-09-14 17:05:54
Date: 2011-09-14 17:05:53 EDT (Wed, 14 Sep 2011)
New Revision: 74378
Unordered: Remove more parts of rationale made unnecessary by C++11.
Text files modified:
trunk/libs/unordered/doc/rationale.qbk | 33 +++++++++++++--------------------
1 files changed, 13 insertions(+), 20 deletions(-)
--- trunk/libs/unordered/doc/rationale.qbk (original)
+++ trunk/libs/unordered/doc/rationale.qbk 2011-09-14 17:05:53 EDT (Wed, 14 Sep 2011)
@@ -44,6 +44,8 @@
So chained addressing is used.
+[/ (Removing for now as this is out of date)
For containers with unique keys I store the buckets in a single-linked list.
There are other possible data structures (such as a double-linked list)
that allow for some operations to be faster (such as erasing and iteration)
@@ -63,6 +65,17 @@
the first element points to the last) and can be quickly updated when elements
are inserted or erased. The main disadvantage of this approach is some hairy code
for erasing elements.
+[/ (Starting to write up new structure, might not be ready in time)
+The node used to be stored in a linked list for each bucket but that
+didn't meet the complexity requirements for C++11, so now the nodes
+are stored in one long single linked list. But there needs a way to get
+the bucket from the node, to do that a copy of the key's hash value is
+stored in the node. Another possibility would be to store a pointer to
+the bucket, or the bucket's index, but storing the hash value allows
+some operations to be faster.
[h2 Number of Buckets]
@@ -90,24 +103,4 @@
So, this implementation uses a prime number for the hash table size.
-[h2 Active Issues and Proposals]
-[h3 C++0x allocators]
-/TODO/: This is out of date.
-Recent drafts have included an overhaul of the allocators, but this was
-dependent on concepts which are no longer in the standard.
-attempts to respecify them without concepts. I'll try to implement this (or
-an appropriate later version) in a future version of boost, possibly changed
-a little to accomodate non-C++0x compilers.
-[h3 Are insert and erase stable for unordered_multiset and unordered_multimap?]
-It wan't specified if `unordered_multiset` and `unordered_multimap` preserve the order
-of elements with equivalent keys (i.e. if they're stable under `insert` and `erase`).
-n2691] it's been specified that they do and this implementation follows that.