[Boost-commit] svn:boost r46883 - sandbox/committee/concepts/stdlib

From: dgregor_at_[hidden]
Date: 2008-06-30 00:50:39

Author: dgregor
Date: 2008-06-30 00:50:38 EDT (Mon, 30 Jun 2008)
New Revision: 46883
URL: http://svn.boost.org/trac/boost/changeset/46883

Log:
Eliminate informal requirements in the container requirements tables that are better specified in the containers themselves
Text files modified: 
   sandbox/committee/concepts/stdlib/clib-containers.tex |   561 +++++++++++++++++++++++++++++++++++++++ 
   1 files changed, 560 insertions(+), 1 deletions(-)

Modified: sandbox/committee/concepts/stdlib/clib-containers.tex
==============================================================================
--- sandbox/committee/concepts/stdlib/clib-containers.tex	(original)
+++ sandbox/committee/concepts/stdlib/clib-containers.tex	2008-06-30 00:50:38 EDT (Mon, 30 Jun 2008)
@@ -34,6 +34,8 @@
 \setlength{\evensidemargin}{0pt}
 \setlength{\textwidth}{6.6in}
 
+\newcommand{\resetcolor}{\textcolor{addclr}{}}
+
 %%--------------------------------------------------
 %% Handle special hyphenation rules
 \hyphenation{tem-plate ex-am-ple in-put-it-er-a-tor}
@@ -139,7 +141,12 @@
   container's value type for the same operation. Those container
   concepts that are actually needed (e.g., for the container
   adaptors~\ref{container.adaptors}) are specified in the new
-  section~\ref{container.concepts}.}
+  section~\ref{container.concepts}. We have, however, removed many
+  informal ``requires'' clauses from the container requirements
+  tables, because they have never been complete and the same
+  information is available more formally in the real requires clauses
+  of the containers themselves (which appropriately account for the
+  variation between containers).}
 
 \setcounter{Paras}{2}
 \pnum
@@ -181,6 +188,239 @@
 \editorial{Remove Table 88: \mbox{\tcode{ConstructibleAsElement<A, T,
       Args>}} requirements}
 
+\setcounter{Paras}{4}
+\pnum
+In Tables~\ref{tab:containers.container.requirements} and
+\ref{tab:containers.reversible.requirements}, \tcode{X}\
+denotes a container class containing objects of type
+\tcode{T}, \tcode{a}\ and \tcode{b}
+denote values of type \tcode{X}, \tcode{u}\
+denotes an identifier, \tcode{r}\ denotes
+an lvalue or a const rvalue of type \tcode{X}, and \tcode{rv}
+denotes a non-const rvalue of type \tcode{X}.
+
+\setcounter{table}{88}
+
+\begin{libreqtab5}
+{Container requirements}
+{tab:containers.container.requirements}
+\\ \topline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{operational}  &
+\chdr{assertion/note}   &   \rhdr{complexity}   \\
+    &   &   \chdr{semantics}    &   \chdr{pre/post-condition}   &       \\ \capsep
+\endfirsthead
+\topline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{operational}  &
+\chdr{assertion/note}   &   \rhdr{complexity}   \\
+    &   &   \chdr{semantics}    &   \chdr{pre/post-condition}   &       \\ \capsep
+\endhead
+
+\tcode{X::value_type}       &
+ \tcode{T}                  &
+                            &
+                            &
+ compile time               \\ \rowsep
+
+\tcode{X::reference}        &
+ lvalue of \tcode{T}        &
+                            &
+                            &
+ compile time               \\ \rowsep
+
+\tcode{X::const_reference} &
+ const lvalue of \tcode{T}  &
+                            &
+                            &
+ compile time               \\ \rowsep
+
+\tcode{X::iterator}         &
+ iterator type whose value type is \tcode{T} &
+                            &
+ any iterator category except output iterator.
+ convertible to \tcode{X::const_iterator}. &
+ compile time               \\ \rowsep
+
+\tcode{X::const_iterator}  &   
+ constant iterator type whose value type is \tcode{T} &
+                            &
+ any iterator category except output iterator &
+ compile time               \\ \rowsep
+
+\tcode{X::dif\-ference_type}   &
+ signed integral type           &
+                                &
+ is identical to the difference type of \tcode{X::iterator}\ and \tcode{X::const_iterator} &
+ compile time               \\ \rowsep
+
+\tcode{X::size_type}       &
+ unsigned integral type     &
+                            &
+ \tcode{size_type} can represent any non-negative value of \tcode{difference_type} &
+ compile time                \\ \rowsep
+
+\tcode{X u;}                &
+                            &
+                            &
+ post: \tcode{u.size() == 0}&
+ constant                   \\ \rowsep
+
+\tcode{X();}                &
+                            &
+                            &
+ \tcode{X().size() == 0}    &
+ constant                   \\ \rowsep
+
+\tcode{X(a);}               &
+                            &
+                            &
+\removedCCC{\mbox{\requires} \mbox{\tcode{T}} is \mbox{\tcode{CopyConstructible}}.} post: \tcode{a == X(a)}.         &
+ linear                     \\ \rowsep
+
+\tcode{X u(a);}             &
+                            &
+                            &
+\removedCCC{\mbox{\requires} \mbox{\tcode{T}} is \mbox{\tcode{CopyConstructible}}.}       &
+ linear                     \\
+\tcode{X u = a;}            &
+                            &
+                            &
+ post: \tcode{u == a}       &
+                            \\ \rowsep
+
+\tcode{X u(rv);} &
+                            &
+                            &
+	\removedCCC{\mbox{\requires} \mbox{\tcode{T}} is \mbox{\tcode{MoveConstructible}}.}													&
+(Note B)           \\
+\tcode{X u = rv;} &
+                            &
+                            &
+ post: \tcode{u} shall be equal to the value that \tcode{rv} had before this construction   
+                            &
+                            \\ \rowsep
+
+\tcode{a = rv;} &
+\tcode{X\&} &
+All existing elements of \tcode{a} are either move assigned or destroyed                  &
+\tcode{a} shall be equal to the value that \tcode{rv}
+had before this construction   &
+ (Note C)           \\ \rowsep
+\tcode{(\&a)->$\sim$X();}   &
+ \tcode{void}               &
+                            &
+ note: the destructor is applied to every element of \tcode{a}; all the memory is deallocated. &
+ linear                     \\ \rowsep
+
+\tcode{a.begin();}          &
+ \tcode{iterator}; \tcode{const_iterator}\ for constant \tcode{a} &
+                            &
+                            &
+ constant                   \\ \rowsep
+
+\tcode{a.end();}            &
+ \tcode{iterator}; \tcode{const_iterator}\ for constant \tcode{a} &
+                            &
+                            &
+ constant                   \\ \rowsep
+
+\tcode{a.cbegin();}         &
+ \tcode{const_iterator}     &
+ \tcode{const_cast<X const\&>(a).begin();} &
+                            &
+ constant                   \\ \rowsep
+
+\tcode{a.cend();}         &
+ \tcode{const_iterator}     &
+ \tcode{const_cast<X const\&>(a).end();} &
+                            &
+ constant                   \\ \rowsep
+
+\tcode{a == b}                  &
+ convertible to \tcode{bool}    &
+                                &
+ \tcode{==}\ is an equivalence relation.
+ \tcode{a.size() == b.size()}
+ \tcode{\&\& equal(a.begin(),}
+ \tcode{a.end(), b.begin())}     &
+ linear                         \\ \rowsep
+
+\tcode{a != b}                      &
+ convertible to \tcode{bool}        &
+                                    &
+ Equivalent to: \tcode{!(a == b)}   &
+ linear                             \\ \rowsep
+
+\tcode{a.swap(b)};          &
+ \tcode{void}               &
+                            &
+ \tcode{swap(a,b)}          &
+ (Note A)                   \\ \rowsep
+
+\tcode{r = a}               &
+ \tcode{X\&}                &
+                            &
+ post: \tcode{r == a}.      &
+ linear                     \\ \rowsep
+
+\tcode{a.size()}                &
+ \tcode{size_type}             &
+ \tcode{a.end() $-$ a.begin()}  &
+                                &
+ (Note A)                       \\ \rowsep
+
+\tcode{a.max_size()}        &
+ \tcode{size_type}         &
+ \tcode{size()}\ of the largest possible container &
+                            &
+ (Note A)                   \\ \rowsep
+
+\tcode{a.empty()}               &
+ convertible to \tcode{bool}    &
+ \tcode{a.size() == 0}          &
+                                &
+constant                        \\ \rowsep
+
+\resetcolor{}\tcode{a < b}                   &
+ convertible to \tcode{bool}    &
+ \tcode{lexico\-graphical_compare( a.begin(), a.end(), b.begin(), b.end())} &
+ pre: \tcode{<}\ is defined for values of \tcode{T}. \tcode{<} is a total ordering relationship.    &
+ linear                     \\ \rowsep
+
+\tcode{a > b}                   &
+ convertible to \tcode{bool}    &
+ \tcode{b < a}                  &
+                                &
+ linear                         \\ \rowsep
+
+\tcode{a <= b}                  &
+ convertible to \tcode{bool}    &
+ \tcode{!(a > b)}               &
+                                &
+ linear                         \\ \rowsep
+
+\tcode{a >= b}                  &
+ convertible to \tcode{bool}    &
+ \tcode{!(a < b)}               &
+                                &
+ linear                         \\
+\end{libreqtab5}
+
+Notes: the algorithms
+\tcode{swap()},
+\tcode{equal()}\
+and
+\tcode{lexicographical_compare()}\
+are defined in clause~\ref{algorithms}.
+Those entries marked ``(Note A)'' should have constant complexity.
+Those entries marked ``(Note B)'' have constant complexity unless
+\changedCCC{\mbox{\tcode{allocator_propagate_never<X::allocator_type>::value}}
+  is \mbox{\tcode{true}}}{\mbox{\tcode{AllocatorPropagateNever<X::allocator_type>}} is satisfied}, in which case they have linear complexity. Those
+  entries marked ``(Note C)'' have constant complexity if
+  \tcode{a.get_allocator() == rv.get_allocator()} or if either
+  \changedCCC{\mbox{\tcode{allocator_propagate_on_move_assignment<X::allocator_type>::value}}
+  is \mbox{\tcode{true}}}{\mbox{\tcode{AllocatorPropagateOnMoveAssignment<X::allocator>}} is satisfied} or \changedCCC{\mbox{\tcode{allocator_propagate_on_copy_assignment<X::allocator_type>::value}} is
+  \mbox{\tcode{true}}}{\mbox{\tcode{AllocatorPropagateOnCopyAssignment<X::allocator>}} is satisfied} and linear complexity otherwise.
+
 \setcounter{Paras}{8}
 \pnum
 Copy and move constructors for all container types defined in this
@@ -205,6 +445,325 @@
 \tcode{get_allocator()} returns a copy of the \tcode{Allocator} object
 used to construct the container, or to replace the allocator. 
 
+\rSec2[sequence.reqmts]{Sequence containers}
+\setcounter{Paras}{3}
+\pnum
+The complexities of the expressions are sequence dependent.
+
+\setcounter{table}{91}
+
+\begin{libreqtab3}
+{Sequence container requirements (in addition to container)}
+{tab:containers.sequence.requirements}
+\\ \topline
+\lhdr{expression}       &   \chdr{return type}  &   \rhdr{assertion/note}       \\
+                        &                       &   \rhdr{pre/post-condition}   \\ \capsep
+\endfirsthead
+\hline
+\lhdr{expression}       &   \chdr{return type}  &   \rhdr{assertion/note}       \\
+                        &                       &   \rhdr{pre/post-condition}   \\ \capsep
+\endhead
+\tcode{X(n, t)}\br
+\tcode{X a(n, t)}   &
+                &
+ \removedCC{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}.}\br
+ post: \tcode{size() == n}\br
+ Constructs a sequence container with \tcode{n}\ copies of \tcode{t}  \\ \rowsep
+\tcode{X(i, j)}\br
+\tcode{X a(i, j)}   &
+                    &
+\mbox{\requires} \removedCC{If the iterator's dereference operation returns an
+ lvalue or a const rvalue, \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}.}
+ Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br
+ post: \tcode{size() == distance}\ between \tcode{i}\ and \tcode{j}\br
+ Constructs a sequence container equal to the range \tcode{[i, j)}    \\ \rowsep
+
+\tcode{a.emplace(p, args);}  &
+ \tcode{iterator}            &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{T, Args>}}.}
+ Inserts an object of type \tcode{T} constructed with
+ \tcode{std::forward<Args>(args)...}.   \\ \rowsep
+
+\tcode{a.insert(p,t)}   &
+ \tcode{iterator}       &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{T, Args>}}
+ and \mbox{\tcode{T}} shall be \mbox{\tcode{CopyAssignable}}.}\br
+ Inserts a copy of \tcode{t}\ before \tcode{p}. \\ \rowsep
+
+\tcode{a.insert(p,rv)}   &
+ \tcode{iterator}       &
+\removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{T, T\&\&>}} and \mbox{\tcode{T}} shall be \mbox{\tcode{MoveAssignable}}.}
+ Inserts a copy of \tcode{rv} before \tcode{p}. \\ \rowsep
+
+\tcode{a.insert(p,n,t)}     &
+ \tcode{void}               &
+ \removedCC{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}
+ and \mbox{\tcode{CopyAssignable}}.}\br
+ Inserts \tcode{n}\ copies of \tcode{t}\ before \tcode{p}. \\ \rowsep
+
+\tcode{a.insert(p,i,j)}    &
+ \tcode{void}           &
+\mbox{\requires}  \removedCC{If the iterator's dereference operation returns an
+ lvalue or a const rvalue, \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}.}
+ Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br
+ pre: \tcode{i}\ and \tcode{j}\ are not iterators into \tcode{a}.\br
+ Inserts copies of elements in \tcode{[i, j)} before \tcode{p}  \\ \rowsep
+
+\tcode{a.erase(q)}  &
+ \tcode{iterator}   &
+ \removedCC{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{MoveAssignable}}.}
+ Erases the element pointed to by \tcode{q} \\ \rowsep
+
+\tcode{a.erase(q1,q2)}  &
+ \tcode{iterator}   &
+ \removedCC{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{MoveAssignable}}.}
+ Erases the elements in the range \tcode{[q1, q2)}.  \\ \rowsep
+
+\tcode{a.clear()}   &
+ \tcode{void}       &
+ \tcode{erase(begin(), end())}\br
+ post: \tcode{size() == 0}      \\ \rowsep
+
+\tcode{a.assign(i,j)}   &
+ \tcode{void}           &
+ \requires \removedCC{If the iterator's dereference operation returns an
+ lvalue or a const rvalue, \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}
+ and \mbox{\tcode{CopyAssignable}}.}
+ Each iterator in the range \range{i}{j} shall be dereferenced exactly once.\br
+ pre: \tcode{i}, \tcode{j}\ are not iterators into \tcode{a}.\br
+ Replaces elements in \tcode{a}\ with a copy of \tcode{[i, j)}. \\ \rowsep
+
+\tcode{a.assign(n,t)}   &
+ \tcode{void}           &
+ \removedCC{\mbox{\requires} \mbox{\tcode{T}} shall be \mbox{\tcode{CopyConstructible}}
+ and \mbox{\tcode{CopyAssignable}}.}\br
+ pre: \tcode{t}\ is not a reference into \tcode{a}.\br
+ Replaces elements in \tcode{a}\ with \tcode{n}\ copies of \tcode{t}.   \\
+\end{libreqtab3}
+
+\setcounter{Paras}{11}
+
+\pnum
+Table~\ref{tab:containers.sequence.optional} lists operations
+that are provided for some types of
+sequence containers but not others.
+An implementation shall provide
+these operations for all container types shown in the ``container''
+column, and shall implement them so as to take amortized constant
+time.
+
+\begin{libreqtab4a}
+{Optional sequence container operations}
+{tab:containers.sequence.optional}
+\\ \topline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{assertion/note}       &   \rhdr{container}    \\
+                        &                       &   \chdr{pre/post-condition}   &                       \\ \capsep
+\endfirsthead
+\hline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{assertion/note}       &   \rhdr{container}    \\
+                        &                       &   \chdr{pre/post-condition}   &                       \\ \capsep
+\endhead
+
+\tcode{a.front()}       &
+ \tcode{reference; const_reference}\ for constant \tcode{a}    &
+ \tcode{*a.begin()}     &
+ \tcode{vector}, \tcode{list}, \tcode{deque}, \tcode{basic_string}\\ \rowsep
+
+\tcode{a.back()}        &
+ \tcode{reference; const_reference}\ for constant \tcode{a}    &
+ \tcode{\{ iterator tmp = a.end();}\br
+ \tcode{    \dcr tmp;}\br
+ \tcode{    return *tmp; \}}    &
+ \tcode{vector}, \tcode{list}, \tcode{deque}, \tcode{basic_string}\\ \rowsep
+
+\tcode{a.push_-} \tcode{front(args)}      &
+ \tcode{void}                &
+ \tcode{a.emplace(a.begin(),} \tcode{std::forward<Args>(args)...)}
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{T, Args>}}}    &
+ \tcode{list}, \tcode{deque}  \\ \rowsep
+
+\tcode{a.push_-} \tcode{back(args)}      &
+ \tcode{void}                &
+ \tcode{a.emplace(a.end(),} \tcode{std::forward<Args>(args)...)}
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{T, Args>}}}    &
+ \tcode{list}, \tcode{deque}, \tcode{vector}  \\ \rowsep
+
+\tcode{a.pop_front()}      &
+ \tcode{void}               &
+ \tcode{a.erase(a.begin())} &
+ \tcode{list}, \tcode{deque}    \\ \rowsep
+
+\tcode{a.pop_back()}       &
+ \tcode{void}               &
+ \tcode{\{ iterator tmp = a.end();}\br
+ \tcode{    \dcr tmp;}\br
+ \tcode{    a.erase(tmp); \}}   &
+ \tcode{vector}, \tcode{list}, \tcode{deque}, \tcode{basic_string}\\ \rowsep
+
+\tcode{a[n]}                &
+ \tcode{reference; const_reference}\ for constant \tcode{a}    &
+ \tcode{*(a.begin() + n)}   &
+ \tcode{vector}, \tcode{deque}, \tcode{basic_string}, \tcode{match_results}\\ \rowsep
+
+\tcode{a.at(n)}             &
+ \tcode{reference; const_reference}\ for constant \tcode{a}    &
+ \tcode{*(a.begin() + n)}   &
+ \tcode{vector}, \tcode{deque}      \\
+
+\end{libreqtab4a}
+
+\rSec2[associative.reqmts]{Associative containers}
+\setcounter{Paras}{6}
+
+\pnum
+In Table~\ref{tab:containers.associative.requirements},
+\tcode{X}\ denotes an associative container class,
+\tcode{a}\ denotes a value of \tcode{X},
+\tcode{a_uniq}\ denotes a value of \tcode{X}\
+when \tcode{X}\ supports unique keys,
+\tcode{a_eq}\ denotes a value of \tcode{X}\
+when \tcode{X}\ supports multiple keys,
+\tcode{u} denotes an identifier, \tcode{r} denotes an lvalue or a const rvalue of type \tcode{X}, \tcode{rv} denotes a non-const rvalue of type \tcode{X},
+\tcode{i}\ and \tcode{j}\
+satisfy input iterator requirements and refer to elements
+implicitly convertible to
+\tcode{value_type}, \range{i}{j}\
+denotes a valid range,
+\tcode{p}\ denotes a valid const iterator to \tcode{a},
+\tcode{q}\ denotes a valid dereferenceable const iterator to \tcode{a},
+\tcode{[q1, q2)}\ denotes a valid range of const iterators in \tcode{a},
+\tcode{t}\ denotes a value of \tcode{X::value_type},
+\tcode{k} denotes a value of \tcode{X::key_type}\
+and \tcode{c}\ denotes a value of type \tcode{X::key_compare}.
+\tcode{A} denotes the storage allocator used by \tcode{X}, if any, or \tcode{std::allocator<X::value_type>} otherwise, and \tcode{m} denotes an allocator of a type convertible to \tcode{A}.
+
+\begin{libreqtab4b}
+{Associative container requirements (in addition to container)}
+{tab:containers.associative.requirements}
+\\ \topline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{assertion/note}       &   \rhdr{complexity}   \\
+                        &                       &   \chdr{pre/post-condition}   &                       \\ \capsep
+\endfirsthead
+\hline
+\lhdr{expression}       &   \chdr{return type}  &   \chdr{assertion/note}       &   \rhdr{complexity}   \\
+                        &                       &   \chdr{pre/post-condition}   &                       \\ \capsep
+\endhead
+
+\tcode{X::key_type}    &
+ \tcode{Key}            &
+ \removedCC{\mbox{\tcode{Key}} is \mbox{\tcode{CopyConstructible}} and \mbox{\tcode{CopyAssignable}}}  &
+  compile time \\ \rowsep
+
+\tcode{X::key_compare} &   \tcode{Compare} &   defaults to 
+ \tcode{less<key_type>} &   compile time   \\ \rowsep
+
+\tcode{X::value_compare}           &
+ a binary predicate type           &
+ is the same as \tcode{key_compare}\ for \tcode{set}\ and
+ \tcode{multiset}; is an ordering relation on pairs induced by the
+ first component (\textit{i.e.} \tcode{Key}) for \tcode{map}\ and \tcode{multimap}. &
+ compile time                       \\ \rowsep
+
+\tcode{X(c)}\br
+\tcode{X a(c);}                         &
+                                        &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{key_compare, key_compare>}}.}
+ Constructs an empty container.\br
+ Uses a copy of \tcode{c} as a comparison object.  &
+ constant                               \\ \rowsep
+
+\tcode{X()}\br\tcode{X a;}                      &
+                                                &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{key_compare, key_compare>}}.}
+ Constructs an empty container.\br
+ Uses \tcode{Compare()} as a comparison object  &
+ constant                                       \\ \rowsep
+
+\tcode{X(i,j,c)}\br
+\tcode{X~a(i,j,c);}     &
+                        &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{key_compare, key_compare>}}.}
+ Constructs an empty container and inserts elements from the
+ range \tcode{[i, j)}\ into it; uses \tcode{c}\ as a comparison object. &
+ $N \log N$ in general ($N$ is the distance from \tcode{i}\ to \tcode{j});
+ linear if \tcode{[i, j)}\ is sorted with \tcode{value_comp()} \\ \rowsep
+
+\tcode{X(i,j)} \tcode{X~a(i,j);}    &
+                                    &
+ \removedCC{\mbox{\requires} \mbox{\tcode{ConstructibleAsElement<A,}} \mbox{\tcode{key_compare, key_compare>}}.}
+ Same as above, but uses \tcode{Compare()}\ as a comparison object  &
+ same as above                      \\ \rowsep
+
+\end{libreqtab4b}
+
+\rSec2[unord.req]{Unordered associative containers}
+\setcounter{Paras}{8}
+\setcounter{table}{95}
+\pnum
+\index{unordered associative containers}%
+\index{unordered associative containers!requirements}%
+\index{requirements!Unordered Associative Container}%
+\index{unordered associative containers!unique keys}%
+\index{unordered associative containers!equivalent keys}%
+\index{requirements!Container}%
+In table~\ref{tab:HashRequirements}: 
+\tcode{X} is an unordered associative container class, \tcode{a} is an
+object of type \tcode{X}, \tcode{b} is a possibly const object of
+type \tcode{X}, \tcode{a_uniq} is an object of type \tcode{X}
+when \tcode{X} supports unique keys, \tcode{a_eq} is an object of
+type \tcode{X} when \tcode{X} supports equivalent keys, \tcode{i}
+and \tcode{j} are input iterators that refer
+to \tcode{value_type}, \tcode{[i, j)} is a valid range,
+\tcode{p} and \tcode{q2} are valid const iterators to \tcode{a},
+\tcode{q} and \tcode{q1} are valid dereferenceable const iterators to \tcode{a},
+\tcode{[q1, q2)} is a valid range in \tcode{a},
+\tcode{t} is a value of
+type \tcode{X::value_type}, \tcode{k} is a value of
+type \tcode{key_type}, \tcode{hf} is a possibly const value of
+type \tcode{hasher}, \tcode{eq} is a possibly const value of
+type \tcode{key_equal}, \tcode{n} is a value of
+type \tcode{size_type}, and \tcode{z} is a value of
+type \tcode{float}. 
+
+\begin{libreqtab4d}
+  {Unordered associative container requirements (in addition to container)}
+  {tab:HashRequirements}
+\\ \topline
+\lhdr{expression} & \chdr{return type}
+& \chdr{assertion/note pre/post-condition}
+& \rhdr{complexity} \\ \capsep
+\endfirsthead
+\hline
+\lhdr{expression} & \chdr{return type} & \chdr{assertion/note pre/post-condition} & \rhdr{complexity} \\ \capsep
+\endhead
+%%
+\tcode{X::key_type}
+&   \tcode{Key}
+&   \removedCC{\mbox{\tcode{Key}} shall be \mbox{\tcode{CopyAssignable}} and \mbox{\tcode{CopyConstructible}}}
+    \index{unordered associative containers!key_type@\tcode{key_type}}%
+    \index{key_type@\tcode{key_type}!unordered associative containers}%
+&   compile time
+\\ \rowsep
+%
+\tcode{X::hasher}
+&   \tcode{Hash}
+&   \removedCC{\mbox{\tcode{Hash}} shall be a unary function object type such that the expression 
+    \mbox{\tcode{hf(k)}} has type \mbox{\tcode{std::size_t}}.}
+    \index{unordered associative containers!hasher@\tcode{hasher}}%
+    \index{hasher@\tcode{hasher}!unordered associative containers}%
+&   compile time
+\\ \rowsep
+%
+\tcode{X::key_equal}
+&   \tcode{Pred}
+&   \removedCC{\mbox{\tcode{Pred}} shall be a binary predicate that takes two arguments
+    of type \mbox{\tcode{Key}}.}  \tcode{Pred} is an equivalence relation.%
+    \index{unordered associative containers!key_equal@\tcode{key_equal}}%
+    \index{key_equal@\tcode{key_equal}!unordered associative containers}%
+&   compile time
+\\ \rowsep
+\end{libreqtab4d}
+
 \editorial{Add the following new section [container.concepts]}
 \color{addclr}
 \rSec2[container.concepts]{Container concepts}