bslstl_set

Detailed Description

Outline

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

Purpose

Provide an STL-compliant set class.

Classes

• bsl::set: STL-compatible set template

Canonical header: bsl_set.h

See also

bslstl_multiset, bslstl_map

Description

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

An instantiation of set is an allocator-aware, value-semantic type whose salient attributes are its size (number of keys) and the ordered sequence of keys the set contains. If set 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 set containing that type cannot be tested for equality. It is even possible to instantiate set with a key type that does not have a copy-constructor, in which case the set will not be copyable.

A set meets the requirements of an associative container with bidirectional iterators in the C++ standard [23.2.4]. The set 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 set is a fully "Value-Semantic Type" (see bsldoc_glossary ) only if the supplied KEY template parameters is fully value-semantic. It is possible to instantiate a set with KEY 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 set 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 set instantiation, the requirements apply specifically to the set's entry type, value_type, which is an alias for KEY.

Glossary

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

Operations

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

Legend
------
'K'             - (template parameter) type 'KEY' of the set
'a', 'b'        - two distinct objects of type 'set<K>'
'rv'            - modifiable rvalue of type 'set<K>'
'n', 'm'        - number of elements in 'a' and 'b' respectively
'c'             - comparator providing an ordering for objects of type 'K'
'al             - an STL-style memory allocator
'i1', 'i2'      - two iterators defining a sequence of 'value_type' objects
'k'             - an object of type 'K'
'rk'            - modifiable rvalue of type 'K'
'p1', 'p2'      - two 'const' iterators belonging to 'a'
distance(i1,i2) - the number of elements in the range [i1, i2)
 
+----------------------------------------------------+--------------------+
| Operation                                          | Complexity         |
+====================================================+====================+
| set<K> a;    (default construction)                | O[1]               |
| set<K> a(al);                                      |                    |
| set<K> a(c, al);                                   |                    |
+----------------------------------------------------+--------------------+
| set<K> a(rv); (move construction)                  | O[1] if 'a' and    |
| set<K> a(rv, al);                                  | 'rv' use the same  |
|                                                    | allocator,         |
|                                                    | O[n] otherwise     |
+----------------------------------------------------+--------------------+
| set<K> a(b); (copy construction)                   | O[n]               |
| set<K> a(b, al);                                   |                    |
+----------------------------------------------------+--------------------+
| set<K> a(i1, i2);                                  | O[N] if [i1, i2)   |
| set<K> a(i1, i2, al);                              | is sorted with     |
| set<K> a(i1, i2, c, al);                           | 'a.value_comp()',  |
|                                                    | O[N * log(N)]      |
|                                                    | otherwise, where N |
|                                                    | is distance(i1,i2) |
+----------------------------------------------------+--------------------+
| a.~set<K>(); (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(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(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.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 Holiday Calendar

In this example, we will utilize bsl::set to define and implement a class, HolidayCalendar, that provides a calendar that allows client to add and remove holiday dates and determine whether a particular date is a holiday.

First, we define and implement the methods of a value-semantic type, MyDate, that represents a date: (Note that for brevity, we do not explicitly document the invariants of a valid date.)

/// This class implements a value-semantic attribute class
/// characterizing a date according to the (Gregorian) Unix date
/// convention.
class MyDate {
 
    // DATA
    int d_year;
    int d_month;
    int d_day;
 
  public:
    // CREATORS
 
    /// Create a `MyDate` object having the value represented by the
    /// specified `year`, `month`, and `day`.  The behavior is undefined
    /// unless the value represented by `year`, `month`, and `day` is
    /// valid.
    MyDate(int year, int month, int day)
    : d_year(year), d_month(month), d_day(day)
    {
    }
 
    /// Create a `MyDate` object having the same value as the specified
    /// `original` object.
    MyDate(const MyDate& original)
    : d_year(original.d_year)
    , d_month(original.d_month)
    , d_day(original.d_day)
    {
    }
 
    /// Destroy this object
    //! ~MyDate() = default;
 
    // MANIPULATORS
 
    /// Assign to this object the value of the specified `rhs` object,
    /// and return a reference providing modifiable access to this
    /// object.
    MyDate& operator=(const MyDate& rhs)
    {
        d_year = rhs.d_year;
        d_month = rhs.d_month;
        d_day = rhs.d_day;
        return *this;
    }
 
    // ACCESSORS
 
    /// Return the year of this date.
    int year() const
    {
        return d_year;
    }
 
    /// Return the month of this date.
    int month() const
    {
        return d_month;
    }
 
    /// Return the day of this date.
    int day() const
    {
        return d_day;
    }
 
};
 
// FREE FUNCTIONS
 
/// Return `true` if the specified `lhs` and `rhs` objects have the same
/// value, and `false` otherwise.  Two `MyDate` objects have the same
/// value if each of their corresponding `year`, `month`, and `day`
/// attributes respective have the same value.
inline
bool operator==(const MyDate& lhs, const MyDate& rhs)
{
    return lhs.year()  == rhs.year() &&
           lhs.month() == rhs.month() &&
           lhs.day()   == rhs.day();
}
 
/// Return `true` if the specified `lhs` and `rhs` objects do not have
/// the same value, and `false` otherwise.  Two `MyDate` objects do not
/// have the same value if each of their corresponding `year`, `month`,
/// and `day` attributes respective do not have the same value.
inline
bool operator!=(const MyDate& lhs, const MyDate& rhs)
{
    return !(lhs == rhs);
}

Then, we define a comparison functor for MyDate objects in order for them to be stored in a bsl::set object:

/// This `struct` defines an ordering on `MyDate` objects, allowing them
/// to be included in associative containers such as `bsl::set`.
struct MyDateLess {
 
    /// 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 date represented by `lhs` is earlier than the date
    /// represented by `rhs` in time.
    bool operator() (const MyDate& lhs, const MyDate& rhs) const
    {
        if (lhs.year() < rhs.year()) return true;
        if (lhs.year() == rhs.year()) {
            if (lhs.month() < rhs.month()) return true;
            if (lhs.month() == rhs.month()) {
                if (lhs.day() < rhs.day()) return true;
            }
        }
        return false;
    }
};

Next, we define HolidayCalendar:

/// This class provides a value-semantic type that allows clients to
/// modify and query a set of dates considered to be holidays.
class HolidayCalendar {

Here, we create a type alias, DateSet, for a bsl::set that will serve as the data member for a HolidayCalendar. A DateSet has keys of type MyDate, and a comparator of type MyDateLess. We use the default ALLOCATOR template parameter as we intend to use HolidayCalendar with bslma style allocators:

    // PRIVATE TYPES
 
    /// This `typedef` is an alias for a set of `MyDate` objects.
    typedef bsl::set<MyDate, MyDateLess> DateSet;
 
    // DATA
    DateSet d_holidayDates;  // set of dates considered to be holidays
 
  public:
    // PUBLIC TYPES
 
    /// This `typedef` provides an alias for the type of an iterator
    /// providing non-modifiable access to holiday dates in a
    /// `HolidayCalendar`.
    typedef DateSet::const_iterator ConstIterator;
 
    // CREATORS
 
    /// Create an empty `HolidayCalendar` object.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is
    /// 0, the currently installed default allocator is used.
    HolidayCalendar(bslma::Allocator *basicAllocator = 0);
 
    /// Create a `HolidayCalendar` 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.
    HolidayCalendar(const HolidayCalendar&  original,
                    bslma::Allocator       *basicAllocator = 0);
 
    /// Destroy this object.
    //! ~HolidayCalendar() = default;
 
    // MANIPULATORS
 
    /// Add the specified `date` as a holiday date maintained by this
    /// calendar.  If `date` is already a holiday date, this method has
    /// no effect.
    void addHolidayDate(const MyDate& date);
 
    /// Remove the specify `date` from the set of holiday dates
    /// maintained by this calendar.  If `date` is not a holiday date,
    /// this method has no effect.
    void removeHolidayDate(const MyDate& date);
 
    // ACCESSORS
 
    /// Return `true` if the specified `date` is in the set of holiday
    /// dates maintained by this calendar, and return `false` otherwise.
    bool isHolidayDate(const MyDate& date) const;
 
    /// Return an iterator providing non-modifiable access to the first
    /// date in the ordered sequence of holiday dates maintained by this
    /// calendar.
    ConstIterator beginHolidayDates() const;
 
    /// Return an iterator providing non-modifiable access to
    /// past-the-end date in the ordered sequence of holiday dates
    /// maintained by this calendar.
    ConstIterator endHolidayDates() const;
};

Then, we declare the free operators for HolidayCalendar:

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

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

// CREATORS
HolidayCalendar::HolidayCalendar(bslma::Allocator *basicAllocator)
: d_holidayDates(basicAllocator)
{
}

Notice that, on construction, we pass the bsl::set object the specified bsl::Allocator object.

// MANIPULATORS
void HolidayCalendar::addHolidayDate(const MyDate& date)
{
    d_holidayDates.insert(date);
}
 
void HolidayCalendar::removeHolidayDate(const MyDate& date)
{
    d_holidayDates.erase(date);
}
 
// ACCESSORS
bool HolidayCalendar::isHolidayDate(const MyDate& date) const
{
    return d_holidayDates.find(date) != d_holidayDates.end();
}
 
HolidayCalendar::ConstIterator HolidayCalendar::beginHolidayDates() const
{
    return d_holidayDates.begin();
}
 
HolidayCalendar::ConstIterator HolidayCalendar::endHolidayDates() const
{
    return d_holidayDates.end();
}

Finally, we implement the free operators for HolidayCalendar:

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