bslstl_map

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on KEY and VALUE
  • Glossary
  • Key Comparison
  • Memory Allocation
    • bslma-Style Allocators
  • Operations
  • Usage
    • Example 1: Creating a Trade Matching System

Purpose

Provide an STL-compliant map class.

Classes

• bsl::map: STL-compliant map template

Canonical header: bsl_map.h

See also

bslstl_multimap, bslstl_set

Description

This component defines a single class template bsl::map, implementing the standard container holding an ordered sequence of key-value pairs (having unique 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 map 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 map contains. If map 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 map containing that type cannot be tested for equality. It is even possible to instantiate map with a key or mapped-value type that does not have a copy constructor, in which case the map will not be copyable.

A map meets the requirements of an associative container with bidirectional iterators in the C++ standard [associative.reqmts]. The map 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 map 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 map 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 map to describe a function's requirements for the KEY and VALUE template parameters. These terms are also defined in sections [utility.arg.requirements] and [container.requirements.general] of the C++11 standard. Note that, in the context of a map instantiation, the requirements apply specifically to the map's entry type, value_type, which is an alias for bsl::pair<const KEY, VALUE>.

Glossary

Legend
------
'X'    - denotes an allocator-aware container type (e.g., 'map')
'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.

Key Comparison

The type supplied as a map's COMPARATOR template parameter determines how that map will order elements. In particular, the COMPARATOR type must induce a strict weak ordering on objects of type KEY. The COMPARATOR parameter defaults to std::less<KEY> when not supplied in an instantiation of map. Note that the COMPARATOR type must be copy-constructible.

The C++11 standard does not require that the function-call operator provided by COMPARATOR functors be const-qualified. However, there is a suggestion for C++17 that this is an oversight in the standard, and that const-qualification will be required in the future. Keep this in mind when opting to use an alternative to the default COMPARATOR.

Memory Allocation

The type supplied as a map's ALLOCATOR template parameter determines how that map will allocate memory. The map template supports allocators meeting the requirements of the C++11 standard [allocator.requirements]. In addition, map 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 map instantiation' is bsl::allocator, then objects of that map type will conform to the standard behavior of a bslma-allocator-enabled type. Such a map 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 map throughout its lifetime; otherwise, the map will use the default allocator installed at the time of the map's construction (see bslma_default ). In addition to directly allocating memory from the indicated bslma::Allocator, a map supplies that allocator's address to the constructors of contained objects of the (template parameter) type 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 map:

Legend
------
'K'             - (template parameter) type 'KEY' of the map
'V'             - (template parameter) type 'VALUE' of the map
'a', 'b'        - two distinct objects of type 'map<K, V>'
'rv'            - modifiable rvalue of type 'map<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         |
+====================================================+====================+
| map<K, V> a;     (default construction)            | O[1]               |
| map<K, V> a(al);                                   |                    |
| map<K, V> a(c, al);                                |                    |
+----------------------------------------------------+--------------------+
| map<K, V> a(rv); (move construction)               | O[1] if 'a' and    |
| map<K, V> a(rv, al);                               | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| map<K, V> a(b);  (copy construction)               | O[n]               |
| map<K, V> a(b, al);                                |                    |
+----------------------------------------------------+--------------------+
| map<K, V> a(i1, i2);                               | O[N] if [i1 .. i2) |
| map<K, V> a(i1, i2, al);                           | is sorted with     |
| map<K, V> a(i1, i2, c, al);                        | 'a.value_comp()',  |
|                                                    | O[N * log(N)]      |
|                                                    | otherwise, where N |
|                                                    | is distance(i1,i2) |
+----------------------------------------------------+--------------------+
| a.~map<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[k]                                               | O[log(n)]          |
+----------------------------------------------------+--------------------+
| a.at(k)                                            | O[log(n)]          |
+----------------------------------------------------+--------------------+
| 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 Trade Matching System

In this example, we will utilize bsl::map to define and implement a class, TradeMatcher, that provides a simple trade matching system for a single stock. The manipulators of TradeMatcher will allow clients to place buy orders and sell orders, and the accessors of TradeMatcher will allow clients to retrieve active orders and past executions.

First, we define the public interface for TradeMatcher:

/// This class provides a mechanism that characterizes a simple trade
/// matching system for one stock.  An object of this class allows
/// clients to place orders and view the active orders.
class TradeMatcher {

Here, we create two type aliases, SellOrdersMap and BuyOrdersMap, for two bsl::map instantiations that maps the price of an order (type double) to the quantity of the order (type int). SellOrdersMap uses the default bsl::less comparator to store the sequence of sell orders in ascending price order. BuyOrdersMap uses the bsl::greater comparator to store the sequence of buy orders in descending price order. Also note that we use the default ALLOCATOR template parameter for both aliases as we intend to provide memory with bslma-style allocators:

    // PRIVATE TYPES
    typedef bsl::map<double, int> SellOrdersMap;
        // This `typedef` is an alias for a mapping between the price and
        // quantity of an order in ascending price order.
 
    typedef bsl::map<double, int, std::greater<double> > BuyOrdersMap;
        // This `typedef` is an alias for a mapping between the price and
        // quantity of an order in descending price order.
 
 
    // DATA
    SellOrdersMap   d_sellOrders;  // current sell orders
    BuyOrdersMap    d_buyOrders;   // current buy orders
 
  private:
    // NOT IMPLEMENTED
    TradeMatcher& operator=(const TradeMatcher&);
    TradeMatcher(const TradeMatcher&);
 
  public:
    // PUBLIC TYPES
    typedef SellOrdersMap::const_iterator SellOrdersConstIterator;
        // This `typedef` provides an alias for the type of an iterator
        // providing non-modifiable access to sell orders in a
        // `TradeMatcher`.
 
    typedef BuyOrdersMap::const_iterator BuyOrdersConstIterator;
        // This `typedef` provides an alias for the type of an iterator
        // providing non-modifiable access to buy orders in a
        // `TradeMatcher`.
 
    // CREATORS
    TradeMatcher(bslma::Allocator *basicAllocator = 0);
        // Create an empty `TradeMatcher` object.  Optionally specify a
        // `basicAllocator` used to supply memory.  If `basicAllocator` is
        // 0, the currently installed default allocator is used.
 
    //! ~TradeMatcher() = default;
        // Destroy this object.
 
    // MANIPULATORS
    void placeBuyOrder(double price, int numShares);
        // Place an order to buy the specified `numShares` at the specified
        // `price`.  The placed buy order will (possibly partially) execute
        // when active sale orders exist in the system at or below `price`.
        // The behavior is undefined unless `0 < price` and `0 <
        // numShares`.
 
    void placeSellOrder(double price, int numShares);
        // Place an order to sell the specified `numShares` at the
        // specified `price`.  The placed sell order will (possibly
        // partially) execute when active buy orders exist in the system at
        // or above `price`.  The behavior is undefined unless `0 < price`
        // and `0 < numShares`.
 
    // ACCESSORS
    SellOrdersConstIterator beginSellOrders() const;
        // Return an iterator providing non-modifiable access to the active
        // sell order at the lowest price in the ordered sequence (from low
        // price to high price) of sell orders maintained by this object.
 
    SellOrdersConstIterator endSellOrders() const;
        // Return an iterator providing non-modifiable access to the
        // past-the-end sell order in the ordered sequence (from low price
        // to high price) of sell orders maintained by this object.
 
    BuyOrdersConstIterator beginBuyOrders() const;
        // Return an iterator providing non-modifiable access to the active
        // buy order at the highest price in the ordered sequence (from
        // high price to low price) of buy orders maintained by this
        // object.
 
    BuyOrdersConstIterator endBuyOrders() const;
        // Return an iterator providing non-modifiable access to the
        // past-the-end buy order in the ordered sequence (from high price
        // to low price) of buy orders maintained by this object.
};

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

// CREATORS
TradeMatcher::TradeMatcher(bslma::Allocator *basicAllocator)
: d_sellOrders(basicAllocator)
, d_buyOrders(basicAllocator)
{
}

Notice that, on construction, we pass the contained bsl::map objects the bsl::Allocator supplied at construction'.

// MANIPULATORS
void TradeMatcher::placeBuyOrder(double price, int numShares)
{
    BSLS_ASSERT(0 < price);
    BSLS_ASSERT(0 < numShares);
 
    // Buy shares from sellers from the one with the lowest price up to but
    // not including the first seller with a price greater than the
    // specified `price`.
 
    SellOrdersMap::iterator itr = d_sellOrders.begin();
 
    while (numShares && itr != d_sellOrders.upper_bound(price)) {
        if (itr->second > numShares) {
            itr->second -= numShares;
            numShares = 0;
            break;
        }
 
        itr = d_sellOrders.erase(itr);
        numShares -= itr->second;
    }
 
    if (numShares > 0) {
        d_buyOrders[price] += numShares;
    }
}
 
void TradeMatcher::placeSellOrder(double price, int numShares)
{
    BSLS_ASSERT(0 < price);
    BSLS_ASSERT(0 < numShares);
 
    // Sell shares to buyers from the one with the highest price up to but
    // not including the first buyer with a price smaller than the
    // specified `price`.
 
    BuyOrdersMap::iterator itr = d_buyOrders.begin();
 
    while (numShares && itr != d_buyOrders.upper_bound(price)) {
        if (itr->second > numShares) {
            itr->second -= numShares;
            numShares = 0;
            break;
        }
 
        itr = d_buyOrders.erase(itr);
        numShares -= itr->second;
    }
 
    if (numShares > 0) {
        d_sellOrders[price] += numShares;
    }
}
 
// ACCESSORS
TradeMatcher::SellOrdersConstIterator TradeMatcher::beginSellOrders() const
{
    return d_sellOrders.begin();
}
 
TradeMatcher::SellOrdersConstIterator TradeMatcher::endSellOrders() const
{
    return d_sellOrders.end();
}
 
TradeMatcher::BuyOrdersConstIterator TradeMatcher::beginBuyOrders() const
{
    return d_buyOrders.begin();
}
 
TradeMatcher::BuyOrdersConstIterator TradeMatcher::endBuyOrders() const
{
    return d_buyOrders.end();
}