bslstl_multiset

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on KEY
  • Memory Allocation
    • bslma-Style Allocators
  • Operations
  • Usage
    • Example 1: Creating a Shopping Cart

Purpose

Provide an STL-compliant multiset class.

Classes

• bsl::multiset: STL-compatible multiset template

Canonical header: bsl_set.h

See also

bslstl_set, bslstl_multimap

Description

This component defines a single class template bsl::multiset, implementing the standard container holding an ordered sequence of possibly duplicate keys.

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

A multiset meets the requirements of an associative container with bidirectional iterators in the C++ standard [23.2.4]. The multiset 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

A multiset is a fully "Value-Semantic Type" (see bsldoc_glossary ) only if the supplied KEY template parameter is fully value-semantic. It is possible to instantiate a multiset with a KEY parameter argument that does 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 multiset to describe a function's requirements for the KEY template parameter. These terms are also defined in section [17.6.3.1] of the C++11 standard. Note that, in the context of a multiset instantiation, the requirements apply specifically to the multiset's entry type, value_type, which is an alias for KEY.

Legend

X - denotes an allocator-aware container type (e.g., multiset) 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 multiset's ALLOCATOR template parameter determines how that multiset will allocate memory. The multiset 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 multiset instantiation is bsl::allocator, then objects of that multiset type will conform to the standard behavior of a bslma-allocator-enabled type. Such a multiset 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 multiset throughout its lifetime; otherwise, the multiset will use the default allocator installed at the time of the multiset's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a multiset supplies that allocator's address to the constructors of contained objects of the (template parameter) type KEY having the bslma::UsesBslmaAllocator trait.

Operations

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

Legend
------
'K'             - (template parameter) type 'KEY' of the multiset
'a', 'b'        - two distinct objects of type 'multiset<K>'
'rv'            - modifiable rvalue of type 'multiset<K>'
'n', 'm'        - number of elements in 'a' and 'b' respectively
'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
'li'            - object of type 'initializer_list<K>'
'k'             - object of type 'K'
'rk'            - modifiable rvalue of type 'K'
'p1', 'p2'      - two 'const_iterator's belonging to 'a'
distance(i1,i2) - number of elements in the range '[i1 .. i2)'
distance(p1,p2) - number of elements in the range '[p1 .. p2)'
 
+----------------------------------------------------+--------------------+
| Operation                                          | Complexity         |
+====================================================+====================+
| multiset<K> a;               (default construction)| O[1]               |
| multiset<K> a(al);                                 |                    |
| multiset<K> a(c, al);                              |                    |
+----------------------------------------------------+--------------------+
| multiset<K> a(b);            (copy construction)   | O[n]               |
| multiset<K> a(b, al);                              |                    |
+----------------------------------------------------+--------------------+
| multiset<K> a(rv);           (move construction)   | O[1] if 'a' and    |
| multiset<K> a(rv, al);                             | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| multiset<K> a(i1, i2, al);   (range construction)  | O[N] if [i1, i2)   |
| multiset<K> a(i1, i2, c, al);                      | is sorted with     |
|                                                    | 'a.value_comp()',  |
|                                                    | O[N * log(N)]      |
|                                                    | otherwise, where N |
|                                                    | is distance(i1,i2) |
+----------------------------------------------------+--------------------+
| multiset<K> a(li);                                 | O[N] if 'li' is    |
| multiset<K> a(li, al);                             | sorted with        |
| multiset<K> a(li, c);                              | 'a.value_comp()',  |
| multiset<K> a(li, c, al);                          | O[N * log(N)]      |
|                                                    | otherwise, where   |
|                                                    | N = 'li.size()'    |
+----------------------------------------------------+--------------------+
| a.~multiset<K>();            (destruction)         | O[n]               |
+----------------------------------------------------+--------------------+
| a = b;                       (copy assignment)     | O[n]               |
+----------------------------------------------------+--------------------+
| a = rv;                      (move assignment)     | O[1] if 'a' and    |
|                                                    | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| a = li;                                            | O[N] if 'li' is    |
|                                                    | sorted with        |
|                                                    | 'a.value_comp()',  |
|                                                    | O[N * log(N)]      |
|                                                    | otherwise, where   |
|                                                    | N = 'li.size()'    |
+----------------------------------------------------+--------------------+
| 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(k)                                        | O[log(n)]          |
| a.insert(rk)                                       |                    |
| a.emplace(Args&&...)                               |                    |
+----------------------------------------------------+--------------------+
| a.insert(p1, k)                                    | amortized constant |
| a.insert(p1, rk)                                   | if the value is    |
| a.emplace_hint(p1, Args&&...)                      | inserted right     |
|                                                    | before p1,         |
|                                                    | O[log(n)]          |
|                                                    | otherwise          |
+----------------------------------------------------+--------------------+
| a.insert(i1, i2)                                   | O[N * log(n + N)]  |
|                                                    | where N is         |
|                                                    | distance(i1,i2)    |
+----------------------------------------------------+--------------------+
| a.insert(li)                                       | O[N * log(n + N)]  |
|                                                    | where N =          |
|                                                    |         'li.size()'|
+----------------------------------------------------+--------------------+
| 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.clear()                                          | O[n]               |
+----------------------------------------------------+--------------------+
| a.key_comp()                                       | O[1]               |
+----------------------------------------------------+--------------------+
| a.value_comp()                                     | O[1]               |
+----------------------------------------------------+--------------------+
| a.contains(k)                                      | O[log(n)]          |
+----------------------------------------------------+--------------------+
| 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 Shopping Cart

In this example, we will utilize bsl::multiset to define a class ShoppingCart, that characterizes a simple online shopping cart with the ability to add, remove, and view items in the shopping cart.

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 a comparison functor for string objects:

struct StringComparator {
    // This 'struct' defines an ordering on 'string' values, allowing
    // them to be included in sorted containers such as 'bsl::multiset'.
 
    bool operator()(const string& lhs, const string& 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.
    {
        int cmp = std::strcmp(lhs.c_str(), rhs.c_str());
        return cmp < 0;
    }
};

Then, we define the public interface for ShoppingCart:

class ShoppingCart {
    // This class provides an ordered collection of (possibly duplicate)
    // items in a shopping cart.  For simplicity of the usage example, each
    // item in the shopping cart is represented by a 'string'.

Here, we create a type alias, StringSet, for a bsl::multiset that will serve as the data member for a ShoppingCart. A StringSet has keys of type string, and uses the default ALLOCATOR template parameter to be compatible with bslma style allocators:

    // PRIVATE TYPES
    typedef bsl::multiset<string, StringComparator> StringSet;
        // This 'typedef' is an alias for a multiset of 'string' objects,
        // each representing an item in a shopping cart;
 
    // DATA
    StringSet d_items;  // multiset of items in the shopping cart
 
    // FRIENDS
    friend bool operator==(const ShoppingCart& lhs,
                           const ShoppingCart& rhs);
 
  public:
    // PUBLIC TYPES
    typedef StringSet::const_iterator ConstIterator;
        // This 'typedef' provides an alias for the type of an iterator
        // providing non-modifiable access to the items in a
        // 'ShoppingCart'.
 
    // CREATORS
    ShoppingCart(bslma::Allocator *basicAllocator = 0);
        // Create an empty 'Shopping' object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    ShoppingCart(const ShoppingCart&  original,
                 bslma::Allocator    *basicAllocator = 0);
        // Create a 'ShoppingCart' 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.
 
    //! ~ShoppingCart() = default;
        // Destroy this object.
 
    // MANIPULATORS
    ShoppingCart& operator=(const ShoppingCart& rhs);
        // Assign to this object the value of the specified 'rhs' object,
        // and return a reference providing modifiable access to this
        // object.
 
    void addItem(const string& name);
        // Add an item with the specified 'name' to this shopping cart.
        // The behavior is undefined unless 'name' is a non-empty strings.
 
    size_t removeItems(const string& name);
        // Remove from this shopping cart all items having the specified
        // 'name', if they exist, and return the number of removed items;
        // otherwise, return 0 with no other effects.  The behavior is
        // undefined unless 'name' is a non-empty strings.
 
    // ACCESSORS
    size_t count(const string& name) const;
        // Return the number of items in the shopping cart with the
        // specified 'name'.  The behavior is undefined unless 'name' is a
        // non-empty strings.
 
    ConstIterator begin() const;
        // Return an iterator providing non-modifiable access to the first
        // item in the ordered sequence of item held in this shopping cart,
        // or the past-the-end iterator if this shopping cart is empty.
 
    ConstIterator end() const;
        // Return an iterator providing non-modifiable access to the
        // past-the-end item in the ordered sequence of items maintained by
        // this shopping cart.
 
    size_t numItems() const;
        // Return the number of items contained in this shopping cart.
};

Then, we declare the free operators for ShoppingCart:

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

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

// CREATORS
inline
ShoppingCart::ShoppingCart(bslma::Allocator *basicAllocator)
: d_items(basicAllocator)
{
}

Notice that, on construction, we pass the contained bsl::multiset object the allocator supplied to ShoppingCart at construction'.

inline
ShoppingCart::ShoppingCart(const ShoppingCart&   original,
                           bslma::Allocator     *basicAllocator)
: d_items(original.d_items, basicAllocator)
{
}
 
// MANIPULATORS
inline
ShoppingCart& ShoppingCart::operator=(const ShoppingCart& rhs)
{
    d_items = rhs.d_items;
    return *this;
}
 
inline
void ShoppingCart::addItem(const string& name)
{
    BSLS_ASSERT(!name.empty());
 
    d_items.insert(name);
}
 
inline
size_t ShoppingCart::removeItems(const string& name)
{
    BSLS_ASSERT(!name.empty());
 
    return d_items.erase(name);
}
 
// ACCESSORS
size_t ShoppingCart::count(const string& name) const
{
    BSLS_ASSERT(!name.empty());
 
    return d_items.count(name);
}
 
ShoppingCart::ConstIterator ShoppingCart::begin() const
{
    return d_items.begin();
}
 
ShoppingCart::ConstIterator ShoppingCart::end() const
{
    return d_items.end();
}
 
size_t ShoppingCart::numItems() const
{
    return d_items.size();
}

Finally, we implement the free operators for ShoppingCart:

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