bslstl_multimap

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on KEY and VALUE
  • Memory Allocation
    • bslma-Style Allocators
  • Operations
  • Usage
    • Example 1: Creating a Phone Book

Purpose

Provide an STL-compliant multimap class.

Classes

• bsl::multimap: STL-compatible multimap template

Canonical header: bsl_map.h

See also

bslstl_map, bslstl_multiset

Description

This component defines a single class template, bsl::multimap, implementing the standard container holding an ordered sequence of key-value pairs (possibly having duplicate keys), and presenting a mapping from the keys (of a template parameter type, KEY) to their associated values (of another template parameter type, VALUE).

An instantiation of multimap is an allocator-aware, value-semantic type whose salient attributes are its size (number of key-value pairs) and the ordered sequence of key-value pairs the multimap contains. If multimap is instantiated with either a key type or mapped-value type that is not itself value-semantic, then it will not retain all of its value-semantic qualities. In particular, if either the key or value type cannot be tested for equality, then a multimap containing that type cannot be tested for equality. It is even possible to instantiate multimap with a key or mapped-value type that does not have a copy-constructor, in which case the multimap will not be copyable.

A multimap meets the requirements of an associative container with bidirectional iterators in the C++ standard [23.2.4]. The multimap implemented here adheres to the C++11 standard when compiled with a C++11 compiler, and makes the best approximation when compiled with a C++03 compiler. In particular, for C++03 we emulate move semantics, but limit forwarding (in emplace) to const lvalues, and make no effort to emulate noexcept or initializer-lists.

Requirements on KEY and VALUE

A multimap is a fully "Value-Semantic Type" (see bsldoc_glossary ) only if the supplied KEY and VALUE template parameters are themselves fully value-semantic. It is possible to instantiate a multimap with KEY and VALUE parameter arguments that do not provide a full set of value-semantic operations, but then some methods of the container may not be instantiable. The following terminology, adopted from the C++11 standard, is used in the function documentation of multimap to describe a function's requirements for the KEY and VALUE template parameters. These terms are also defined in section [17.6.3.1] of the C++11 standard. Note that, in the context of a multimap instantiation, the requirements apply specifically to the multimap's entry type, value_type, which is an alias for 'pair<const KEY, VALUE>'.

Legend
------
'X'    - denotes an allocator-aware container type (e.g., 'multimap')
'T'    - 'value_type' associated with 'X'
'A'    - type of the allocator used by 'X'
'm'    - lvalue of type 'A' (allocator)
'p',   - address ('T *') of uninitialized storage for a 'T' within an 'X'
'rv'   - rvalue of type (non-'const') 'T'
'v'    - rvalue or lvalue of type (possibly 'const') 'T'
'args' - 0 or more arguments

The following terms are used to more precisely specify the requirements on template parameter types in function-level documentation.

default-insertable: T has a default constructor. More precisely, T is default-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p)

move-insertable: T provides a constructor that takes an rvalue of type (non-const) T. More precisely, T is move-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, rv)

copy-insertable: T provides a constructor that takes an lvalue or rvalue of type (possibly const) T. More precisely, T is copy-insertable into X means that the following expression is well-formed: allocator_traits<A>::construct(m, p, v)

move-assignable: T provides an assignment operator that takes an rvalue of type (non-const) T.

copy-assignable: T provides an assignment operator that takes an lvalue or rvalue of type (possibly const) T.

emplace-constructible: T is emplace-constructible into X from args means that the following expression is well-formed:

allocator_traits<A>::construct(m, p, args)

erasable: T provides a destructor. More precisely, T is erasable from X means that the following expression is well-formed: allocator_traits<A>::destroy(m, p)

equality-comparable: The type provides an equality-comparison operator that defines an equivalence relationship and is both reflexive and transitive.

Memory Allocation

The type supplied as a multimap's ALLOCATOR template parameter determines how that multimap will allocate memory. The multimap template supports allocators meeting the requirements of the C++11 standard [17.6.3.5]. In addition, it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma-style allocators should use the template's default ALLOCATOR type. The default type for the ALLOCATOR template parameter, bsl::allocator, provides a C++11 standard-compatible adapter for a bslma::Allocator object.

bslma-Style Allocators

If the (template parameter) type ALLOCATOR of a multimap instantiation is bsl::allocator, then objects of that multimap type will conform to the standard behavior of a bslma-allocator-enabled type. Such a multimap accepts an optional bslma::Allocator argument at construction. If the address of a bslma::Allocator object is explicitly supplied at construction, it is used to supply memory for the multimap throughout its lifetime; otherwise, the multimap will use the default allocator installed at the time of the multimap's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a multimap supplies that allocator's address to the constructors of contained objects of the (template parameter) types KEY and VALUE, if respectively, the types define the bslma::UsesBslmaAllocator trait.

Operations

This section describes the run-time complexity of operations on instances of multimap:

Legend
------
'K'             - (template parameter) type 'KEY' of the 'multimap'
'V'             - (template parameter) type 'VALUE' of the 'multimap'
'a', 'b'        - two distinct objects of type 'multimap<K, V>'
'rv'            - modifiable rvalue of type 'multimap<K, V>'
'n', 'm'        - number of elements in 'a' and 'b', respectively
'value_type'    - 'pair<const K, V>'
'c'             - comparator providing an ordering for objects of type 'K'
'al'            - STL-style memory allocator
'i1', 'i2'      - two iterators defining a sequence of 'value_type' objects
'k'             - object of type 'K'
'v'             - object of type 'V'
'vt'            - object of type 'value_type'
'rvt'           - modifiable rvalue of type 'value_type'
'p1', 'p2'      - two 'const_iterator's belonging to 'a'
distance(i1,i2) - number of elements in the range '[i1 .. i2)'
 
+----------------------------------------------------+--------------------+
| Operation                                          | Complexity         |
+====================================================+====================+
| multimap<K, V> a;        (default construction)    | O[1]               |
| multimap<K, V> a(al);                              |                    |
| multimap<K, V> a(c, al);                           |                    |
+----------------------------------------------------+--------------------+
| multimap<K, V> a(rv);    (move construction)       | O[1] if 'a' and    |
| multimap<K, V> a(rv, al);                          | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| multimap<K, V> a(b);     (copy construction)       | O[n]               |
| multimap<K, V> a(b, al);                           |                    |
+----------------------------------------------------+--------------------+
| multimap<K, V> a(i1, i2);                          | O[N] if [i1, i2)   |
| multimap<K, V> a(i1, i2, al);                      | is sorted with     |
| multimap<K, V> a(i1, i2, c, al);                   | 'a.value_comp()',  |
|                                                    | O[N * log(N)]      |
|                                                    | otherwise, where N |
|                                                    | is distance(i1,i2) |
+----------------------------------------------------+--------------------+
| a.~multimap<K, V>();     (destruction)             | O[n]               |
+----------------------------------------------------+--------------------+
| a = rv;                  (move assignment)         | O[1] if 'a' and    |
|                                                    | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| a = b;                   (copy assignment)         | O[n]               |
+----------------------------------------------------+--------------------+
| a.begin(), a.end(), a.cbegin(), a.cend(),          | O[1]               |
| a.rbegin(), a.rend(), a.crbegin(), a.crend()       |                    |
+----------------------------------------------------+--------------------+
| a == b, a != b                                     | O[n]               |
+----------------------------------------------------+--------------------+
| a < b, a <= b, a > b, a >= b                       | O[n]               |
+----------------------------------------------------+--------------------+
| a.swap(b), swap(a, b)                              | O[1] if 'a' and    |
|                                                    | 'b' use the same   |
|                                                    | allocator,         |
|                                                    | O[n + m] otherwise |
+----------------------------------------------------+--------------------+
| a.size()                                           | O[1]               |
+----------------------------------------------------+--------------------+
| a.max_size()                                       | O[1]               |
+----------------------------------------------------+--------------------+
| a.empty()                                          | O[1]               |
+----------------------------------------------------+--------------------+
| get_allocator()                                    | O[1]               |
+----------------------------------------------------+--------------------+
| a.insert(vt)                                       | O[log(n)]          |
| a.insert(rvt)                                      |                    |
| a.emplace(Args&&...)                               |                    |
+----------------------------------------------------+--------------------+
| a.insert(p1, vt)                                   | amortized constant |
| a.insert(p1, rvt)                                  | if the value is    |
| a.emplace(p1, Args&&...)                           | inserted right     |
|                                                    | before p1,         |
|                                                    | O[log(n)]          |
|                                                    | otherwise          |
+----------------------------------------------------+--------------------+
| a.insert(i1, i2)                                   | O[log(N) *         |
|                                                    |   distance(i1,i2)] |
|                                                    |                    |
|                                                    | where N is         |
|                                                    | n + distance(i1,i2)|
+----------------------------------------------------+--------------------+
| a.erase(p1)                                        | amortized constant |
+----------------------------------------------------+--------------------+
| a.erase(k)                                         | O[log(n) +         |
|                                                    | a.count(k)]        |
+----------------------------------------------------+--------------------+
| a.erase(p1, p2)                                    | O[log(n) +         |
|                                                    | distance(p1, p2)]  |
+----------------------------------------------------+--------------------+
| a.erase(p1, p2)                                    | O[log(n) +         |
|                                                    | distance(p1, p2)]  |
+----------------------------------------------------+--------------------+
| a.clear()                                          | O[n]               |
+----------------------------------------------------+--------------------+
| a.contains(k)                                      | O[log(n)]          |
+----------------------------------------------------+--------------------+
| a.key_comp()                                       | O[1]               |
+----------------------------------------------------+--------------------+
| a.value_comp()                                     | O[1]               |
+----------------------------------------------------+--------------------+
| a.find(k)                                          | O[log(n)]          |
+----------------------------------------------------+--------------------+
| a.count(k)                                         | O[log(n) +         |
|                                                    | a.count(k)]        |
+----------------------------------------------------+--------------------+
| a.lower_bound(k)                                   | O[log(n)]          |
+----------------------------------------------------+--------------------+
| a.upper_bound(k)                                   | O[log(n)]          |
+----------------------------------------------------+--------------------+
| a.equal_range(k)                                   | O[log(n)]          |
+----------------------------------------------------+--------------------+

Usage

In this section we show intended use of this component.

Example 1: Creating a Phone Book

In this example, we will define a class PhoneBook, that provides a mapping of names to phone numbers. The PhoneBook class will be implemented using a bsl::multimap, and will supply manipulators, allowing a client to add or remove entries from the phone book, as well as accessors, allowing clients to efficiently lookup entries by name, and to iterate over the entries in the phone book in sorted order.

Note that this example uses a type string that is based on the standard type string (see bslstl_string ). For the sake of brevity, the implementation of string is not explored here.

First, we define an alias for a pair of string objects that we will use to represent names in the phone book:

typedef bsl::pair<string, string> FirstAndLastName;
    // This 'typedef' provides an alias for a pair of 'string' objects,
    // whose 'first' and 'second' elements refer to the first and last
    // names of a person, respectively.

Then, we define a comparison functor for FirstAndLastName objects (note that this comparator is required because we intend for the last name to take precedence over the first name in the ordering of entries maintained by the phone book, which differs from the behavior supplied by operator< for bsl::pair):

struct FirstAndLastNameLess {
    // This 'struct' defines an ordering on 'FirstAndLastName' values,
    // allowing them to be included in sorted containers such as
    // 'bsl::multimap'.  Note that last name (the 'second' member of a
    // 'FirstAndLastName' value) takes precedence over first name in the
    // ordering defined by this functor.
 
    bool operator()(const FirstAndLastName& lhs,
                    const FirstAndLastName& rhs) const
        // Return 'true' if the value of the specified 'lhs' is less than
        // (ordered before) the value of the specified 'rhs', and 'false'
        // otherwise.  The 'lhs' value is considered less than the 'rhs'
        // value if the second value in the 'lhs' pair (the last name) is
        // less than the second value in the 'rhs' pair or, if the second
        // values are equal, if the first value in the 'lhs' pair (the
        // first name) is less than the first value in the 'rhs' pair.
    {
        int cmp = std::strcmp(lhs.second.c_str(), rhs.second.c_str());
        if (0 == cmp) {
            cmp = std::strcmp(lhs.first.c_str(), rhs.first.c_str());
        }
        return cmp < 0;
    }
};

Next, we define the public interface for PhoneBook:

class PhoneBook {
    // This class provides a mapping of a person's name to their phone
    // number.  Names within a 'PhoneBook' are represented using a using
    // 'FirstAndLastName' object, and phone numbers are represented using a
    // 'bsls::Types::Uint64' value.

Here, we create a type alias, NameToNumberMap, for a bsl::multimap that will serve as the data member for a PhoneBook. A NameToNumberMap has keys of type FirstAndLastName, mapped-values of type bsls::Types::Uint64, and a comparator of type FirstAndLastNameLess. We use the default ALLOCATOR template parameter as we intend to use PhoneBook with bslma style allocators:

    // PRIVATE TYPES
    typedef bsl::multimap<FirstAndLastName,
                          bsls::Types::Uint64,
                          FirstAndLastNameLess> NameToNumberMap;
        // This 'typedef' is an alias for a mapping between names and phone
        // numbers.
 
    // DATA
    NameToNumberMap d_nameToNumber;  // mapping of names to phone numbers
 
    // FRIENDS
    friend bool operator==(const PhoneBook& lhs, const PhoneBook& rhs);
 
  public:
    // PUBLIC TYPES
    typedef bsls::Types::Uint64 PhoneNumber;
        // This 'typedef' provides an alias for the type of an unsigned
        // integers used to represent phone-numbers in a 'PhoneBook'.
 
    typedef NameToNumberMap::const_iterator ConstIterator;
        // This 'typedef' provides an alias for the type of an iterator
        // providing non-modifiable access to the entries in a 'PhoneBook'.
 
    // CREATORS
    PhoneBook(bslma::Allocator *basicAllocator = 0);
        // Create an empty 'PhoneBook' object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    PhoneBook(const PhoneBook&  original,
              bslma::Allocator  *basicAllocator = 0);
        // Create a 'PhoneBook' object having the same value as the
        // specified 'original' object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    //! ~PhoneBook() = default;
        // Destroy this object.
 
    // MANIPULATORS
    PhoneBook& operator=(const PhoneBook& rhs);
        // Assign to this object the value of the specified 'rhs' object,
        // and return a reference providing modifiable access to this
        // object.
 
    void addEntry(const FirstAndLastName& name, PhoneNumber number);
        // Add an entry to this phone book having the specified 'name' and
        // 'number'.  The behavior is undefined unless 'name.first' and
        // 'name.end' are non-empty strings.
 
    int removeEntry(const FirstAndLastName& name, PhoneNumber number);
        // Remove the entries from this phone book having the specified
        // 'name' and 'number', if they exists, and return the number of
        // removed entries; otherwise, return 0 with no other effects.
 
    // ACCESSORS
    bsl::pair<ConstIterator, ConstIterator> lookupByName(
                                       const FirstAndLastName& name) const;
        // Return a pair of iterators to the ordered sequence of entries
        // held in this phone book having the specified 'name', where the
        // first iterator is position at the start of the sequence, and the
        // second is positioned one past the last entry in the sequence.
        // If 'name' does not exist in this phone book, then the two
        // returned iterators will have the same value.
 
    ConstIterator begin() const;
        // Return an iterator providing non-modifiable access to the first
        // entry in the ordered sequence of entries held in this phone
        // book, or the past-the-end iterator if this phone book is empty.
 
    ConstIterator end() const;
        // Return an iterator providing non-modifiable access to the
        // past-the-end entry in the ordered sequence of entries maintained
        // by this phone book.
 
    size_t numEntries() const;
        // Return the number of entries contained in this phone book.
};

Then, we declare the free operators for PhoneBook:

inline
bool operator==(const PhoneBook& lhs, const PhoneBook& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects have the same
    // value, and 'false' otherwise.  Two 'PhoneBook' objects have the
    // same value if they have the same number of entries, and each
    // corresponding entry, in their respective ordered sequence of
    // entries, is the same.
 
inline
bool operator!=(const PhoneBook& lhs, const PhoneBook& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
    // the same value, and 'false' otherwise.  Two 'PhoneBook' objects do
    // not have the same value if they either differ in their number of
    // contained entries, or if any of the corresponding entries, in their
    // respective ordered sequences of entries, is not the same.

Now, we define the implementations methods of the PhoneBook class:

// CREATORS
inline
PhoneBook::PhoneBook(bslma::Allocator *basicAllocator)
: d_nameToNumber(FirstAndLastNameLess(), basicAllocator)
{
}

Notice that, on construction, we pass the contained bsl::multimap (d_nameToNumber), a default constructed FirstAndLastNameLess object that it will use to perform comparisons, and the allocator supplied to PhoneBook at construction'.

inline
PhoneBook::PhoneBook(const PhoneBook&   original,
                     bslma::Allocator  *basicAllocator)
: d_nameToNumber(original.d_nameToNumber, basicAllocator)
{
}
 
// MANIPULATORS
inline
PhoneBook& PhoneBook::operator=(const PhoneBook& rhs)
{
    d_nameToNumber = rhs.d_nameToNumber;
    return *this;
}
 
inline
void PhoneBook::addEntry(const FirstAndLastName& name, PhoneNumber number)
{
    BSLS_ASSERT(!name.first.empty());
    BSLS_ASSERT(!name.second.empty());
 
    d_nameToNumber.insert(NameToNumberMap::value_type(name, number));
}
 
inline
int PhoneBook::removeEntry(const FirstAndLastName& name,
                           PhoneNumber             number)
{
    bsl::pair<NameToNumberMap::iterator, NameToNumberMap::iterator> range =
                                          d_nameToNumber.equal_range(name);
 
    NameToNumberMap::iterator it = range.first;
 
    int numRemovedEntries = 0;
 
    while (it != range.second) {
        if (it->second == number) {
            it = d_nameToNumber.erase(it);
            ++numRemovedEntries;
        }
        else {
            ++it;
        }
    }
 
    return numRemovedEntries;
}
 
// ACCESSORS
inline
bsl::pair<PhoneBook::ConstIterator, PhoneBook::ConstIterator>
PhoneBook::lookupByName(const FirstAndLastName&  name) const
{
    return d_nameToNumber.equal_range(name);
}
 
inline
PhoneBook::ConstIterator PhoneBook::begin() const
{
    return d_nameToNumber.begin();
}
 
inline
PhoneBook::ConstIterator PhoneBook::end() const
{
    return d_nameToNumber.end();
}
 
inline
size_t PhoneBook::numEntries() const
{
    return d_nameToNumber.size();
}

Finally, we implement the free operators for PhoneBook:

inline
bool operator==(const PhoneBook& lhs, const PhoneBook& rhs)
{
    return lhs.d_nameToNumber == rhs.d_nameToNumber;
}
 
inline
bool operator!=(const PhoneBook& lhs, const PhoneBook& rhs)
{
    return !(lhs == rhs);
}