bslstl_unorderedmapkeyconfiguration.h

Go to the documentation of this file.

/// @file bslstl_unorderedmapkeyconfiguration.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_unorderedmapkeyconfiguration.h                              -*-C++-*-
#ifndef INCLUDED_BSLSTL_UNORDEREDMAPKEYCONFIGURATION
#define INCLUDED_BSLSTL_UNORDEREDMAPKEYCONFIGURATION
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_unorderedmapkeyconfiguration bslstl_unorderedmapkeyconfiguration
/// @brief  Provide a class template to extract keys as the `first` attribute.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_unorderedmapkeyconfiguration
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_unorderedmapkeyconfiguration-purpose"> Purpose</a>
/// * <a href="#bslstl_unorderedmapkeyconfiguration-classes"> Classes </a>
/// * <a href="#bslstl_unorderedmapkeyconfiguration-description"> Description </a>
///   * <a href="#bslstl_unorderedmapkeyconfiguration-usage"> Usage </a>
///     * <a href="#bslstl_unorderedmapkeyconfiguration-example-1-using-multiple-extractors-to-sort-an-array-on-different-keys"> Example 1: Using Multiple Extractors to Sort an Array on Different Keys </a>
///
/// # Purpose {#bslstl_unorderedmapkeyconfiguration-purpose}
/// Provide a class template to extract keys as the `first` attribute.
///
/// # Classes {#bslstl_unorderedmapkeyconfiguration-classes}
///
/// -   bslalg::UnorderedMapKeyConfiguration : extracts `key` from `value` type
///
/// @see  bslalg_hashtableimputil
///
/// # Description {#bslstl_unorderedmapkeyconfiguration-description}
/// This component will, given an object of a value type consisting
/// of a key type and some other information, return a const reference to only
/// the key type within that object.  The object passed will be of parameterized
/// type `VALUE_TYPE`, for which a type `VALUE_TYPE::first_type` must be
/// defined and be of the key type, and for which the operation `.first` must be
/// defined and must yield the object of the key type.
///
/// `bslalg::HashTableImpUtil` has a static `extractKey` function template that,
/// given a `value type`, will represent objects stored in a data structure,
/// will abstract out the `key type` portion of that object.  In the case of the
/// `unordered_map` data structure, the `value type` will be `bsl::pair`, and
/// the key type will `bsl::pair::first_type`.
///
/// ## Usage {#bslstl_unorderedmapkeyconfiguration-usage}
///
///
/// This section illustrates intended use of this component.
///
/// ### Example 1: Using Multiple Extractors to Sort an Array on Different Keys {#bslstl_unorderedmapkeyconfiguration-example-1-using-multiple-extractors-to-sort-an-array-on-different-keys}
///
///
/// Suppose we want to define a `sort` function which will work on a variety
/// of different object types.  The object has to have a `key` within it,
/// possibly the whole object, which will compare with the `key` of other
/// objects with a transitive `<` operator.
///
/// First, we define our function `mySort`, which takes two template args:
/// `VALUE_TYPE`, the type of object being sorted, and `KEY_EXTRACTOR`, the
/// utility class that will extra which part of the objects to be sorted is the
/// key which will drive the sort:
/// @code
/// // This function provides an order-preserving sort of the items in the
/// // range `[begin .. end)`, where `KEY_EXTRACTOR::extractKey` yields the
/// // key being sorted over.  We require that `VALUE_TYPE` support copy
/// // construction and assignment.
/// template <class VALUE_TYPE, class KEY_EXTRACTOR>
/// void mySort(VALUE_TYPE *begin, VALUE_TYPE *end, const KEY_EXTRACTOR&)
/// {
///     while (begin < --end) {
///         for (VALUE_TYPE *it = begin; it < end; ++it) {
///             if (KEY_EXTRACTOR::extractKey(it[1]) <
///                                         KEY_EXTRACTOR::extractKey(it[0])) {
///                 // they're in the wrong order -- swap them
///
///                 VALUE_TYPE tmp(it[0]);
///                 it[0] = it[1];
///                 it[1] = tmp;
///             }
///         }
///
///         // '*end' is now the highest element in the range '[begin .. end]',
///         // so we only have to sort the elements before it in the next pass.
///     }
/// }
/// @endcode
/// Then, we define `StudentRecord`, which keeps some vital statistics on
/// students:
/// @code
/// struct StudentRecord {
///     const char *d_name;
///     double      d_gpa;
///     int         d_age;
/// };
/// @endcode
/// Next, we define two extractors for `StudentRecord`, which will yield the
/// `GPA` or `Age` fields:
/// @code
/// struct StudentRecordGPAExtractor {
///     static
///     const double& extractKey(const StudentRecord& record)
///     {
///         return record.d_gpa;
///     }
/// };
///
/// struct StudentRecordAgeExtractor {
///     static
///     const int& extractKey(const StudentRecord& record)
///     {
///         return record.d_age;
///     }
/// };
/// @endcode
/// Then, in `main`, we create an array of `StudentRecord`s describing a set of
/// students, with their names, GPA's, and ages.
/// @code
/// StudentRecord studentArray[] = {
///     { "Phil",  3.4, 19 },
///     { "Bob",   2.7, 20 },
///     { "Bill",  4.2, 21 },
///     { "Stan",  1.9, 18 },
///     { "Ann",   2.3, 21 },
///     { "Julie", 2.3, 20 } };
/// const int NUM_STUDENTS = sizeof studentArray / sizeof *studentArray;
/// @endcode
/// Next, using our GPA extractor and our `mySort` function, we sort the
/// students by GPA:
/// @code
/// StudentRecordGPAExtractor gpaExtractor;
///
/// mySort(studentArray + 0,
///        studentArray + NUM_STUDENTS,
///        gpaExtractor);
/// @endcode
/// Then, we print out the sorted array of students:
/// @code
/// if (verbose) {
///     printf("\nList of students, lowest GPA first:\n");
///     printf(  "===================================\n");
///
///     printf("Name   GPA  AGE\n"
///            "-----  ---  ---\n");
///     for (int i = 0; i < NUM_STUDENTS; ++i) {
///         const StudentRecord& record = studentArray[i];
///
///         printf("%-5s  %g  %3d\n", record.d_name,
///                                   record.d_gpa,
///                                   record.d_age);
///     }
/// }
/// @endcode
/// The output produced is:
/// @code
/// List of students, lowest GPA first:
/// ===================================
///                             Name   GPA  AGE
/// -----  ---  ---
/// Stan   1.9   18
/// Ann    2.3   21
/// Julie  2.3   20
/// Bob    2.7   20
/// Phil   3.4   19
/// Bill   4.2   21
/// @endcode
/// Note that Ann and Julie, who have the same GPA, are still in the same order
/// as they were before the sort, as `mySort` was an order-preserving sort:
///
/// Next, we sort by age with our age extractor, and print out the results:
/// @code
/// StudentRecordAgeExtractor ageExtractor;
///
/// mySort(studentArray + 0,
///        studentArray + NUM_STUDENTS,
///        ageExtractor);
///
/// if (verbose) {
///     printf("\nList of students, youngest first:\n");
///     printf(  "================================\n");
///
///     printf("Name   GPA  AGE\n"
///            "-----  ---  ---\n");
///     for (int i = 0; i < NUM_STUDENTS; ++i) {
///         const StudentRecord& record = studentArray[i];
///
///         printf("%-5s  %g  %3d\n", record.d_name,
///                                   record.d_gpa,
///                                   record.d_age);
///     }
/// }
/// @endcode
/// The output is:
/// @code
/// List of students, youngest first:
/// ================================
///                             Name   GPA  AGE
/// -----  ---  ---
/// Stan   1.9   18
/// Phil   3.4   19
/// Julie  2.3   20
/// Bob    2.7   20
/// Ann    2.3   21
/// Bill   4.2   21
/// @endcode
/// Note again, the ordering of students with identical ages is preserved.
///
/// Then, suppose we are storing information about employees in `MyPair`
/// objects, where `first` is a double storing the employees hourly wage, and
/// `second` in the employee's name.  Suppose we want to sort the employees by
/// their hourly wages, which is the `.first` field of the pair.
///
/// We declare our employee pair type:
/// @code
/// typedef MyPair<double, const char *> EmployeePair;
/// @endcode
/// Next, we define an array of employee pairs for employees' wages and names:
/// @code
/// EmployeePair employees[] = {
///     { 12.25, "Kyle" },
///     { 15.00, "Eric" },
///     { 12.25, "Stan" },
///     {  7.75, "Kenny" } };
/// const int NUM_EMPLOYEES = sizeof employees / sizeof *employees;
/// @endcode
/// Then, we create an `UnorderedMapKeyConfiguration` type parameterized on
/// `EmployeePair`, which will extract the `.first` field, which is the wage,
/// from an employee pair:
/// @code
/// bslstl::UnorderedMapKeyConfiguration<EmployeePair> wageExtractor;
/// @endcode
/// Next, we sort:
/// @code
/// mySort(employees + 0, employees + NUM_EMPLOYEES, wageExtractor);
/// @endcode
/// Now, we print out our results:
/// @code
/// if (verbose) {
///     printf("\nList of employees, cheapest first:\n"
///              "==================================\n");
///
///     printf("Name   Wage\n"
///            "-----  -----\n");
///
///     for (int i = 0; i < NUM_EMPLOYEES; ++i) {
///         const EmployeePair& employee = employees[i];
///
///         printf("%-5s  %5.2f\n", employee.second, employee.first);
///     }
/// }
/// @endcode
/// Finally, we see our output.  Note that the ordering of Kyle and Stan, who
/// are paid the same wage, is preserved.
/// @code
/// List of employees, cheapest first:
/// ==================================
///                             Name   Wage
/// -----  -----
/// Kenny   7.75
/// Kyle   12.25
/// Stan   12.25
/// Eric   15.00
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_unorderedmapkeyconfiguration
 * @{
 */
 
#include <bslscm_version.h>
 
 
namespace bslstl {
 
                      // ===================================
                      // struct UnorderedMapKeyConfiguration
                      // ===================================
 
template <class KEY, class VALUE_TYPE>
struct UnorderedMapKeyConfiguration {
  public:
    typedef   VALUE_TYPE    ValueType;
    typedef   KEY           KeyType;
 
    // Choosing to implement for each configuration, to reduce the template
    // mess.  With only two policies, not much is saved using a shared
    // dependent base class to provide a common implementation.  This is the
    // key abstraction, turning 'bslalg::BidirectionalLink*' into 'VALUE_TYPE&'
 
    // CLASS METHODS
 
    /// Return the member `first` of the specified object `obj`.
    /// `obj.first` must be of type `VALUE_TYPE::first_type`, which is the
    /// `key` portion of `obj`.
    static const KeyType& extractKey(const VALUE_TYPE& obj);
};
 
// ============================================================================
//                  TEMPLATE AND INLINE FUNCTION DEFINITIONS
// ============================================================================
 
                       //-----------------------------------
                       // class UnorderedMapKeyConfiguration
                       //-----------------------------------
 
// CLASS METHODS
template <class KEY, class VALUE_TYPE>
inline
const KEY&
UnorderedMapKeyConfiguration<KEY, VALUE_TYPE>::extractKey(const VALUE_TYPE& obj)
{
    return obj.first;
}
 
}  // close package namespace
 
 
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2013 Bloomberg Finance L.P.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// ----------------------------- END-OF-FILE ----------------------------------
 
/** @} */
/** @} */
/** @} */