From 4312e020f1419864e1c05ecb0e85b4876d01bd08 Mon Sep 17 00:00:00 2001 From: Benjamin Kosnik Date: Fri, 18 Jan 2008 08:16:51 +0000 Subject: [multiple changes] 2008-01-18 Benjamin Kosnik * docs/*: To... * doc/*: ...here. * testsuite/Makefile.am: Move doc-performance to... * Makefile.am: Add doc to SUBDIRS, move doxygen-* rules to... * doc/Makefile.am: Consolidate documentation creation here. (doc-doxygen-html): New. (doc-doxygen-man): New. (doc-performance): New. * doc/Makefile.in: New. * acinclude.m4 (glibcxx_SUBDIRS): Add doc directory. * doc/doxygen/guide.html: Edit for unified html configuration. * doc/doxygen/mainpage.html: Same. * doc/doxygen/run_doxygen: Same, more namespace fixups for man generation. * doc/doxygen/user.cfg.in: Update for doxygen 1.5.4. * include/tr1_impl/random: Remove maint from doxygen markup. * include/tr1_impl/functional: Same. * include/std/tuple: Same. * include/std/streambuf: Same. * include/std/bitset: Same. * include/std/limits: Same. * include/std/fstream: Same. * include/std/istream: Same. * include/std/sstream: Same. * include/ext/pool_allocator.h: Same. * include/ext/rc_string_base.h: Same. * include/bits/basic_ios.h: Same. * include/bits/stl_list.h: Same. * include/bits/stl_map.h: Same. * include/bits/locale_classes.h: Same. * include/bits/stl_set.h: Same. * include/bits/stl_iterator_base_types.h: Same. * include/bits/basic_string.h: Same. * include/bits/stl_multimap.h: Same. * include/bits/stl_vector.h: Same. * include/bits/ios_base.h: Same. * include/bits/stl_deque.h: Same. * include/bits/postypes.h: Same. * include/bits/stl_multiset.h: Same. * include/bits/stl_algo.h: Same. * include/bits/stl_iterator.h: Same. * include/bits/stl_tempbuf.h: Same. * include/bits/stl_construct.h: Same. * include/bits/stl_relops.h: Same. * include/tr1/tuple: Same. * include/backward/auto_ptr.h: Same. * testsuite/23_containers/vector/requirements/dr438/assign_neg.cc: Fixups for line number changes. * testsuite/23_containers/vector/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/vector/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/vector/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/assign_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/20_util/auto_ptr/assign_neg.cc: Same. * aclocal.m4: Regenerate. * config.h.in: Regenerate. * configure: Regenerate. * Makefile.in: Regenerate. * src/Makefile.in: Regenerate. * po/Makefile.in: Regenerate. * libmath/Makefile.in: Regenerate. * include/Makefile.in: Regenerate. * libsupc++/Makefile.in: Regenerate. * testsuite/Makefile.in: Regenerate. * scripts/make_graphs.py: Correct paths for new layout. 2008-01-17 Benjamin Kosnik * acinclude.m4 (AC_LC_MESSAGES): Remove serial. * linkage.m4 (AC_REPLACE_MATHFUNCS): Same. * configure: Regenerate. * aclocal.m4: Regenerate. From-SVN: r131625 --- libstdc++-v3/doc/doxygen/tables.html | 645 +++++++++++++++++++++++++++++++++++ 1 file changed, 645 insertions(+) create mode 100644 libstdc++-v3/doc/doxygen/tables.html (limited to 'libstdc++-v3/doc/doxygen/tables.html') diff --git a/libstdc++-v3/doc/doxygen/tables.html b/libstdc++-v3/doc/doxygen/tables.html new file mode 100644 index 0000000..74ac3e2 --- /dev/null +++ b/libstdc++-v3/doc/doxygen/tables.html @@ -0,0 +1,645 @@ + + + +Tables + + + + + +

Tables

+ +

Most of the requirements on containers are presented in the ISO standard + in the form of tables. In order to avoid massive duplication of effort + while documenting all the classes, we follow the standard's lead and + present the base information here. Individual classes will only document + their departures from these tables (removed functions, additional functions, + changes, etc). +

+ +

We will not try to duplicate all of the surrounding text (footnotes, + explanations, etc.) from the standard, because that would also entail a + duplication of effort. Some of the surrounding text has been paraphrased + here for clarity. If you are uncertain about the meaning or interpretation + of these notes, consult a good textbook, and/or purchase your own copy of + the standard (it's cheap, see our FAQ). +

+ +

The table numbers are the same as those used in the standard. Tables can + be jumped to using their number, e.g., "tables.html#67". Only + Tables 65 through 69 are presented. Some of the active Defect Reports + are also noted or incorporated. +

+ +
+ +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Table 65 --- Container Requirements

+Anything calling itself a container must meet these minimum requirements. +
expressionresult typeoperational semanticsnotes, pre-/post-conditions, assertionscomplexity
X::value_typeT T is Assignablecompile time
X::referencelvalue of T  compile time
X::const_referenceconst lvalue of T  compile time
X::iteratoriterator type pointing to T Any iterator category except output iterator. + Convertible to X::const_iterator.compile time
X::const_iteratoriterator type pointing to const T Any iterator category except output iterator.compile time
X::difference_typesigned integral type identical to the difference type of X::iterator and X::const_iteratorcompile time
X::size_typeunsigned integral type size_type can represent any non-negative value of difference_typecompile time
X u;  post: u.size() == 0constant
X();  X().size == 0constant
X(a);  a == X(a)linear
X u(a);
X u = a;		  post: u == a. Equivalent to: X u; u = a;linear
(&a)->~X();void dtor is applied to every element of a; all the memory is deallocatedlinear
a.begin()iterator; const_iterator for constant a  constant
a.end()iterator; const_iterator for constant a  constant
a == bconvertible to bool == is an equivalence relation. a.size()==b.size() && + equal(a.begin(),a.end(),b.begin())linear
a != bconvertible to bool equivalent to !(a==b)linear
a.swap(b)void swap(a,b)may or may not have constant complexity
r = aX& r == alinear
a.size()size_typea.end() - a.begin() may or may not have constant complexity
a.max_size()size_typesize() of the largest possible container may or may not have constant complexity
a.empty()convertible to boola.size() == 0 constant
a < bconvertible to boollexographical_compare( a.begin, a.end(), b.begin(), b.end())pre: < is defined for T and is a total ordering relationlinear
a > bconvertible to boolb < a linear
a <= bconvertible to bool!(a > b) linear
a >= bconvertible to bool!(a < b) linear

 + + +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Table 66 --- Reversible Container Requirements

+If a container's iterator is bidirectional or random-access, then the +container also meets these requirements. +Deque, list, vector, map, multimap, set, and multiset are such containers. +
expressionresult typenotes, pre-/post-conditions, assertionscomplexity
X::reverse_iteratoriterator type pointing to Treverse_iterator<iterator>compile time
X::const_reverse_iteratoriterator type pointing to const Treverse_iterator<const_iterator>compile time
a.rbegin()reverse_iterator; const_reverse_iterator for constant areverse_iterator(end())constant
a.rend()reverse_iterator; const_reverse_iterator for constant areverse_iterator(begin())constant

 + + +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Table 67 --- Sequence Requirements

+These are in addition to the requirements of containers. +Deque, list, and vector are such containers. +
expressionresult typenotes, pre-/post-conditions, assertions
X(n,t)
X a(n,t)		 constructs a sequence with n copies of t
post: size() == n
X(i,j)
X a(i,j)		 constructs a sequence equal to the range [i,j)
+ post: size() == distance(i,j)
a.insert(p,t)iterator (points to the inserted copy of t)inserts a copy of t before p
a.insert(p,n,t)voidinserts n copies of t before p
a.insert(p,i,j)voidinserts copies of elements in [i,j) before p
+ pre: i, j are not iterators into a
a.erase(q)iterator (points to the element following q (prior to erasure))erases the element pointed to by q
a.erase(q1,q1)iterator (points to the element pointed to by q2 (prior to erasure))erases the elements in the range [q1,q2)
a.clear()voiderase(begin(),end())
post: size() == 0

 + + +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Table 68 --- Optional Sequence Operations

+These operations are only included in containers when the operation can be +done in constant time. +
expressionresult typeoperational semanticscontainer
a.front()reference; const_reference for constant a*a.begin()vector, list, deque
a.back()reference; const_reference for constant a*--a.end()vector, list, deque
a.push_front(x)voida.insert(a.begin(),x)list, deque
a.push_back(x)voida.insert(a.end(),x)vector, list, deque
a.pop_front()voida.erase(a.begin())list, deque
a.pop_back()voida.erase(--a.end())vector, list, deque
a[n]reference; const_reference for constant a*(a.begin() + n)vector, deque
a.at(n)reference; const_reference for constant a*(a.begin() + n)
throws out_of_range if n>=a.size()		vector, deque

 + + +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +

Table 69 --- Associative Container Requirements

+These are in addition to the requirements of containers. +Map, multimap, set, and multiset are such containers. An associative +container supports unique keys (and is written as +a_uniq instead of a) if it may contain at most +one element for each key. Otherwise it supports equivalent keys +(and is written a_eq). Examples of the former are set and map, +examples of the latter are multiset and multimap. +
expressionresult typenotes, pre-/post-conditions, assertionscomplexity
X::key_typeKeyKey is Assignablecompile time
X::key_compareComparedefaults to less<key_type>compile time
X::value_comparea binary predicate typesame as key_compare for set and multiset; an ordering relation on + pairs induced by the first component (Key) for map and multimapcompile time
X(c)
X a(c)		 constructs an empty container which uses c as a comparison objectconstant
X()
X a		 constructs an empty container using Compare() as a comparison objectconstant
X(i,j,c)
X a(i,j,c)		 constructs an empty container and inserts elements from the range [i,j) + into it; uses c as a comparison objectNlogN in general where N is distance(i,j); linear if [i,j) is + sorted with value_comp()
X(i,j)
X a(i,j)		 same as previous, but uses Compare() as a comparison objectsame as previous
a.key_comp()X::key_comparereturns the comparison object out of which a was constructedconstant
a.value_comp()X::value_comparereturns an object constructed out of the comparison objectconstant
a_uniq.insert(t)pair<iterator,bool>"Inserts t if and only if there is no element in the container with + key equivalent to the key of t. The bool component of the returned pair + is true -iff- the insertion took place, and the iterator component of + the pair points to the element with key equivalent to the key of + t." logarithmic
a_eq.insert(t)iteratorinserts t, returns the iterator pointing to the inserted elementlogarithmic
a.insert(p,t)iteratorpossibly inserts t (depending on whether a_uniq or a_eq); returns iterator + pointing to the element with key equivalent to the key of t; iterator p + is a hint pointing to where the insert should start to searchlogarithmic in general, amortized constant if t is inserted right + after p
+ [but see DR 233 and our + specific notes]
a.insert(i,j)voidpre: i, j are not iterators into a. possibly inserts each element from + the range [i,j) (depending on whether a_uniq or a_eq)Nlog(size()+N) where N is distance(i,j) in general
a.erase(k)size_typeerases all elements with key equivalent to k; returns number of erased + elementslog(size()) + count(k)
a.erase(q)voiderases the element pointed to by qamortized constant
a.erase(q1,q2)voiderases all the elements in the range [q1,q2)log(size()) + distance(q1,q2)
a.clear()voiderases everything; post: size() == 0linear
a.find(k)iterator; const_iterator for constant areturns iterator pointing to element with key equivalent to k, or + a.end() if no such element foundlogarithmic
a.count(k)size_typereturns number of elements with key equivalent to klog(size()) + count(k)
a.lower_bound(k)iterator; const_iterator for constant areturns iterator pointing to the first element with key not less than klogarithmic
a.upper_bound(k)iterator; const_iterator for constant areturns iterator pointing to the first element with key greater than klogarithmic
a.equal_range(k)pair<iterator,iterator>; + pair<const_iterator, const_iterator> for constant aequivalent to make_pair(a.lower_bound(k), a.upper_bound(k))logarithmic

 + + +
+

+See mainpage.html for copying conditions. +See the libstdc++ homepage +for more information. +

+ + + + + -- cgit v1.1