123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523 |
- [/license
- Boost.Bimap
- Copyright (c) 2006-2007 Matias Capeletto
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- ]
- [/ QuickBook Document version 1.4 ]
- [section Bimap Reference]
- [section View concepts]
- `bimap` instantiations comprise two side views and an view of the relation
- specified at compile time. Each view allows read-write access to the elements contained
- in a definite manner, mathing an STL container signature.
- Views are not isolated objects and so cannot be constructed on their
- own; rather they are an integral part of a `bimap`. The name of the view
- class implementation proper is never directly exposed to the user, who
- has access only to the associated view type specifier.
- Insertion and deletion of elements are always performed through the
- appropriate interface of any of the three views of the `bimap`; these
- operations do, however, have an impact on all other views as well: for
- instance, insertion through a given view may fail because there exists
- another view that forbids the operation in order to preserve its
- invariant (such as uniqueness of elements). The global operations
- performed jointly in the any view can be reduced to six primitives:
- * copying
- * insertion of an element
- * hinted insertion, where a pre-existing element is suggested in order to improve
- the efficiency of the operation
- * deletion of an element
- * replacement of the value of an element, which may trigger the
- rearrangement of this element in one or more views, or may forbid the
- replacement
- * modification of an element, and its subsequent
- rearrangement/banning by the various views
- The last two primitives deserve some further explanation: in order to
- guarantee the invariants associated to each view (e.g. some definite
- ordering) elements of a `bimap` are not mutable. To overcome this
- restriction, the views expose member functions for updating and
- modifying, which allows for the mutation of elements in a controlled
- fashion.
- [endsect]
- [#complexity_signature_explanation]
- [section Complexity signature]
- Some member functions of a view interface are implemented by global
- primitives from the above list. The complexity of these operations thus
- depends on all views of a given `bimap`, not just the currently used view.
- In order to establish complexity estimates, a view is characterised by
- its complexity signature, consisting of the following associated
- functions on the number of elements:
- * `c(n)`: copying
- * `i(n)`: insertion
- * `h(n)`: hinted insertion
- * `d(n)`: deletion
- * `r(n)`: replacement
- * `m(n)`: modifying
- If the collection type of the relation is `left_based` or `right_based`, and we use
- an `l` subscript to denote the left view and an `r` for the right view, then
- the insertion of an element in such a container is of complexity
- `O(i_l(n)+i_r(n))`, where n is the number of elements. If the collection type of
- relation is not side-based, then there is an additional term to add that
- is contributed by the collection type of relation view. Using `a` to denote the
- above view, the complexity of insertion will now be
- `O(i_l(n)+i_r(n)+i_a(n))`. To abbreviate the notation, we adopt the
- following definitions:
- * `C(n) = c_l(n) + c_r(n) [ + c_a(n) ]`
- * `I(n) = i_l(n) + i_r(n) [ + i_a(n) ]`
- * `H(n) = h_l(n) + h_r(n) [ + h_a(n) ]`
- * `D(n) = d_l(n) + d_r(n) [ + d_a(n) ]`
- * `R(n) = r_l(n) + r_r(n) [ + r_a(n) ]`
- * `M(n) = m_l(n) + m_r(n) [ + m_a(n) ]`
- [endsect]
- [section Set type specification]
- Set type specifiers are passed as instantiation arguments to `bimap` and
- provide the information needed to incorporate the corresponding views.
- Currently, Boost.Bimap provides the collection type specifiers. The ['side collection type]
- specifiers define the constraints of the two map views of the
- bimap. The ['collection type of relation] specifier defines the main set view
- constraints. If `left_based` (the default parameter) or `right_based` is
- used, then the collection type of relation will be based on the left or right
- collection type correspondingly.
- [table
- [[Side collection type ][Collection type of relation ][Include ]]
- [[`set_of` ][`set_of_relation` ][`boost/bimap/set_of.hpp` ]]
- [[`multiset_of` ][`multiset_of_relation` ][`boost/bimap/multiset_of.hpp` ]]
- [[`unordered_set_of` ][`unordered_set_of_relation` ][`boost/bimap/unordered_set_of.hpp` ]]
- [[`unordered_multiset_of` ][`unordered_multiset_of_relation`][`boost/bimap/unordered_multiset_of.hpp` ]]
- [[`list_of` ][`list_of_relation` ][`boost/bimap/list_of.hpp` ]]
- [[`vector_of` ][`vector_of_relation` ][`boost/bimap/vector_of.hpp` ]]
- [[`unconstrained_set_of` ][`unconstrained_set_of_relation` ][`boost/bimap/unconstrained_set_of.hpp` ]]
- [[ ][`left_based` ][`boost/bimap/bimap.hpp` ]]
- [[ ][`right_based` ][`boost/bimap/bimap.hpp` ]]
- ]
- [endsect]
- [section Tags]
- Tags are just conventional types used as mnemonics for the types stored
- in a `bimap`. Boost.Bimap uses the tagged idiom to let the user specify
- this tags.
- [endsect]
- [section Header "boost/bimap/bimap.hpp" synopsis]
- namespace boost {
- namespace bimaps {
- template< class Type, typename Tag >
- struct tagged;
- // bimap template class
- template
- <
- class LeftCollectionType, class RightCollectionType,
- class AdditionalParameter_1 = detail::not_specified,
- class AdditionalParameter_2 = detail::not_specified
- >
- class bimap ``['- implementation defined { : public SetView } -]``
- {
- public:
- // Metadata
- typedef ``['-unspecified-]`` left_tag;
- typedef ``['-unspecified-]`` left_map;
- typedef ``['-unspecified-]`` right_tag;
- typedef ``['-unspecified-]`` right_map;
- // Shortcuts
- // typedef -side-_map::-type- -side-_-type-;
- typedef ``['-unspecified-]`` info_type;
- // Map views
- left_map left;
- right_map right;
- // Constructors
- bimap();
- template< class InputIterator >
- bimap(InputIterator first,InputIterator last);
- bimap(const bimap &);
- bimap& operator=(const bimap& b);
- // Projection of iterators
- template< class IteratorType >
- left_iterator project_left(IteratorType iter);
- template< class IteratorType >
- left_const_iterator project_left(IteratorType iter) const;
- template< class IteratorType >
- right_iterator project_right(IteratorType iter);
- template< class IteratorType >
- right_const_iterator project_right(IteratorType iter) const;
- template< class IteratorType >
- iterator project_up(IteratorType iter);
- template< class IteratorType >
- const_iterator project_up(IteratorType iter) const;
- // Support for tags
- template< class Tag >
- struct map_by;
- template< class Tag >
- map_by<Tag>::type by();
- template< class Tag >
- const map_by<Tag>::type & by() const;
- template< class Tag, class IteratorType >
- map_by<Tag>::iterator project(IteratorType iter);
- template< class Tag, class IteratorType >
- map_by<Tag>::const_iterator project(IteratorType iter) const
- };
- } // namespace bimap
- } // namespace boost
- [/
- // Metafunctions for a bimap
- template< class Tag, class Bimap > struct value_type_by;
- template< class Tag, class Bimap > struct key_type_by;
- template< class Tag, class Bimap > struct data_type_by;
- template< class Tag, class Bimap > struct iterator_type_by;
- template< class Tag, class Bimap > struct const_iterator_type_by;
- template< class Tag, class Bimap > struct reverse_iterator_type_by;
- template< class Tag, class Bimap > struct const_reverse_iterator_type_by;
- template< class Tag, class Bimap > struct local_iterator_type_by;
- template< class Tag, class Bimap > struct const_local_iterator_type_by;
- // Functions for a bimap
- template<class Tag, class Relation>
- result_of::map_by< Tag, Bimap>::type map_by(Bimap &);
- // Metafunctions for a relation
- template< class Tag, class Relation > struct value_type_of;
- template< class Tag, class Relation > struct pair_type_by;
- // Functions for a relation
- template<class Tag, class Relation>
- result_of::get< Tag, Relation>::type get(Relation &r);
- template<class Tag, class Relation>
- result_of::pair_by< Tag, Relation>::type pair_by(Relation &);
- ]
- [endsect]
- [section Class template bimap]
- This is the main component of Boost.Bimap.
- [section Complexity]
- In the descriptions of the operations of `bimap`, we adopt the scheme
- outlined in the complexity signature section.
- [endsect]
- [section Instantiation types]
- `bimap` is instantiated with the following types:
- # LeftCollectionType and RightCollectionType are collection type specifications
- optionally tagged, or any type optionally tagged, in which case that
- side acts as a set.
- # AdditionalParameter_{1/2} can be any ordered subset of:
- * CollectionTypeOfRelation specification
- * Allocator
- [endsect]
- [section Nested types]
- left_tag, right_tag
- [: Tags for each side of the bimap. If the user has not specified any tag the
- tags default to `member_at::left` and `member_at::right`.
- ]
- left_key_type, right_key_type
- [: Key type of each side. In a `bimap<A,B> ` `left_key_type` is `A` and
- `right_key_type` is `B`.
- If there are tags, it is better to use: `Bimap::map_by<Tag>::key_type`.
- ]
- left_data_type, right_data_type
- [: Data type of each side. In a bimap<A,B> left_key_type is B and
- right_key_type is A.
- If there are tags, it is better to use: `Bimap::map_by<Tag>::data_type`.
- ]
- left_value_type, right_value_type
- [: Value type used for the views.
- If there are tags, it is better to use: `Bimap::map_by<Tag>::value_type`.
- ]
- left_iterator, right_iterator
- left_const_iterator, right_const_iterator
- [: Iterators of the views.
- If there are tags, it is better to use:
- `Bimap::map_by<Tag>::iterator` and
- `Bimap::map_by<Tag>::const_iterator`
- ]
- left_map, right_map
- [: Map view type of each side.
- If there are tags, it is better to use:
- `Bimap::map_by<Tag>::type`.
- ]
- [endsect]
- [section Constructors, copy and assignment]
- bimap();
- * [*Effects:] Constructs an empty `bimap`.
- * [*Complexity:] Constant.
- template<typename InputIterator>
- bimap(InputIterator first,InputIterator last);
- * [*Requires: ] `InputIterator` is a model of Input Iterator over elements of
- type `relation` or a type convertible to `relation`. last is reachable from `first`.
- * [*Effects:] Constructs an empty `bimap` and fills it with the elements in the range
- `[first,last)`. Insertion of each element may or may not succeed depending on
- acceptance by the collection types of the `bimap`.
- * [link complexity_signature_explanation
- [*Complexity:]] O(m*H(m)), where m is the number of elements in `[first,last)`.
- bimap(const bimap & x);
- * [*Effects:] Constructs a copy of x, copying its elements as well as its
- internal objects (key extractors, comparison objects, allocator.)
- * [*Postconditions:] `*this == x`. The order of the views of the `bimap`
- is preserved as well.
- * [*Complexity:] O(x.size()*log(x.size()) + C(x.size()))
- ~bimap()
- * [*Effects:] Destroys the `bimap` and all the elements contained.
- The order in which the elements are destroyed is not specified.
- * [*Complexity:] O(n).
- bimap& operator=(const bimap& x);
- * [*Effects:] Replaces the elements and internal objects of the `bimap`
- with copies from x.
- * [*Postconditions:] `*this==x`. The order on the views of the `bimap`
- is preserved as well.
- * [*Returns: ] `*this`.
- * [*Complexity:] O(n + x.size()*log(x.size()) + C(x.size())).
- * [*Exception safety:] Strong, provided the copy and assignment operations
- of the types of `ctor_args_list` do not throw.
- [/
- allocator_type get_allocator() const;
- * [*Effects:] Returns a copy of the `allocator_type` object used to construct
- the `bimap`.
- * [*Complexity:] Constant.
- ]
- [endsect]
- [#reference_projection_operations]
- [section Projection operations]
- Given a `bimap` with views v1 and v2, we say than an v1-iterator
- it1 and an v2-iterator it2 are equivalent if:
- * `it1 == i1.end()` AND `it2 == i2.end()`,
- * OR `it1` and `it2` point to the same element.
- template< class IteratorType >
- left_iterator project_left(IteratorType iter);
- template< class IteratorType >
- left_const_iterator project_left(IteratorType iter) const;
- * [*Requires:] `IteratorType` is a bimap view iterator. it is a
- valid iterator of some view of `*this` (i.e. does not refer to some other
- `bimap`.)
- * [*Effects:] Returns a left map view iterator equivalent to `it`.
- * [*Complexity:] Constant.
- * [*Exception safety:] nothrow.
- template< class IteratorType >
- right_iterator project_right(IteratorType iter);
- template< class IteratorType >
- right_const_iterator project_right(IteratorType iter) const;
- * [*Requires:] `IteratorType` is a bimap view iterator. it is a
- valid iterator of some view of `*this` (i.e. does not refer to some other
- `bimap`.)
- * [*Effects:] Returns a right map view iterator equivalent to `it`.
- * [*Complexity:] Constant.
- * [*Exception safety:] nothrow.
- template< class IteratorType >
- iterator project_up(IteratorType iter);
- template< class IteratorType >
- const_iterator project_up(IteratorType iter) const;
- * [*Requires:] `IteratorType` is a bimap view iterator. it is a
- valid iterator of some view of `*this` (i.e. does not refer to some other
- `bimap`.)
- * [*Effects:] Returns a collection of relations view iterator equivalent to `it`.
- * [*Complexity:] Constant.
- * [*Exception safety:] nothrow.
- [endsect]
- [#reference_support_for_used_defined_names]
- [section Support for user defined names]
- template< class Tag >
- struct map_by;
- * `map_by<Tag>::type` yields the type of the map view tagged with `Tag`.
- `map_by<Tag>::`['-type name-] is the same as `map_by<Tag>::type::`['-type name-].
- * [*Requires: ] `Tag` is a valid user defined name of the bimap.
- template< class Tag >
- map_by<Tag>::type by();
- template< class Tag >
- const map_by<Tag>::type & by() const;
- * [*Requires: ] `Tag` is a valid user defined name of the bimap.
- * [*Effects:] Returns a reference to the map view tagged with `Tag` held by
- `*this`.
- * [*Complexity:] Constant.
- * [*Exception safety:] nothrow.
- template< class Tag, class IteratorType >
- map_by<Tag>::iterator project(IteratorType iter);
- template< class Tag, class IteratorType >
- map_by<Tag>::const_iterator project(IteratorType iter) const
- * [*Requires: ] `Tag` is a valid user defined name of the bimap. `IteratorType`
- is a bimap view iterator. it is a valid iterator of some view of `*this`
- (i.e. does not refer to some other `bimap`.)
- * [*Effects:] Returns a reference to the map view tagged with `Tag` held by
- `*this`.
- * [*Complexity:] Constant.
- * [*Exception safety:] nothrow.
- [endsect]
- [section Serialization]
- A `bimap` can be archived and retrieved by means of __BOOST_SERIALIZATION__.
- Boost.Bimap does not expose a public serialisation interface, as this is
- provided by Boost.Serialization itself. Both regular and XML archives
- are supported.
- Each of the set specifications comprising a given `bimap` contributes its
- own preconditions as well as guarantees on the retrieved containers. In describing
- these, the following concepts are used. A type `T` is ['serializable]
- (resp. XML-serializable) if any object of type `T` can be saved to an output
- archive (XML archive) and later retrieved from an input archive (XML archive)
- associated to the same storage. If `x`' of type `T` is loaded from the serialization
- information saved from another object x, we say that x' is a ['restored copy] of x.
- Given a __SGI_BINARY_PREDICATE__ `Pred` over `(T, T)`, and objects `p` and `q` of
- type `Pred`, we say that `q` is ['serialization-compatible] with `p` if
- * `p(x,y) == q(x`'`,y`'`)`
- for every `x` and `y` of type `T` and `x`' and `y`' being restored copies of `x`
- and `y`, respectively.
- [blurb [*Operation:] saving of a `bimap b` to an output archive
- (XML archive) ar.]
- * [*Requires:] Value is serializable (XML-serializable). Additionally, each
- of the views of b can impose other requirements.
- * [*Exception safety:] Strong with respect to `b`. If an exception is thrown, ar
- may be left in an inconsistent state.
- [blurb [*Operation:] loading of a `bimap` m' from an input archive
- (XML archive) ar.]
- * [*Requires:] Value is serializable (XML-serializable). Additionally, each of
- the views of `b`' can impose other requirements.
- * [*Exception safety:] Basic. If an exception is thrown, ar may be left in an
- inconsistent state.
- [endsect]
- [endsect]
- [endsect]
|