bslstl_list.h

Go to the documentation of this file.

/// @file bslstl_list.h
///
/// The content of this file has been pre-processed for Doxygen.
///
 
 
// bslstl_list.h                                                      -*-C++-*-
#ifndef INCLUDED_BSLSTL_LIST
#define INCLUDED_BSLSTL_LIST
 
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
 
/// @defgroup bslstl_list bslstl_list
/// @brief  Provide an STL-compliant list class.
/// @addtogroup bsl
/// @{
/// @addtogroup bslstl
/// @{
/// @addtogroup bslstl_list
/// @{
///
/// <h1> Outline </h1>
/// * <a href="#bslstl_list-purpose"> Purpose</a>
/// * <a href="#bslstl_list-classes"> Classes </a>
/// * <a href="#bslstl_list-description"> Description </a>
///   * <a href="#bslstl_list-requirements-on-value"> Requirements on VALUE </a>
///   * <a href="#bslstl_list-memory-allocation"> Memory Allocation </a>
///     * <a href="#bslstl_list-bslma-style-allocators"> bslma-Style Allocators </a>
///     * <a href="#bslstl_list-comparators-and-strict-weak-ordering"> Comparators and Strict Weak Ordering </a>
///   * <a href="#bslstl_list-glossary"> Glossary </a>
///   * <a href="#bslstl_list-operations"> Operations </a>
///   * <a href="#bslstl_list-usage"> Usage </a>
///     * <a href="#bslstl_list-example-1-filter-twinkle-star"> Example 1: Filter "Twinkle Star" </a>
///     * <a href="#bslstl_list-example-2-combine-two-star-surveys"> Example 2: Combine Two Star Surveys </a>
///
/// # Purpose {#bslstl_list-purpose}
/// Provide an STL-compliant list class.
///
/// # Classes {#bslstl_list-classes}
///
/// -   bsl::list: STL-compatible list template
///
/// **Canonical header:**  bsl_list.h
///
/// @see  bslstl_deque
///
/// # Description {#bslstl_list-description}
/// This component defines a single class template, `bsl::list`,
/// implementing the standard container holding a sequence of elements (of a
/// template parameter type, `VALUE`).  All list operations involving a single
/// element are constant-time, including insertion and removal of an element
/// anywhere in the list.  Operations that do not change the number of elements
/// are performed without calling constructors, destructors, swap, or assignment
/// on the individual elements.  (I.e., they are performed by
/// pointer-manipulation alone.)  A `list` does not provide random access to its
/// elements; although access to the first and last elements of a `list` is
/// constant-time, other elements can be accessed only by traversing the list
/// (forwards or backwards) from the beginning or end.
///
/// An instantiation of `list` is an allocator-aware, in-core value-semantic
/// type whose salient attributes are its size (number of elements) and the
/// sequence of its contained element values (in order).  If `list` is
/// instantiated with a type that is not itself value-semantic, then it will not
/// retain all of its value-semantic qualities.  In particular, if a type cannot
/// be tested for equality, then a `list` containing that type cannot be tested
/// for equality.  It is even possible to instantiate `list` with a type that
/// does not have a copy-constructor, in which case the `list` will not be
/// copyable.
///
/// A `list` meets the requirements of a sequence container with bidirectional
/// iterators in the C++ standard [23.3].  The `list` 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 VALUE {#bslstl_list-requirements-on-value}
///
///
/// A `list` is a fully Value-Semantic Type (see @ref bsldoc_glossary ) only if
/// the supplied `VALUE` template parameter is itself fully value-semantic.  It
/// is possible to instantiate a `list` with a `VALUE` 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 `list` to describe a function's requirements for the
/// `VALUE` template parameter.  These terms are also defined in sections
/// [utility.arg.requirements] and [container.requirements.general] of the C++11
/// standard.
///
/// ## Memory Allocation {#bslstl_list-memory-allocation}
///
///
/// The type supplied as a list's `ALLOCATOR` template parameter determines how
/// that list will allocate memory.  The `list` 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 {#bslstl_list-bslma-style-allocators}
///
///
/// If the (template parameter) type `ALLOCATOR` of a `list` instantiation is
/// `bsl::allocator`, then objects of that list type will conform to the
/// standard behavior of a `bslma`-allocator-enabled type.  Such a list accepts
/// an optional `bslma::Allocator` argument at construction.  If the address of
/// a `bslma::Allocator` object is explicitly supplied at construction, the list
/// uses it to supply memory for the list throughout its lifetime; otherwise,
/// the list will use the default allocator installed at the time of the list's
/// construction (see @ref bslma_default ).  In addition to directly allocating
/// memory from the indicated `bslma::Allocator`, a list supplies that
/// allocator's address to the constructors of contained objects of the
/// (template parameter) `VALUE` type if it defines the
/// `bslma::UsesBslmaAllocator` trait.
///
/// ### Comparators and Strict Weak Ordering {#bslstl_list-comparators-and-strict-weak-ordering}
///
///
/// A comparator function `comp(a, b)` defines a *strict* *weak* *ordering* if
/// * `comp(a, b)` && `comp(b, c)` implies `comp(a, c)`
/// * `comp(a, b)` implies `!comp(b, a)`
/// * `!comp(a, b)` does not imply that `comp(b, a)`
///
/// ## Glossary {#bslstl_list-glossary}
///
///
/// @code
/// Legend
/// ------
/// 'X'    - denotes an allocator-aware container type (e.g., 'list')
/// '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
/// @endcode
/// 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.
///
/// ## Operations {#bslstl_list-operations}
///
///
/// This section describes the run-time complexity of operations on instances
/// of `list`:
/// @code
/// Legend
/// ------
/// 'V'             - template parameter 'VALUE' type of the list
/// 'A'             - template parameter 'ALLOCATOR' type of the list
/// 'a', 'b'        - distinct objects of type 'list<V>'
/// 'k'             - unsigned integral constant
/// 'ra','rb'       - distinct modifiable rvalue objects of type 'list<V>&&'
/// 'n', 'm'        - number of elements in 'a' and 'b', respectively
/// 'al'            - an STL-style memory allocator
/// 'i1', 'i2'      - two iterators defining a sequence of 'V' objects
/// 'v'             - an object of type 'V'
/// 'rv'            - modifiable rvalue object of type 'V&&'
/// 'p1', 'p2'      - two iterators belonging to 'a'
/// 's1', 's2'      - two iterators belonging to 'b'
/// 'pred'          - a unary predicate
/// 'binary_pred'   - a binary predicate
/// 'comp'          - a binary predicate implementing a strict-weak ordering
/// 'args...'       - a variadic list of (up to 10) arguments
/// '{*}'           - C++11-style initializer list of length 'ni'
/// distance(i1,i2) - the number of elements in the range '[i1 .. i2)'
///
/// +----------------------------------------------------+--------------------+
/// | Operation                                          | Complexity         |
/// +====================================================+====================+
/// | list<V> a;    (default construction)               | O[1]               |
/// | list<V> a(al);                                     |                    |
/// +----------------------------------------------------+--------------------+
/// | list<V> a(b); (copy construction)                  | O[m]               |
/// | list<V> a(b, al);                                  |                    |
/// +----------------------------------------------------+--------------------+
/// | list<V> a(rb); (move construction)                 | O[1]               |
/// | list<V> a(rb, al);                                 | O[1] if 'a' and 'b'|
/// |                                                    | use the same       |
/// |                                                    | allocator,         |
/// |                                                    | O[m]     otherwise |
/// +----------------------------------------------------+--------------------+
/// | list<V> a(k);                                      | O[k]               |
/// | list<V> a(k, v);                                   |                    |
/// | list<V> a(k, v, al);                               |                    |
/// +----------------------------------------------------+--------------------+
/// | list<V> a(i1, i2);                                 | O[distance(i1, i2)]|
/// | list<V> a(i1, i2, al);                             |                    |
/// +----------------------------------------------------+--------------------+
/// | list<V> a({*}, al = A())                           | O[ni]              |
/// +----------------------------------------------------+--------------------+
/// | a.~list<V>(); (destruction)                        | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a = b;                (copy assignment)            | O[max(n, m)]       |
/// +----------------------------------------------------+--------------------+
/// | a = {*};              (copy assignment)            | O[max(n, ni)]      |
/// +----------------------------------------------------+--------------------+
/// | a = rb;               (move assignment)            | O[1] if 'a' and 'b'|
/// |                                                    | use the same       |
/// |                                                    | allocator,         |
/// |                                                    | O[max(n, m)]       |
/// |                                                    | otherwise          |
/// +----------------------------------------------------+--------------------+
/// | 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]               |
/// +----------------------------------------------------+--------------------+
/// | a.get_allocator()                                  | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.emplace(p1, args...)                             | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.insert(p1, v)                                    | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.insert(p1, k, v)                                 | O[k]               |
/// +----------------------------------------------------+--------------------+
/// | a.insert(p1, i1, i2)                               | O[distance(i1, i2)]|
/// +----------------------------------------------------+--------------------+
/// | a.insert(p1, rv)                                   | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.insert(p1, {*})                                  | O[ni]              |
/// +----------------------------------------------------+--------------------|
/// | a.erase(p1)                                        | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.erase(p1, p2)                                    | O[distance(p1, p2)]|
/// +----------------------------------------------------+--------------------+
/// | a.clear()                                          | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a.assign(i1,i2)                                    | O[distance(i1, i2)]|
/// +----------------------------------------------------+--------------------+
/// | a.assign(k, v)                                     | O[max(n, k)]       |
/// +----------------------------------------------------+--------------------+
/// | a.assign({*})                                      | O[max(n, ni)]      |
/// +----------------------------------------------------+--------------------+
/// | a.front(), a.back()                                | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.emplace_front(args...), a.emplace_back(args...)  | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.push_front(v),                                   |                    |
/// | a.push_back(v)                                     | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.push_front(rv),                                  |                    |
/// | a.push_back(rv)                                    | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.pop_front(), a.pop_back()                        | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.resize(k), a.resize(k, v)                        | O[k]               |
/// +----------------------------------------------------+--------------------+
/// | a.splice(p, b),  a.splice(p, b, s1)                | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.splice(p, rb), a.splice(p, rb, s1)               | O[1]               |
/// +----------------------------------------------------+--------------------+
/// | a.splice(p, b, s1, s2)                             | O[distance(s1, s2)]|
/// +----------------------------------------------------+--------------------+
/// | a.splice(p, rb, s1, s2)                            | O[distance(s1, s2)]|
/// +----------------------------------------------------+--------------------+
/// | a.remove(t), a.remove_if(pred)                     | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a.unique(), a.unique(binary_pred)                  | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a.merge(b),  a.merge(b, comp)                      | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a.merge(rb), a.merge(rb, comp)                     | O[n]               |
/// +----------------------------------------------------+--------------------+
/// | a.sort(), a.sort(comp)                             | O[n*log(n)]        |
/// +----------------------------------------------------+--------------------+
/// | a.reverse()                                        | O[n]               |
/// +----------------------------------------------------+--------------------+
/// @endcode
///
/// ## Usage {#bslstl_list-usage}
///
///
/// This section illustrates intended usage of this component.
///
/// ### Example 1: Filter "Twinkle Star" {#bslstl_list-example-1-filter-twinkle-star}
///
///
/// Suppose an observatory needs to analyze the results of a sky survey.  The
/// raw data is a text file of star observations where each star is represented
/// by a tuple of three numbers: (x, y, b), where x and y represent the angular
/// coordinates of the star in the sky and b represents its brightness on a
/// scale of 0 to 100.  A star having brightness 75 or higher is of particular
/// interest, which is called "twinkle star".
///
/// Our first example will read such a data file as described above, filter out
/// the dim stars (brightness less than 75), and count the twinkle stars left
/// in the list.  Our test data set has been selected such that there are 10
/// stars in the set, of which 4 are sufficiently bright as to pass our filter.
///
/// First, we define the class `Star` that encapsulates a single tuple, and
/// provides accessors functions `x`, `y`, and `brightness`, file I/O functions
/// `read` and `write`, and free operators `==`, `!=`, and `<`:
/// @code
/// #include <cstdio>
/// using namespace std;
///
/// /// This class represents a star as seen through a digital telescope.
/// class Star
/// {
///     // DATA
///     double d_x, d_y;     // coordinates
///
///     int    d_brightness; // brightness on a scale of 0 to 100
///
/// public:
///     // CREATORS
///
///     /// Create a `Star` object located at coordinates `(0, 0)` having
///     /// `0` brightness.
///     Star()
///     : d_x(0), d_y(0), d_brightness(0)
///     {
///     }
///
///     /// Create a `Star` object located at the specified coordinates
///     /// `(x, y)` having the specified `b` brightness.
///     Star(double x, double y, int b)
///     : d_x(x), d_y(y), d_brightness(b)
///     {
///     }
///
///     // Compiler-generated copy construction, assignment, and destructor
///     // Star(const Star&) = default;
///     // Star& operator=(const Star&) = default;
///     // ~Star() = default;
///
///     // MANIPULATORS
///
///     /// Read x, y, and brightness from the specified `input` file.
///     /// Return `true` if the read succeeded and `false` otherwise.
///     bool read(FILE *input);
///
///     /// Write x, y, and brightness to the specified `output` file
///     /// followed by a newline.
///     void write(FILE *output) const;
///
///     // ACCESSORS
///
///     /// Return the x coordinate of this `Star` object.
///     double x() const
///     {
///         return d_x;
///     }
///
///     /// Return the y coordinate of this `Star` object.
///     double y() const
///     {
///         return d_y;
///     }
///
///     /// Return the brightness of this `Star` object.
///     int brightness() const
///     {
///         return d_brightness;
///     }
/// };
///
/// // FREE FUNCTIONS
/// bool operator==(const Star& lhs, const Star& rhs);
/// bool operator!=(const Star& lhs, const Star& rhs);
/// bool operator< (const Star& lhs, const Star& rhs);
/// @endcode
/// Then, we define a `readData` method that reads a file of data points and
/// appends each onto a list.  The stars are stored in the data file in
/// ascending sorted order by x and y coordinates.
/// @code
/// void readData(list<Star> *starList, FILE *input)
/// {
///     Star s;
///     while (s.read(input)) {
///         starList->push_back(s);
///     }
/// }
/// @endcode
/// Now, we define the `filter` method, which is responsible for removing stars
/// with a brightness of less than 75 from the data set.  It does this by
/// iterating over the list and erasing any element that does not pass the
/// filter.  The list object features a fast `erase` member function.  The
/// return value of `erase` is an iterator to the element immediately following
/// the erased element:
/// @code
/// void filter(list<Star> *starList)
/// {
///     static const int threshold = 75;
///
///     list<Star>::iterator i = starList->begin();
///     while (i != starList->end()) {
///         if (i->brightness() < threshold) {
///             i = starList->erase(i);  // Erase and advance to next element.
///         }
///         else {
///             ++i;  // Advance to next element without erasing
///         }
///     }
/// }
/// @endcode
/// Finally, we use the methods defined in above steps to put together our
/// program to find twinkle stars:
/// @code
/// int usageExample1(int verbose)
/// {
///     FILE *input = fopen("star_data1.txt", "r");  // Open input file.
///     assert(input);
///
///     list<Star> starList;                         // Define a list of stars.
///     assert(starList.empty());                    // A list should be empty
///                                                  // after default
///                                                  // construction.
///
///     readData(&starList, input);                  // Read input to the list.
///     assert(10 == starList.size());               // Verify correct reading.
///     fclose(input);                               // Close input file.
///
///     filter(&starList);                           // Pick twinkle stars.
///     assert(4 == starList.size());                // Verify correct filter.
///
///     // Print out twinkle stars.
///     if (verbose) {
///         for (list<Star>::const_iterator i = starList.begin();
///              i != starList.end(); ++i) {
///             i->write(stdout);
///         }
///     }
///     return 0;
/// }
/// @endcode
///
/// ### Example 2: Combine Two Star Surveys {#bslstl_list-example-2-combine-two-star-surveys}
///
///
/// In the second example, we want to combine the results from two star surveys
/// into a single list, using the same `Star` class defined in the first usage
/// example.
///
/// First, we begin by reading both lists and filtering them.  (Our test data is
/// selected so that the second data file contains 8 stars of which 3 are
/// sufficiently bright as to pass our filter:
/// @code
/// int usageExample2(int verbose)
/// {
///     FILE *input = fopen("star_data1.txt", "r");  // Open first input file.
///     assert(input);
///
///     list<Star> starList1;                        // Define first star list.
///     assert(starList1.empty());
///
///     readData(&starList1, input);                 // Read input into list.
///     assert(10 == starList1.size());
///     fclose(input);                               // Close first input file.
///
///     input = fopen("star_data2.txt", "r");        // Open second input file.
///     assert(input);
///
///     list<Star> starList2;                        // Define second list.
///     assert(starList2.empty());
///
///     readData(&starList2, input);                 // Read input into list.
///     assert(8 == starList2.size());
///     fclose(input);                               // Close input file.
///
///     filter(&starList1);                          // Pick twinkle stars from
///                                                  // the first star list.
///     assert(4 == starList1.size());
///
///     filter(&starList2);                          // Pick twinkle stars from
///                                                  // the second star list.
///     assert(3 == starList2.size());
/// @endcode
/// Then, we combine the two lists, `starList1` and `starList2`.  One way to do
/// this is to simply insert the second list at the end of the first:
/// @code
///     list<Star> tmp1(starList1);  // Make a copy of the first list
///     list<Star> tmp2(starList2);  // Make a copy of the second list
///     tmp1.insert(tmp1.end(), tmp2.begin(), tmp2.end());
///     assert(7 == tmp1.size());    // Verify combined size.
///     assert(3 == tmp2.size());    // 'tmp2' should be unchanged.
/// @endcode
/// Next, let's have a closer look of the above code and see if we can improve
/// the combination performance.  The above `insert` method appends a copy of
/// each element in `tmp2` onto the end of `tmp1`.  This copy is unnecessary
/// because we have no need for `tmp2` after the lists have been combined.  A
/// faster and less-memory-intensive technique is to use the `splice` function,
/// which *moves* rather than *copies* elements from one list to another:
/// @code
///     tmp1 = starList1;
///     tmp2 = starList2;
///     tmp1.splice(tmp1.begin(), tmp2);
///     assert(7 == tmp1.size());    // Verify combined size.
///     assert(0 == tmp2.size());    // 'tmp2' should be emptied by the splice.
/// @endcode
/// Notice that, while the original lists were sorted in ascending order
/// (because the data files were originally sorted), the combined list is no
/// longer sorted.  To fix it, we sort `tmp1` using the `sort` member function:
/// @code
///     tmp1.sort();
/// @endcode
/// Then, we suggest a third, and also the best approach to combine two lists,
/// which is to take advantage of the fact that the lists were originally
/// sorted, using the `merge` function:
/// @code
///     starList1.merge(starList2);     // Merge 'starList2' into 'starList1'.
///     assert(7 == starList1.size());  // Verify combined size.
///     assert(0 == starList2.size());  // starList2 should be emptied by the
///                                     // merge.
/// @endcode
/// Now, since the two star surveys may overlap, we want to eliminate
/// duplicates.  We accomplish this by using the `unique` member function:
/// @code
///     starList1.unique();             // Eliminate duplicates in 'starList1'.
///     assert(6 == starList1.size());  // Verify size after elimination.
/// @endcode
/// Finally, we print the result:
/// @code
///     if (verbose) {
///         for (list<Star>::const_iterator i = starList1.begin();
///              i != starList1.end(); ++i) {
///             i->write(stdout);
///         }
///     }
///     return 0;
/// }
/// @endcode
/// For completeness, the implementations of the `read`, `write`, and comparison
/// functions for class `Star` are shown below:
/// @code
/// bool Star::read(FILE *input)
/// {
///     int ret = fscanf(input, "%lf %lf %d", &d_x, &d_y, &d_brightness);
///     return 3 == ret;
/// }
///
/// void Star::write(FILE *output) const
/// {
///     fprintf(output, "%f %f %d\n", d_x, d_y, d_brightness);
/// }
///
/// bool operator==(const Star& lhs, const Star& rhs)
/// {
///     return lhs.x() == rhs.x()
///         && lhs.y() == rhs.y()
///         && lhs.brightness() == rhs.brightness();
/// }
///
/// bool operator!=(const Star& lhs, const Star& rhs)
/// {
///     return ! (lhs == rhs);
/// }
///
/// bool operator<(const Star& lhs, const Star& rhs)
/// {
///     if (lhs.x() < rhs.x())
///         return true;
///     else if (rhs.x() < lhs.x())
///         return false;
///     else if (lhs.y() < rhs.y())
///         return true;
///     else if (rhs.y() < lhs.y())
///         return true;
///     else
///         return lhs.brightness() < rhs.brightness();
/// }
/// @endcode
/// @}
/** @} */
/** @} */
 
/** @addtogroup bsl
 * @{
 */
/** @addtogroup bslstl
 * @{
 */
/** @addtogroup bslstl_list
 * @{
 */
 
#include <bslscm_version.h>
 
#include <bslstl_algorithm.h>
#include <bslstl_iterator.h>
#include <bslstl_iteratorutil.h>
 
#include <bslalg_rangecompare.h>
#include <bslalg_synththreewayutil.h>
#include <bslalg_typetraithasstliterators.h>
 
#include <bslma_allocator.h>
#include <bslma_allocatortraits.h>
#include <bslma_allocatorutil.h>
#include <bslma_isstdallocator.h>
#include <bslma_bslallocator.h>
#include <bslma_usesbslmaallocator.h>
 
#include <bslmf_assert.h>
#include <bslmf_enableif.h>
#include <bslmf_isarithmetic.h>
#include <bslmf_isbitwisemoveable.h>
#include <bslmf_isconvertible.h>
#include <bslmf_isenum.h>
#include <bslmf_issame.h>
#include <bslmf_movableref.h>
#include <bslmf_nestedtraitdeclaration.h>
#include <bslmf_removecv.h>
#include <bslmf_typeidentity.h>
#include <bslmf_util.h>    // 'forward(V)'
 
#include <bsls_assert.h>
#include <bsls_compilerfeatures.h>
#include <bsls_keyword.h>
#include <bsls_libraryfeatures.h>
#include <bsls_performancehint.h>
#include <bsls_types.h>
#include <bsls_util.h>
 
#include <algorithm>   // for std::swap in C++03 or earlier
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
#include <initializer_list>
#endif
 
#include <utility>   // for std::swap in C++11 or later
 
#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
// Include version that can be compiled with C++03
// Generated on Thu Oct 21 10:11:37 2021
// Command line: sim_cpp11_features.pl bslstl_list.h
# define COMPILING_BSLSTL_LIST_H
# include <bslstl_list_cpp03.h>
# undef COMPILING_BSLSTL_LIST_H
#else
 
namespace bsl {
 
                        // =====================
                        // struct bsl::List_Node
                        // =====================
 
/// PRIVATE CLASS TEMPLATE.  For use only by `bsl::list` implementation.
/// An instance of `List_Node<T>` is a single node in a doubly-linked list
/// used to implement `bsl::list<T,A>`, for a given element type `T` and
/// allocator type `A`.  Note that an instantiation of this `class` for a
/// given `bsl::list` is independent of the allocator type.
///
/// See @ref bslstl_list 
template <class VALUE>
class List_Node {
 
    // DATA
    List_Node *d_prev_p;   // pointer to the previous node in the list
    List_Node *d_next_p;   // pointer to the next node in the list
    VALUE      d_value;    // list element
 
    // FRIENDS
    template <class LIST_VALUE, class LIST_ALLOCATOR>
    friend class list;
 
    template <class ITER_VALUE>
    friend class List_Iterator;
 
  private:
    // NOT IMPLEMENTED
    List_Node();                              // = delete;
    List_Node(const List_Node&);              // = delete;
    ~List_Node();                             // = delete;
    List_Node& operator=(const List_Node&);   // = delete;
 
    // A 'List_Node' is never constructed, copied, destroyed, or assigned to.
    // The 'd_value' field is constructed directly by 'list::emplace', and
    // destroyed directly by 'list::erase'.
};
 
                        // ========================
                        // class bsl::List_Iterator
                        // ========================
 
#if defined(BSLS_LIBRARYFEATURES_STDCPP_LIBCSTD)
// On Solaris studio12-v4, <algorithm> is compatible only with iterators
// inheriting from 'std::iterator'.
 
template <class VALUE>
class List_Iterator :
                 public std::iterator<std::bidirectional_iterator_tag, VALUE> {
#else
template <class VALUE>
class List_Iterator {
#endif
    // Implementation of 'bsl::list::iterator'.
 
    // PRIVATE TYPES
    typedef typename remove_cv<VALUE>::type  NcType;
    typedef List_Iterator<NcType>            NcIter;
    typedef List_Node<NcType>                Node;
 
    // DATA
    Node *d_node_p;      // pointer to list node
 
    // FRIENDS
    template <class LIST_VALUE, class LIST_ALLOCATOR>
    friend class list;
 
    template <class ITER_VALUE>    // This 'friend' statement is needed for the
    friend class List_Iterator;    // case where 'VALUE' != 'ITER_VALUE'.
 
    template <class T1, class T2>
    friend bool operator==(List_Iterator<T1>, List_Iterator<T2>);
 
  private:
    // PRIVATE ACCESSORS
 
    /// Return an iterator providing modifiable access to the list element
    /// that this list iterator refers to.
    NcIter unconst() const;
 
  public:
    // PUBLIC TYPES
    typedef std::bidirectional_iterator_tag   iterator_category;
    typedef NcType                            value_type;
    typedef BloombergLP::bsls::Types::IntPtr  difference_type;
    typedef VALUE                            *pointer;
    typedef VALUE&                            reference;
 
    // CREATORS
 
    /// Create a singular iterator (i.e., one that cannot be incremented,
    /// decremented, or dereferenced until assigned a non-singular value).
    List_Iterator();
 
    /// Create an iterator that references the value pointed to by the
    /// specified `nodePtr`.  If `0 == nodePtr` the iterator will be
    /// singular.
    explicit List_Iterator(Node *nodePtr);
 
    /// Create an iterator that has the same value as the specified `other`
    /// iterator.  If the (template parameter) type `VALUE` is not
    /// `const`-qualified, then this constructor is the copy constructor;
    /// otherwise, the copy constructor is implicitly generated.  Note that
    /// this method is marked "IMPLICIT" in case it is not the copy
    /// constructor.
    ///
    /// Note that this means that a `List_Iterator<const VALUE>` can be copy
    /// constructed or assigned to from a `List_Iterator<VALUE>`, but not
    /// vice-versa.
    List_Iterator(const NcIter& other);                             // IMPLICIT
 
    // Compiler-generated copy constructor, destructor, and copy-assignment
    // operator:
    //: o List_Iterator(const List_Iterator&); // Maybe defaulted (see above).
    //: o ~List_Iterator() = default;
    //: o List_Iterator& operator=(const List_Iterator&) = default;
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_DEFAULTED_FUNCTIONS)
    /// Default compiler-generated destructor.
    ~List_Iterator() = default;
 
    /// Default compiler-generated copy-assignment operator.
    List_Iterator& operator=(const List_Iterator&) = default;
#endif
 
    // MANIPULATORS
 
    /// Advance this iterator to the next element in the list and return its
    /// new value.  The behavior is undefined unless this iterator is in the
    /// range `[begin() .. end())` for some list (i.e., the iterator is not
    /// singular, is not `end()`, and has not been invalidated).
    List_Iterator& operator++();
 
    /// Regress this iterator to the previous element in the list and return
    /// its new value.  The behavior is undefined unless this iterator is in
    /// the range `(begin() .. end()]` for some list (i.e., the iterator is
    /// not singular, is not `begin()`, and has not been invalidated).
    List_Iterator& operator--();
 
    /// Advance this iterator to the next element in the list and return its
    /// previous value.  The behavior is undefined unless this iterator is
    /// in the range `[begin() .. end())` for some list (i.e., the iterator
    /// is not singular, is not `end()`, and has not been invalidated).
    List_Iterator operator++(int);
 
    /// Regress this iterator to the previous element in the list and return
    /// its previous value.  The behavior is undefined unless this iterator
    /// is in the range `(begin() .. end()]` for some list (i.e., the
    /// iterator is not singular, is not `begin()`, and has not been
    /// invalidated).
    List_Iterator operator--(int);
 
    // ACCESSORS
 
    /// Return a reference providing modifiable access to the element
    /// referenced by this iterator.  The behavior is undefined unless this
    /// iterator is in the range `[begin() .. end())` for some list (i.e.,
    /// the iterator is not singular, is not `end()`, and has not been
    /// invalidated).
    reference operator*() const;
 
    /// Return a pointer providing modifiable access to the element
    /// referenced by this iterator.  The behavior is undefined unless this
    /// iterator is in the range `[begin() .. end())` for some list (i.e.,
    /// the iterator is not singular, is not `end()`, and has not been
    /// invalidated).
    pointer operator->() const;
};
 
// FREE OPERATORS
 
/// Return `true` if the specified `lhs` and `rhs` iterators have the same
/// value, and `false` otherwise.  Two iterators have the same value if both
/// refer to the same element of the same list or both are the `end()`
/// iterator of the same list.  The behavior is undefined unless both `lhs`
/// and `rhs` refer to the same list.  Note that the different types `T1`
/// and `T2` are to facilitate comparisons between `const` and non-`const`
/// iterators and there will be a compilation error if `T1` and `T2` differ
/// in any way other than `const`-ness.
template <class T1, class T2>
bool operator==(List_Iterator<T1> lhs, List_Iterator<T2> rhs);
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
template <class T1, class T2>
bool operator!=(List_Iterator<T1> lhs, List_Iterator<T2> rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' iterators do not have the
    // same value, and 'false' otherwise.  Two iterators do not have the same
    // value unless both refer to the same element of the same list or unless
    // both are the 'end()' iterator of the same list.  The behavior is
    // undefined unless both 'lhs' and 'rhs' refer to the same list.  Note that
    // the different types 'T1' and 'T2' are to facilitate comparisons between
    // 'const' and non-'const' iterators and there will be a compilation error
    // if 'T1' and 'T2' differ in any way other than 'const'-ness.
#endif
 
                         // ===========================
                         // struct List_DefaultLessThan
                         // ===========================
 
/// Binary predicate type for comparing two `VALUE` objects using
/// `operator<`.  This operation is usually, but not always, the same as
/// that provided by `std::less<VALUE>`.  The standard requires that certain
/// functions use `operator<`, which means that divergent specializations of
/// `std::less` are to be ignored.
template <class VALUE>
struct List_DefaultLessThan {
 
    // ACCESSORS
 
    /// Return `true` if the value of the specified `lhs` is less than that
    /// of the specified `rhs`, and `false` otherwise.
    bool operator()(const VALUE& lhs, const VALUE& rhs) const;
};
 
                        // ==============================
                        // class List_AllocAndSizeWrapper
                        // ==============================
 
/// This struct is a wrapper around the allocator and size data members of a
/// `list`.  It takes advantage of the empty-base optimization (EBO) so that
/// if the allocator is stateless, it takes up no space.
///
/// TBD: This struct should eventually be replaced by the use of a general
/// EBO-enabled component that provides a `pair`-like interface.  (A
/// properly-optimized `tuple` would do the job.)
template <class VALUE, class ALLOCATOR>
class List_AllocAndSizeWrapper : public allocator_traits<ALLOCATOR>::
                    template rebind_traits<List_Node<VALUE> >::allocator_type {
 
    // PRIVATE TYPES
    typedef List_Node<VALUE>                      Node;
 
    /// Alias for the allocator traits type associated with the `bsl::list`
    /// container.
    typedef typename allocator_traits<ALLOCATOR>::template rebind_traits<Node>
                                                  AllocTraits;
 
    typedef typename AllocTraits::allocator_type  NodeAlloc;    // base class
 
    typedef typename AllocTraits::size_type       size_type;
 
    // DATA
    size_type d_size;      // Number of elements in the list (not including the
                           // sentinel).
 
  private:
    // NOT IMPLEMENTED
    List_AllocAndSizeWrapper(const List_AllocAndSizeWrapper&);
    List_AllocAndSizeWrapper& operator=(const List_AllocAndSizeWrapper&);
 
  public:
    // CREATORS
 
    /// Create an allocator and size wrapper having the specified
    /// `basicAllocator` and (initial) `size`.
    List_AllocAndSizeWrapper(const NodeAlloc& basicAllocator,
                             size_type        size);
 
    // ~List_AllocAndSizeWrapper() = default;
 
    // MANIPULATORS
 
    /// Return a reference providing modifiable access to the `size` field
    /// of this object.
    size_type& size();
 
    // ACCESSORS
 
    /// Return a reference providing non-modifiable access to the `size`
    /// field of this object.
    const size_type& size() const;
};
 
/// Forward declaration required by `List_NodeProctor`.
template <class VALUE, class ALLOCATOR>
class list;
 
                            // ======================
                            // class List_NodeProctor
                            // ======================
 
/// This class provides a proctor to free a node containing an uninitialized
/// `VALUE` object in the event that an exception is thrown.
///
/// See @ref bslstl_list 
template <class VALUE, class ALLOCATOR>
class List_NodeProctor {
 
    // PRIVATE TYPES
    typedef List_Node<VALUE>                      Node;
 
    /// Alias for the allocator traits type associated with the `bsl::list`
    /// container.
    typedef typename allocator_traits<ALLOCATOR>::template rebind_traits<Node>
                                                  AllocTraits;
 
  public:
    // PUBLIC TYPES
 
    // In C++11 'NodePtr' would be generalized as follows:
    // 'typedef pointer_traits<VoidPtr>::template rebind<List_Node> NodePtr;'
 
    typedef typename AllocTraits::pointer         NodePtr;
 
  private:
    // DATA
    list<VALUE, ALLOCATOR>  *d_list_p;  // list to proctor
    NodePtr                  d_node_p;  // node to free upon destruction
 
  private:
    // NOT IMPLEMENTED
    List_NodeProctor(const List_NodeProctor&);
    List_NodeProctor &operator=(const List_NodeProctor&);
 
  public:
    // CREATORS
 
    /// Create a node proctor object that will use the specified list
    /// `listPtr` to free the specified `nodePtr`.  The behavior is
    /// undefined unless `nodePtr` was allocated by the allocator of
    /// `*listPtr`.
    List_NodeProctor(list<VALUE, ALLOCATOR> *listPtr, NodePtr nodePtr);
 
    /// Destroy this node proctor, and free the node it contains unless the
    /// `release` method has been called before.  Note that the `d_value`
    /// field of the node is not destroyed.
    ~List_NodeProctor();
 
    // MANIPULATORS
 
    /// Detach the node contained in this proctor from the proctor.  After
    /// calling this `release` method, the proctor no longer frees any node
    /// upon its destruction.
    void release();
};
 
                            // ===============
                            // class bsl::list
                            // ===============
 
/// This class template implements a value-semantic container type holding a
/// sequence of elements of the (template parameter) `VALUE` type.
///
/// See @ref bslstl_list 
template <class VALUE, class ALLOCATOR = bsl::allocator<VALUE> >
class list {
 
    // PRIVATE TYPES
 
    /// Default comparator.
    typedef List_DefaultLessThan<VALUE>           DefaultLessThan;
 
    /// Alias for the node type in this list.
    typedef List_Node<VALUE>                      Node;
 
    /// Proctor for guarding a newly allocated node.
    typedef List_NodeProctor<VALUE, ALLOCATOR>    NodeProctor;
 
    /// Alias for the allocator traits type associated with this container.
    typedef typename allocator_traits<ALLOCATOR>::template rebind_traits<Node>
                                                  AllocTraits;
 
    /// Alias for the utility associated with movable references.
    typedef BloombergLP::bslmf::MovableRefUtil    MoveUtil;
 
    /// Alias for the wrapper containing the (usually stateless) allocator
    /// and number of elements stored in this container.
    typedef List_AllocAndSizeWrapper<VALUE, ALLOCATOR>
                                                  AllocAndSizeWrapper;
 
    /// Base class of `List_AllocAndSizeWrapper` containing the allocator.
    typedef typename AllocTraits::allocator_type  NodeAlloc;
 
    // In C++11 'NodePtr' would be generalized as follows:
    // 'typedef pointer_traits<VoidPtr>::template rebind<List_Node> NodePtr;'
 
    typedef typename AllocTraits::pointer         NodePtr;
 
  public:
    // PUBLIC TYPES
    typedef VALUE&                                             reference;
    typedef const VALUE&                                       const_reference;
    typedef List_Iterator<VALUE>                               iterator;
    typedef List_Iterator<const VALUE>                         const_iterator;
    typedef typename allocator_traits<ALLOCATOR>::pointer      pointer;
    typedef typename allocator_traits<ALLOCATOR>::const_pointer
                                                               const_pointer;
 
    typedef typename allocator_traits<ALLOCATOR>::size_type    size_type;
    typedef typename allocator_traits<ALLOCATOR>::difference_type
                                                               difference_type;
    typedef VALUE                                 value_type;
    typedef ALLOCATOR                             allocator_type;
    typedef bsl::reverse_iterator<iterator>       reverse_iterator;
    typedef bsl::reverse_iterator<const_iterator> const_reverse_iterator;
 
  private:
    // DATA
    NodePtr             d_sentinel;        // node pointer of sentinel element
    AllocAndSizeWrapper d_alloc_and_size;  // node allocator
 
    // FRIENDS
    friend class List_NodeProctor<VALUE, ALLOCATOR>;
 
    // PRIVATE MANIPULATORS
 
    /// Return a reference providing modifiable access to the allocator used
    /// to allocate nodes.
    NodeAlloc& allocatorImp();
 
    /// Return a pointer to a node allocated from the container's allocator.
    /// Before returning, the node's pointers are zeroed, but the
    /// constructor of the `value_type` is not called.
    NodePtr allocateNode();
 
    /// Create the sentinel node of this list.  The sentinel node does not
    /// hold a value.  When first created, its forward and backward pointers
    /// point to itself, creating a circular linked list.  This function
    /// also sets this list's size to 0.
    void createSentinel();
 
    /// Destroy the value part of the specified `node` and free the node's
    /// memory.  Do not do any pointer fix-up of the node or its neighbors,
    /// and do not update `sizeRef`.  The behavior is undefined unless
    /// `node` was allocated using the allocator of this list.
    void deleteNode(NodePtr node);
 
    /// Erase all elements and deallocate the sentinel node, leaving this
    /// list in an invalid but destructible state (i.e., with `size == -1`).
    void destroyAll();
 
    /// Zero out the pointers and deallocate the node pointed to by the
    /// specified `node`.  The behavior is undefined unless `node` was
    /// allocated using the allocator of this list.  Note that `node`s
    /// destructor is not called, and, importantly, the value field of
    /// `node` is not destroyed.
    void freeNode(NodePtr node);
 
    /// Insert the specified `node` prior to the specified `position` in
    /// this list.  The behavior is undefined unless `node` was allocated
    /// using the allocator of this list and `position` is in the range
    /// `[begin() .. end()]`.
    iterator insertNode(const_iterator position, NodePtr node);
 
    /// Modify the forward pointer of the specified `prev` to point to the
    /// specified `next` and the backward pointer of `next` to point to
    /// `prev`.  The behavior is undefined unless `prev` and `next` point to
    /// nodes created with `allocateNode`.
    void linkNodes(NodePtr prev, NodePtr next);
 
    /// Given a specified pair of nodes `node1` and `finish` specifying the
    /// range `[node1 .. finish)`, with the specified `node2` pointing
    /// somewhere in the middle of the sequence, merge sequence
    /// `[node2 .. finish)` into `[node1 .. node2)`, and return a pointer to
    /// the beginning of the merged sequence, using the specified
    /// `comparator` to determine order.  If an exception is thrown, all
    /// nodes remain in this list, but their order is unspecified.  If any
    /// nodes in the range `[node1 .. node2)` compare equivalent to any
    /// nodes in the range `[node2 .. finish)`, the nodes from
    /// `[node1 .. node2)` will be merged first.  The behavior is undefined
    /// unless `[node1 .. node2)` and `[node2 .. finish)` each describe a
    /// contiguous sequence of nodes.
    template <class COMPARE>
    NodePtr mergeImp(NodePtr node1,
                     NodePtr node2,
                     NodePtr finish,
                     COMPARE comparator);
 
    /// Efficiently exchange the value of this object with that of the
    /// specified `other` object.  This method provides the no-throw
    /// exception-safety guarantee.  The behavior is undefined unless this
    /// object was created with the same allocator as `other`.
    void quickSwap(list *other);
 
    /// Return a reference providing modifiable access to the data element
    /// holding the size of this list.
    typename AllocTraits::size_type& sizeRef() BSLS_KEYWORD_NOEXCEPT;
 
    /// Sort the sequence of the specified `size` nodes starting with the
    /// specified `*nodePtrPtr`, and modify `*nodePtrPtr` to refer to the
    /// first node of the sorted sequence.  Return the pointer to the node
    /// following the sequence of nodes to be sorted.  Use the specified
    /// `comparator` to compare `VALUE` type objects.  If an exception is
    /// thrown, all nodes remain properly linked, but their order is
    /// unspecified.  The behavior is undefined unless `*nodePtrPtr` begins
    /// a sequence of at least `size` nodes, none of which is the sentinel
    /// node, and `0 < size`.
    template <class COMPARE>
    NodePtr sortImp(NodePtr        *nodePtrPtr,
                    size_type       size,
                    const COMPARE&  comparator);
 
    // PRIVATE ACCESSORS
 
    /// Return a reference providing non-modifiable access to the allocator
    /// used to allocate nodes.
    const NodeAlloc& allocatorImp() const;
 
    /// Return a pointer providing modifiable access to the first node in
    /// this list or the sentinel node if this list is empty.
    NodePtr headNode() const;
 
    /// Return a reference providing non-modifiable access to the data
    /// element holding the size of this list.
    const typename AllocTraits::size_type& sizeRef() const
                                                         BSLS_KEYWORD_NOEXCEPT;
 
  public:
    // CREATORS
 
    /// Create an empty list.  A default-constructed object of the (template
    /// parameter) type `ALLOCATOR` is used.  If the type `ALLOCATOR` is
    /// `bsl::allocator`, the currently installed default allocator is used.
    list();
 
    /// Create an empty list.  Use the specified `basicAllocator` to supply
    /// memory.  If the type `ALLOCATOR` is `bsl::allocator` (the default),
    /// then `basicAllocator` shall be convertible to `bslma::Allocator *`.
    explicit list(const ALLOCATOR& basicAllocator);
 
    /// Create a list of the specified `numElements` size whose every
    /// element is default-constructed.  A default-constructed object of the
    /// (template parameter) type `ALLOCATOR` is used.  If the type
    /// `ALLOCATOR` is `bsl::allocator`, the currently installed default
    /// allocator is used.  Throw `bsl::length_error` if
    /// `numElements > max_size()`.  This method requires that the (template
    /// parameter) `VALUE` be `default-insertable` into this list (see
    /// {Requirements on `VALUE`}).
    explicit list(size_type numElements);
 
    /// Create a list of the specified `numElements` size whose every
    /// element is default-constructed.  Use the specified `basicAllocator`
    /// to supply memory.  If the type `ALLOCATOR` is `bsl::allocator` (the
    /// default), then `basicAllocator` shall be convertible to
    /// `bslma::Allocator *`.  Throw `bsl::length_error` if
    /// `numElements > max_size()`.  This method requires that the (template
    /// parameter) `VALUE` be `default-insertable` into this list (see
    /// {Requirements on `VALUE`}).
    list(size_type        numElements,
         const ALLOCATOR& basicAllocator);
 
    /// Create a list of the specified `numElements` size whose every
    /// element has the specified `value`.  Optionally specify a
    /// `basicAllocator` used to supply memory.  If `basicAllocator` is not
    /// supplied, a default-constructed object of the (template parameter)
    /// type `ALLOCATOR` is used.  If the type `ALLOCATOR` is
    /// `bsl::allocator` (the default), then `basicAllocator`, if supplied,
    /// shall be convertible to `bslma::Allocator *`.  If the type
    /// `ALLOCATOR` is `bsl::allocator` and `basicAllocator` is not
    /// supplied, the currently installed default allocator is used.  Throw
    /// `bsl::length_error` if `numElements > max_size()`.  This method
    /// requires that the (template parameter) `VALUE` be `copy-insertable`
    /// into this list (see {Requirements on `VALUE`}).
    list(size_type         numElements,
         const value_type& value,
         const ALLOCATOR&  basicAllocator = ALLOCATOR());
 
    /// Create a list initially containing copies of the values in the range
    /// starting at the specified `first` and ending immediately before the
    /// specified `last` iterators of the (template parameter) type
    /// `INPUT_ITERATOR`.  Optionally specify a `basicAllocator` used to
    /// supply memory.  If `basicAllocator` is not supplied, a
    /// default-constructed object of the (template parameter) type
    /// `ALLOCATOR` is used.  If the type `ALLOCATOR` is `bsl::allocator`
    /// (the default), then `basicAllocator`, if supplied, shall be
    /// convertible to `bslma::Allocator *`.  If the type `ALLOCATOR` is
    /// `bsl::allocator` and `basicAllocator` is not supplied, the currently
    /// installed default allocator is used.  Throw `bsl::length_error` if
    /// the number of elements in `[first .. last)` exceeds the size
    /// returned by @ref max_size .  The (template parameter) type
    /// `INPUT_ITERATOR` shall meet the requirements of an input iterator
    /// defined in the C++11 standard [input.iterators] providing access to
    /// values of a type convertible to `value_type`, and `value_type` must
    /// be `emplace-constructible` from `*i` into this list, where `i` is a
    /// dereferenceable iterator in the range `[first .. last)` (see
    /// {Requirements on `VALUE`}).  The behavior is undefined unless
    /// `first` and `last` refer to a sequence of valid values where `first`
    /// is at a position at or before `last`.
    template <class INPUT_ITERATOR>
    list(INPUT_ITERATOR   first,
         INPUT_ITERATOR   last,
         const ALLOCATOR& basicAllocator = ALLOCATOR(),
         typename enable_if<
                 !is_arithmetic<INPUT_ITERATOR>::value &&
                 !is_enum<INPUT_ITERATOR>::value
         >::type * = 0)
    : d_alloc_and_size(basicAllocator, size_type(-1))
    {
        // MS Visual Studio 2008 compiler requires that a function using
        // enable_if be in-place inline.
 
        // '*this' is in an invalid but destructible state (size == -1).
        // Create a temporary list, 'tmp' with the specified data.  If an
        // exception is thrown, 'tmp's destructor will clean up.  Otherwise,
        // swap 'tmp' with '*this', leaving 'tmp' in an invalid but
        // destructible state and leaving '*this' fully constructed.
 
        list tmp(this->allocatorImp());
        tmp.insert(tmp.cbegin(), first, last);
        quickSwap(&tmp);
    }
 
    /// Create a list having the same value as the specified `original`
    /// object.  Use the allocator returned by
    /// 'bsl::allocator_traits<ALLOCATOR>::
    /// select_on_container_copy_construction(original.get_allocator())' to
    /// allocate memory.  This method requires that the (template parameter)
    /// type `VALUE` be `copy-insertable` into this list (see {Requirements
    /// on `VALUE`}).
    list(const list& original);
 
    /// Create a list that has the same value as the specified `original`
    /// object.  Use the specified `basicAllocator` to supply memory.  This
    /// method requires that the (template parameter) `VALUE` be
    /// `copy-insertable` into this list (see {Requirements on `VALUE`}).
    /// Note that a `bslma::Allocator *` can be supplied for
    /// `basicAllocator` if the (template parameter) type `ALLOCATOR` is
    /// `bsl::allocator` (the default).
    list(const list&                                    original,
         const typename type_identity<ALLOCATOR>::type& basicAllocator);
 
    /// Create a list having the same value as the specified `original`
    /// object by moving (in constant time) the contents of `original` to
    /// the new list.  The allocator associated with `original` is
    /// propagated for use in the newly-created list.  `original` is left in
    /// a valid but unspecified state.
    list(BloombergLP::bslmf::MovableRef<list> original);            // IMPLICIT
 
    /// Create a list having the same value as the specified `original`
    /// object that uses the specified `basicAllocator` to supply memory.
    /// The contents of `original` are moved (in constant time) to the new
    /// list if `basicAllocator == original.get_allocator()`, and are move-
    /// inserted (in linear time) using `basicAllocator` otherwise.
    /// `original` is left in a valid but unspecified state.  This method
    /// requires that the (template parameter) `VALUE` be `move-insertable`
    /// into this list (see {Requirements on `VALUE`}).  Note that a
    /// `bslma::Allocator *` can be supplied for `basicAllocator` if the
    /// (template parameter) `ALLOCATOR` is `bsl::allocator` (the default).
    list(BloombergLP::bslmf::MovableRef<list>           original,
         const typename type_identity<ALLOCATOR>::type& basicAllocator);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    list(std::initializer_list<value_type> values,
         const ALLOCATOR&                  basicAllocator = ALLOCATOR());
                                                                    // IMPLICIT
        // Create a list and append each 'value_type' object in the specified
        // 'values' initializer list.  Optionally specify a 'basicAllocator'
        // used to supply memory.  If 'basicAllocator' is not supplied, a
        // default-constructed object of the (template parameter) type
        // 'ALLOCATOR' is used.  If the type 'ALLOCATOR' is 'bsl::allocator'
        // (the default), then 'basicAllocator', if supplied, shall be
        // convertible to 'bslma::Allocator *'.  If the type 'ALLOCATOR' is
        // 'bsl::allocator' and 'basicAllocator' is not supplied, the currently
        // installed default allocator is used.  This method requires that the
        // (template parameter) 'VALUE' be 'copy-insertable' into this list
        // (see {Requirements on 'VALUE'}).
#endif
 
    /// Destroy this list by calling the destructor for each element and
    /// deallocating all allocated storage.
    ~list();
 
    // MANIPULATORS
 
                            // *** assignment ***
 
    /// Assign to this object the value of the specified `rhs` object,
    /// propagate to this object the allocator of `rhs` if the `ALLOCATOR`
    /// type has trait `propagate_on_container_copy_assignment`, and return
    /// a reference providing modifiable access to this object.  If an
    /// exception is thrown, `*this` is left in a valid but unspecified
    /// state.  This method requires that the (template parameter) type
    /// `VALUE` be `copy-assignable` and `copy-insertable` into this list.
    /// Note that, to the extent possible, existing elements of this list
    /// are copy-assigned to, to minimize the number of nodes that need to
    /// be copy-inserted or erased.
    list& operator=(const list& rhs);
 
    list& operator=(BloombergLP::bslmf::MovableRef<list> rhs)
        BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                          AllocTraits::is_always_equal::value);
        // Assign to this object the value of the specified 'rhs' object,
        // propagate to this object the allocator of 'rhs' if the 'ALLOCATOR'
        // type has trait 'propagate_on_container_move_assignment', and return
        // a reference providing modifiable access to this object.  The
        // contents of 'rhs' are moved (in constant time) to this list if
        // 'get_allocator() == rhs.get_allocator()' (after accounting for the
        // aforementioned trait); otherwise, all elements in this list are
        // either destroyed or move-assigned to and each additional element in
        // 'rhs' is move-inserted into this list.  'rhs' is left in a valid but
        // unspecified state, and if an exception is thrown, '*this' is left in
        // a valid but unspecified state.  This method requires that the
        // (template parameter) type 'VALUE' be 'move-assignable' and
        // 'move-insertable' into this list (see {Requirements on 'VALUE'}).
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Assign to this list, in order, the sequence of values in the
    /// specified `rhs` initializer list, and return a reference providing
    /// modifiable access to this list.  This method requires that the
    /// (template parameter) type `VALUE` be `copy-assignable` and
    /// `copy-insertable` into this list.  Note that, to the extent
    /// possible, existing elements of this list are copy-assigned to, to
    /// minimize the number of nodes that need to be copy-inserted or
    /// erased.
    list& operator=(std::initializer_list<value_type> rhs);
#endif
 
    /// Assign to this list the sequence of values, in order, of the
    /// elements of the specified range `[first .. last)`.  The (template
    /// parameter) type `INPUT_ITERATOR` shall meet the requirements of an
    /// input iterator defined in the C++11 standard [24.2.3] providing
    /// access to values of a type convertible to `value_type`, and
    /// `value_type` must be `emplace-constructible` from `*i` into this
    /// list, where `i` is a dereferenceable iterator in the range
    /// `[first .. last)`.  The behavior is undefined unless `first` and
    /// `last` refer to a sequence of valid values where `first` is at a
    /// position at or before `last`.  Note that, to the extent possible,
    /// existing elements of this list are copy-assigned to, to minimize the
    /// number of nodes that need to be copy-inserted or erased.  If an
    /// exception is thrown, `*this` is left in a valid but unspecified
    /// state.
    template <class INPUT_ITERATOR>
    void assign(INPUT_ITERATOR first,
                INPUT_ITERATOR last,
                typename enable_if<
                    !is_arithmetic<INPUT_ITERATOR>::value &&
                    !is_enum<INPUT_ITERATOR>::value
                >::type * = 0)
    {
        // MS Visual Studio 2008 compiler requires that a function using
        // enable_if be in-place inline.
 
        iterator       dstIt  = this->begin();
        const iterator dstEnd = this->end();
 
        for (; first != last && dstEnd != dstIt; ++first, ++dstIt) {
            *dstIt = *first;
        }
 
        erase(dstIt, dstEnd);
 
        for (; first != last; ++first) {
            emplace(dstEnd, *first);
        }
    }
 
    /// Replace the contents of this list with the specified `numElements`
    /// copies of the specified `value`.  Note that, to the extent possible,
    /// existing elements of this list are copy-assigned to, to minimize the
    /// number of nodes that need to be copy-inserted or erased.
    void assign(size_type numElements, const value_type& value);
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Assign to this list, in order, the sequence of values in the
    /// specified `values` initializer list.  This method requires that the
    /// (template parameter) type `VALUE` be `copy-assignable` and
    /// `copy-insertable` into this list.  Note that, to the extent
    /// possible, existing elements of this list are copy-assigned to, to
    /// minimize the number of nodes that need to be copy-inserted or
    /// erased.
    void assign(std::initializer_list<value_type> values);
#endif
 
                              // *** iterators ***
 
    /// Return an iterator providing modifiable access to the first element
    /// in this list, and the past-the-end iterator if this list is empty.
    iterator begin() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end (forward) iterator providing modifiable
    /// access to this list.
    iterator end() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a reverse iterator providing modifiable access to the last
    /// element in this list, and the past-the-end reverse iterator if this
    /// list is empty.
    reverse_iterator rbegin() BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end reverse iterator providing modifiable access
    /// to this list.
    reverse_iterator rend() BSLS_KEYWORD_NOEXCEPT;
 
                            // *** modify size ***
 
    /// Remove all the elements from this list.
    void clear() BSLS_KEYWORD_NOEXCEPT;
 
    void resize(size_type newSize);
    /// Change the size of this list to the specified `newSize`.  Erase
    /// `size() - newSize` elements at the back if `newSize < size()`.
    /// Append `newSize - size()` elements at the back having the optionally
    /// specified `value` if `newSize > size()`; if `value` is not
    /// specified, default-constructed objects of the (template parameter)
    /// `VALUE` are emplaced.  This method has no effect if
    /// `newSize == size()`.  Throw `bsl::length_error` if
    /// `newSize > max_size()`.
    void resize(size_type newSize, const value_type& value);
 
                           // *** element access ***
 
    /// Return a reference providing modifiable access to the last element
    /// of this list.  The behavior is undefined unless this list contains
    /// at least one element.
    reference back();
 
    /// Return a reference providing modifiable access to the first element
    /// of this list.  The behavior is undefined unless this list contains
    /// at least one element.
    reference front();
 
                                // *** end erase ***
 
    /// Remove and destroy the last element of this list.  The behavior is
    /// undefined unless this list contains at least one element.
    void pop_back();
 
    /// Remove and destroy the first element of this list.  The behavior is
    /// undefined unless this list contains at least one element.
    void pop_front();
 
                         // *** random access erase ***
 
    /// Remove from this list the element at the specified `position`, and
    /// return an iterator providing modifiable access to the element
    /// immediately following the removed element, or to the position
    /// returned by the `end` method if the removed element was the last in
    /// the sequence.  The behavior is undefined unless `position` refers to
    /// an element in this list.
    iterator erase(const_iterator position);
 
    /// Remove from this list the elements starting at the specified
    /// `dstBegin` position up to, but not including, the specified `dstEnd`
    /// position, and return a non-`const` iterator equivalent to `dstEnd`.
    /// The behavior is undefined unless `dstBegin` is an iterator in the
    /// range `[begin() .. end()]` and `dstEnd` is an iterator in the range
    /// `[dstBegin .. end()]` (both endpoints included).  Note that
    /// `dstBegin` may be equal to `dstEnd`, in which case the list is not
    /// modified.
    iterator erase(const_iterator dstBegin, const_iterator dstEnd);
 
                            // *** end inserts ***
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Append to the back of this list a newly created `value_type` object,
    /// constructed by forwarding `get_allocator()` (if required) and the
    /// specified (variable number of) `arguments` to the corresponding
    /// constructor of `value_type`.  Return a reference providing
    /// modifiable access to the inserted element.  If an exception is
    /// thrown (other than by the move constructor of a non-copy-insertable
    /// `value_type`), this method has no effect.  This method requires that
    /// the (template parameter) `VALUE` be `move-insertable` into this list
    /// and `emplace-constructible` from `arguments` (see {Requirements on
    /// `VALUE`}).
    template <class... ARGS>
    reference emplace_back(ARGS&&... arguments);
#endif
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Prepend to the front of this list a newly created `value_type`
    /// object, constructed by forwarding `get_allocator()` (if required)
    /// and the specified (variable number of) `arguments` to the
    /// corresponding constructor of `value_type`.  Return a reference
    /// providing modifiable access to the inserted element.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE` be
    /// `move-insertable` into this list and `emplace-constructible` from
    /// `arguments` (see {Requirements on `VALUE`}).
    template <class... ARGS>
    reference emplace_front(ARGS&&... arguments);
#endif
 
    /// Append to the back of this list a copy of the specified `value`.
    /// This method offers full guarantee of rollback in case an exception
    /// is thrown.  This method requires that the (template parameter)
    /// `VALUE` be `copy-constructible` (see {Requirements on `VALUE`}).
    void push_back(const value_type& value);
 
    /// Append to the back of this list the specified move-insertable
    /// `value`.  `value` is left in a valid but unspecified state.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE` be
    /// `move-insertable` into this list (see {Requirements on `VALUE`}).
    void push_back(BloombergLP::bslmf::MovableRef<value_type> value);
 
    /// Prepend to the front of this list a copy of the specified `value`.
    /// This method offers full guarantee of rollback in case an exception
    /// is thrown.  This method requires that the (template parameter)
    /// `VALUE` be `copy-constructible` (see {Requirements on `VALUE`}).
    void push_front(const value_type& value);
 
    /// Prepend to the front of this list the specified move-insertable
    /// `value`.  `value` is left in a valid but unspecified state.  If an
    /// exception is thrown (other than by the move constructor of a
    /// non-copy-insertable `value_type`), this method has no effect.  This
    /// method requires that the (template parameter) `VALUE` be
    /// `move-insertable` into this list (see {Requirements on `VALUE`}).
    void push_front(BloombergLP::bslmf::MovableRef<value_type> value);
 
                       // *** random access inserts ***
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
    /// Insert at the specified `position` in this list a newly created
    /// `value_type` object, constructed by forwarding `get_allocator()` (if
    /// required) and the specified (variable number of) `arguments` to the
    /// corresponding constructor of `value_type`, and return an iterator
    /// providing modifiable access to the newly created and inserted
    /// element.  If an exception is thrown (other than by the copy
    /// constructor, move constructor, assignment operator, or move
    /// assignment operator of `value_type`), this method has no effect.
    /// This method requires that the (template parameter) `VALUE` be
    /// `move-insertable` into this list and `emplace-constructible` from
    /// `arguments` (see {Requirements on `VALUE`}).  The behavior is
    /// undefined unless `position` is an iterator in the range
    /// `[cbegin() .. cend()]` (both endpoints included).
    template <class... ARGS>
    iterator emplace(const_iterator position, ARGS&&... arguments);
#endif
 
    /// Insert at the specified `dstPosition` in this list a copy of the
    /// specified `value`, and return an iterator providing modifiable
    /// access to the newly inserted element.  This method offers full
    /// guarantee of rollback in case an exception is thrown other than by
    /// the `VALUE` copy constructor or assignment operator.  This method
    /// requires that the (template parameter) `VALUE` be `copy-insertable`
    /// into this list (see {Requirements on `VALUE`}).  The behavior is
    /// undefined unless `dstPosition` is an iterator in the range
    /// `[cbegin() .. cend()] (both endpoints included)`.
    iterator insert(const_iterator dstPosition, const value_type& value);
 
    /// Insert at the specified `dstPosition` in this list the specified
    /// move-insertable `value`, and return an iterator providing modifiable
    /// access to the newly inserted element.  `value` is left in a valid
    /// but unspecified state.  If an exception is thrown (other than by the
    /// copy constructor, move constructor, assignment operator, or move
    /// assignment operator of `value_type`), this method has no effect.
    /// This method requires that the (template parameter) `VALUE` be
    /// `move-insertable` into this list (see {Requirements on `VALUE`}).
    /// The behavior is undefined unless `dstPosition` is an iterator in the
    /// range `[cbegin() .. cend()]` (both endpoints included).
    iterator insert(const_iterator                             dstPosition,
                    BloombergLP::bslmf::MovableRef<value_type> value);
 
    /// Insert at the specified `dstPosition` in this list the specified
    /// `numElements` copies of the specified `value`, and return an
    /// iterator providing modifiable access to the first element in the
    /// newly inserted sequence of elements.  This method requires that the
    /// (template parameter) `VALUE` be `copy-insertable` into this list
    /// (see {Requirements on `VALUE`}).  The behavior is undefined unless
    /// `dstPosition` is an iterator in the range `[cbegin() .. cend()]`
    /// (both endpoints included).
    iterator insert(const_iterator    dstPosition,
                    size_type         numElements,
                    const value_type& value);
 
    /// Insert at the specified `dstPosition` in this list the values in the
    /// range starting at the specified `first` and ending immediately
    /// before the specified `last` iterators of the (template parameter)
    /// type `INPUT_ITERATOR`, and return an iterator providing modifiable
    /// access to the first element in the newly inserted sequence of
    /// elements.  The (template parameter) type `INPUT_ITERATOR` shall meet
    /// the requirements of an input iterator defined in the C++11 standard
    /// [input.iterators] providing access to values of a type convertible
    /// to `value_type`, and `value_type` must be `emplace-constructible`
    /// from `*i` into this list, where `i` is a dereferenceable iterator in
    /// the range `[first .. last)` (see {Requirements on `VALUE`}).  The
    /// behavior is undefined unless `dstPosition` is an iterator in the
    /// range `[cbegin() .. cend()]` (both endpoints included), and `first`
    /// and `last` refer to a sequence of valid values where `first` is at a
    /// position at or before `last`.
    template <class INPUT_ITERATOR>
    iterator insert(const_iterator dstPosition,
                    INPUT_ITERATOR first,
                    INPUT_ITERATOR last,
                    typename enable_if<
                        !is_arithmetic<INPUT_ITERATOR>::value &&
                        !is_enum<INPUT_ITERATOR>::value
                    >::type * = 0)
    {
        // MS Visual Studio 2008 compiler requires that a function using
        // enable_if be in place inline.
 
        if (first == last) {
            return dstPosition.unconst();                             // RETURN
        }
 
        // The return value should indicate the first node inserted.  We can't
        // assume 'INPUT_ITERATOR' has a post-increment available.
 
        iterator ret = insert(dstPosition, *first);
        for (++first; first != last; ++first) {
            insert(dstPosition, *first);
        }
 
        return ret;
    }
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
    /// Insert at the specified `dstPosition` in this list the value of each
    /// `value_type` object in the specified `values` initializer list, and
    /// return an iterator providing modifiable access to the first element
    /// in the newly inserted sequence of elements.  This method requires
    /// that the (template parameter) `VALUE` be `copy-insertable` into this
    /// list (see {Requirements on `VALUE`}).  The behavior is undefined
    /// unless `dstPosition` is an iterator in the range
    /// `[cbegin() .. cend()]` (both endpoints included).
    iterator insert(const_iterator                    dstPosition,
                    std::initializer_list<value_type> values);
#endif
 
                          // *** list operations ***
 
    void merge(list&                                other);
    /// Merge the specified sorted `other` list into this sorted list.  This
    /// method has no effect if `other` is this list; otherwise, `other` is
    /// left empty.  The behavior is undefined unless both `other` and this
    /// list are sorted in non-decreasing order according to the ordering
    /// provided by `operator<`, and unless both `other` and this list use
    /// the same allocator.  `operator<` must define a strict weak ordering
    /// per `value_type` (see {Comparators and Strict Weak Ordering}).
    void merge(BloombergLP::bslmf::MovableRef<list> other);
 
    /// Merge the specified sorted `other` list into this sorted list, using
    /// the specified binary `comparator` predicate to order elements.  This
    /// method has no effect if `other` is this list; otherwise, `other` is
    /// left empty.  The behavior is undefined unless both `other` and this
    /// list are sorted in non-decreasing order according to the ordering
    /// provided by `comparator`, and unless both `other` and this list use
    /// the same allocator.
    template <class COMPARE>
    void merge(list& other, COMPARE comparator);
    template <class COMPARE>
    void merge(BloombergLP::bslmf::MovableRef<list> other, COMPARE comparator);
 
    /// Erase all the elements having the specified `value` from this list
    /// and return the number of erased elements.
    size_type remove(const value_type& value);
 
    /// Erase all the elements in this list for which the specified unary
    /// `predicate` returns `true` and return the number of erased elements.
    template <class PREDICATE>
    size_type remove_if(PREDICATE predicate);
 
    /// Reverse the order of the elements in this list.
    void reverse() BSLS_KEYWORD_NOEXCEPT;
 
    /// Sort this list in non-decreasing order according to the order
    /// provided by `operator<`.  `operator<` must provide a strict weak
    /// ordering over `value_type` (see {Comparators and Strict Weak
    /// Ordering}).  The sort is stable, meaning that if
    /// `!(a < b) && !(b < a)`, then the ordering of elements `a` and `b` in
    /// the sequence is preserved.
    void sort();
 
    /// Sort this list in non-decreasing order according to the order
    /// provided by the specified `comparator` predicate.  `comparator` must
    /// define a strict weak ordering over `value_type` (see {Comparators
    /// and Strict Weak Ordering}).  The sort is stable, meaning that if
    /// `!comparator(a, b) && !comparator(b, a)`, then the ordering of
    /// elements `a` and `b` in the sequence is preserved.
    template <class COMPARE>
    void sort(COMPARE comparator);
 
    void splice(const_iterator                       dstPosition,
                list&                                src);
    /// Remove all elements of the specified `src` list and insert them, in
    /// the same order, in this list at the specified `dstPosition`.  The
    /// behavior is undefined unless `src` is not this list, this list and
    /// `src` use the same allocator, and `dstPosition` is in the range
    /// `[begin() .. end()]` (note both endpoints included).
    void splice(const_iterator                       dstPosition,
                BloombergLP::bslmf::MovableRef<list> src);
 
    void splice(const_iterator                       dstPosition,
                list&                                src,
                const_iterator                       srcNode);
    /// Remove the single element at the specified `srcNode` from the
    /// specified `src` list, and insert it at the specified `dstPosition`
    /// in this list.  The behavior is undefined unless `srcNode` refers to
    /// a valid element in `src`, this list and `src` use the same
    /// allocator, and `dstPosition` is in the range `[begin() .. end()]`
    /// (note both endpoints included).  Note that `src` and `*this` may be
    /// the same list, in which case the element is moved to a (possibly)
    /// new position in the list.
    void splice(const_iterator                       dstPosition,
                BloombergLP::bslmf::MovableRef<list> src,
                const_iterator                       srcNode);
 
    void splice(const_iterator                       dstPosition,
                list&                                src,
                const_iterator                       first,
                const_iterator                       last);
    /// Remove the elements in the specified range `[first .. last)` from
    /// the specified `src` list, and insert them, in the same order, at the
    /// specified `dstPosition` in this list.  The behavior is undefined
    /// unless `[first .. last)` represents a range of valid elements in
    /// `src`, `dstPosition` is not in the range `[first .. last)`, this
    /// list and `src` use the same allocator, and `dstPosition` is in the
    /// range `[begin() .. end()]` (note both endpoints included).  Note
    /// that `src` and `*this` may be the same list, in which case an entire
    /// sequence of nodes is moved to a (possibly) new position in this
    /// list.
    void splice(const_iterator                       dstPosition,
                BloombergLP::bslmf::MovableRef<list> src,
                const_iterator                       first,
                const_iterator                       last);
 
    /// Erase from this list all but the first element of every consecutive
    /// group of elements that have the same value.
    void unique();
 
    /// Erase from this list all but the first element of every consecutive
    /// group of elements for which the specified `binaryPredicate` returns
    /// `true` for any two consecutive elements in the group.
    template <class EQ_PREDICATE>
    void unique(EQ_PREDICATE binaryPredicate);
 
                              // *** misc ***
 
    void swap(list& other) BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(
                                          AllocTraits::is_always_equal::value);
        // Exchange the value of this object with that of the specified 'other'
        // object; also exchange the allocator of this object with that of
        // 'other' if the (template parameter) type 'ALLOCATOR' has the
        // 'propagate_on_container_swap' trait, and do not modify either
        // allocator otherwise.  This method provides the no-throw
        // exception-safety guarantee.  This operation has 'O[1]' complexity if
        // either this object was created with the same allocator as 'other' or
        // 'ALLOCATOR' has the 'propagate_on_container_swap' trait; otherwise,
        // it has 'O[n + m]' complexity, where 'n' and 'm' are the number of
        // elements in this object and 'other', respectively.  Note that this
        // method's support for swapping objects created with different
        // allocators when 'ALLOCATOR' does not have the
        // 'propagate_on_container_swap' trait is a departure from the
        // C++ Standard.
 
    // ACCESSORS
 
                               // *** iterators ***
 
    const_iterator begin() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return an iterator providing non-modifiable access to the first
    /// `value_type` object in the ordered sequence of `value_type` objects
    /// maintained by this list, or the `end` iterator if this list is
    /// empty.
    const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    const_iterator end() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end (forward) iterator providing non-modifiable
    /// access to this list.
    const_iterator cend() const BSLS_KEYWORD_NOEXCEPT;
 
    const_reverse_iterator rbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return a reverse iterator providing non-modifiable access to the
    /// last element in this list, and the past-the-end reverse iterator if
    /// this list is empty.
    const_reverse_iterator crbegin() const BSLS_KEYWORD_NOEXCEPT;
 
    const_reverse_iterator rend() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the past-the-end reverse iterator providing non-modifiable
    /// access to this list.
    const_reverse_iterator crend() const BSLS_KEYWORD_NOEXCEPT;
 
                                  // *** size ***
 
    /// Return `true` if this list has no elements, and `false` otherwise.
    bool empty() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return an upper bound on the largest number of elements that this
    /// list could possibly hold.  Note that the return value of this
    /// function does not guarantee that this list can successfully grow
    /// that large, or even close to that large without running out of
    /// resources.
    size_type max_size() const BSLS_KEYWORD_NOEXCEPT;
 
    /// Return the number of elements in this list.
    size_type size() const BSLS_KEYWORD_NOEXCEPT;
 
                           // *** element access ***
 
    /// Return a reference providing non-modifiable access to the last
    /// element of this list.  The behavior is undefined unless this list
    /// contains at least one element.
    const_reference back() const;
 
    /// Return a reference providing non-modifiable access to the first
    /// element of this list.  The behavior is undefined unless this list
    /// contains at least one element.
    const_reference front() const;
 
                                // *** misc ***
 
    /// Return a copy of the allocator used for memory allocation by this
    /// list.
    allocator_type get_allocator() const BSLS_KEYWORD_NOEXCEPT;
};
 
#ifdef BSLS_COMPILERFEATURES_SUPPORT_CTAD
// CLASS TEMPLATE DEDUCTION GUIDES
 
/// Deduce the template parameter `VALUE` from the corresponding parameter
/// supplied to the constructor of `list`.  This deduction guide does not
/// participate unless the supplied allocator is convertible to
/// `bsl::allocator<VALUE>`.
template <
    class SIZE_TYPE,
    class VALUE,
    class ALLOC,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<
                            bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>,
    class = bsl::enable_if_t<
              bsl::is_convertible_v<
                 SIZE_TYPE,
                 typename bsl::allocator_traits<DEFAULT_ALLOCATOR>::size_type>>
    >
list(SIZE_TYPE, VALUE, ALLOC *) -> list<VALUE>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// iterators supplied to the constructor of `list`.
template <
    class INPUT_ITERATOR,
    class VALUE = typename
                   BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>
    >
list(INPUT_ITERATOR, INPUT_ITERATOR) -> list<VALUE>;
 
/// Deduce the template parameter `VALUE` from the `value_type` of the
/// iterators supplied to the constructor of `list`.  Deduce the template
/// parameter `ALLOCATOR` from the allocator supplied to the constructor of
/// `list`.  This deduction guide does not participate unless the supplied
/// allocator meets the requirements of a standard allocator.
template<
    class INPUT_ITERATOR,
    class ALLOCATOR,
    class VALUE = typename
                  BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
    class = bsl::enable_if_t<bsl::IsStdAllocator_v<ALLOCATOR>>>
list(INPUT_ITERATOR, INPUT_ITERATOR, ALLOCATOR) -> list<VALUE, ALLOCATOR>;
 
/// Deduce the template parameter `VALUE` from the value_type of the
/// iterators supplied to the constructor of `list`.  This deduction guide
/// does not participate unless the specified `ALLOC` is convertible to
/// `bsl::allocator<CHAR_TYPE>`.
template<
    class INPUT_ITERATOR,
    class ALLOC,
    class VALUE = typename
                  BloombergLP::bslstl::IteratorUtil::IterVal_t<INPUT_ITERATOR>,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
    >
list(INPUT_ITERATOR, INPUT_ITERATOR, ALLOC *)
-> list<VALUE>;
 
/// Deduce the template parameter `VALUE` from the value_type of the
/// intializer_list supplied to the constructor of `list`.  This deduction
/// guide does not participate unless the specified `ALLOC` is convertible
/// to `bsl::allocator<CHAR_TYPE>`.
template<
    class VALUE,
    class ALLOC,
    class DEFAULT_ALLOCATOR = bsl::allocator<VALUE>,
    class = bsl::enable_if_t<bsl::is_convertible_v<ALLOC *, DEFAULT_ALLOCATOR>>
    >
list(std::initializer_list<VALUE>, ALLOC *)
-> list<VALUE>;
#endif
 
// FREE OPERATORS
 
/// Return `true` if the specified `lhs` and `rhs` objects have the same
/// value, and `false` otherwise.  Two `list` objects `lhs` and `rhs` have
/// the same value if they have the same number of elements, and each
/// element in the ordered sequence of elements of `lhs` has the same value
/// as the corresponding element in the ordered sequence of elements of
/// `rhs`.  This method requires that the (template parameter) type `VALUE`
/// be `equality-comparable` (see {Requirements on `VALUE`}).
template <class VALUE, class ALLOCATOR>
bool operator==(const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
 
template <class VALUE, class ALLOCATOR>
bool operator!=(const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
    // Return 'true' if the specified 'lhs' and 'rhs' objects do not have the
    // same value, and 'false' otherwise.  Two 'list' objects 'lhs' and 'rhs'
    // do not have the same value if they do not have the same number of
    // elements, or some element in the ordered sequence of elements of 'lhs'
    // does not have the same value as the corresponding element in the ordered
    // sequence of elements of 'rhs'.  This method requires that the
    // (template parameter) type 'VALUE' be 'equality-comparable' (see
    // {Requirements on 'VALUE'}).
 
#endif  // BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
 
#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
/// Perform a lexicographic three-way comparison of the specified `lhs` and
/// the specified `rhs` lists by using the comparison operators of `VALUE`
/// on each element; return the result of that comparison.
template <class VALUE, class ALLOCATOR>
BloombergLP::bslalg::SynthThreeWayUtil::Result<VALUE> operator<=>(
                                            const list<VALUE, ALLOCATOR>& lhs,
                                            const list<VALUE, ALLOCATOR>& rhs);
 
#else
 
template <class VALUE, class ALLOCATOR>
bool operator< (const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
    // Return 'true' if the value of the specified 'lhs' list is
    // lexicographically less than that of the specified 'rhs' list, and
    // 'false' otherwise.  Given iterators 'i' and 'j' over the respective
    // sequences '[lhs.begin() .. lhs.end())' and '[rhs.begin() .. rhs.end())',
    // the value of list 'lhs' is lexicographically less than that of list
    // 'rhs' if 'true == *i < *j' for the first pair of corresponding iterator
    // positions where '*i < *j' and '*j < *i' are not both 'false'.  If no
    // such corresponding iterator position exists, the value of 'lhs' is
    // lexicographically less than that of 'rhs' if 'lhs.size() < rhs.size()'.
    // This method requires that 'operator<', inducing a total order, be
    // defined for 'value_type'.
 
template <class VALUE, class ALLOCATOR>
bool operator> (const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
    // Return 'true' if the value of the specified 'lhs' list is
    // lexicographically greater than that of the specified 'rhs' list, and
    // 'false' otherwise.  The value of list 'lhs' is lexicographically greater
    // than that of list 'rhs' if 'rhs' is lexicographically less than 'lhs'
    // (see 'operator<').  This method requires that 'operator<', inducing a
    // total order, be defined for 'value_type'.  Note that this operator
    // returns 'rhs < lhs'.
 
template <class VALUE, class ALLOCATOR>
bool operator<=(const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
    // Return 'true' if the value of the specified 'lhs' list is
    // lexicographically less than or equal to that of the specified 'rhs'
    // list, and 'false' otherwise.  The value of list 'lhs' is
    // lexicographically less than or equal to that of list 'rhs' if 'rhs' is
    // not lexicographically less than 'lhs' (see 'operator<').  This method
    // requires that 'operator<', inducing a total order, be defined for
    // 'value_type'.  Note that this operator returns '!(rhs < lhs)'.
 
template <class VALUE, class ALLOCATOR>
bool operator>=(const list<VALUE, ALLOCATOR>& lhs,
                const list<VALUE, ALLOCATOR>& rhs);
    // Return 'true' if the value of the specified 'lhs' list is
    // lexicographically greater than or equal to that of the specified 'rhs'
    // list, and 'false' otherwise.  The value of list 'lhs' is
    // lexicographically greater than or equal to that of list 'rhs' if 'lhs'
    // is not lexicographically less than 'rhs' (see 'operator<').  This method
    // requires that 'operator<', inducing a total order, be defined for
    // 'value_type'.  Note that this operator returns '!(lhs < rhs)'.
 
#endif  // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
// FREE FUNCTIONS
 
/// Erase all the elements in the specified list `l` that compare equal to
/// the specified `value`.  Return the number of elements erased.
template <class VALUE, class ALLOCATOR, class BDE_OTHER_TYPE>
typename list<VALUE, ALLOCATOR>::size_type
erase(list<VALUE, ALLOCATOR>& l, const BDE_OTHER_TYPE& value);
 
/// Erase all the elements in the specified list `l` that satisfy the
/// specified predicate `predicate`.  Return the number of elements erased.
template <class VALUE, class ALLOCATOR, class PREDICATE>
typename list<VALUE, ALLOCATOR>::size_type
erase_if(list<VALUE, ALLOCATOR>& l, PREDICATE predicate);
 
template <class VALUE, class ALLOCATOR>
void swap(list<VALUE, ALLOCATOR>& a, list<VALUE, ALLOCATOR>& b)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(BSLS_KEYWORD_NOEXCEPT_OPERATOR(
                                                                   a.swap(b)));
    // Exchange the value of the specified 'a' object with that of the
    // specified 'b' object; also exchange the allocator of 'a' with that of
    // 'b' if the (template parameter) type 'ALLOCATOR' has the
    // 'propagate_on_container_swap' trait, and do not modify either allocator
    // otherwise.  This function provides the no-throw exception-safety
    // guarantee.  This operation has 'O[1]' complexity if either 'a' was
    // created with the same allocator as 'b' or 'ALLOCATOR' has the
    // 'propagate_on_container_swap' trait; otherwise, it has 'O[n + m]'
    // complexity, where 'n' and 'm' are the number of elements in 'a' and 'b',
    // respectively.  Note that this function's support for swapping objects
    // created with different allocators when 'ALLOCATOR' does not have the
    // 'propagate_on_container_swap' trait is a departure from the C++
    // Standard.
 
// ============================================================================
//                   INLINE AND TEMPLATE FUNCTION DEFINITIONS
// ============================================================================
 
                           // ------------------------
                           // class bsl::List_Iterator
                           // ------------------------
 
// PRIVATE ACCESSORS
template <class VALUE>
inline
typename List_Iterator<VALUE>::NcIter List_Iterator<VALUE>::unconst() const
{
    return NcIter(d_node_p);
}
 
// CREATORS
template <class VALUE>
inline
List_Iterator<VALUE>::List_Iterator()
: d_node_p()
{
}
 
template <class VALUE>
inline
List_Iterator<VALUE>::List_Iterator(Node *nodePtr)
: d_node_p(nodePtr)
{
}
 
template <class VALUE>
inline
List_Iterator<VALUE>::List_Iterator(const NcIter& other)
: d_node_p(other.d_node_p)
{
}
 
// MANIPULATORS
template <class VALUE>
inline
List_Iterator<VALUE>& List_Iterator<VALUE>::operator++()
{
    this->d_node_p = this->d_node_p->d_next_p;
    return *this;
}
 
template <class VALUE>
inline
List_Iterator<VALUE>& List_Iterator<VALUE>::operator--()
{
    this->d_node_p = this->d_node_p->d_prev_p;
    return *this;
}
 
template <class VALUE>
inline
List_Iterator<VALUE> List_Iterator<VALUE>::operator++(int)
{
    List_Iterator temp = *this;
    this->operator++();
    return temp;
}
 
template <class VALUE>
inline
List_Iterator<VALUE> List_Iterator<VALUE>::operator--(int)
{
    List_Iterator temp = *this;
    this->operator--();
    return temp;
}
 
// ACCESSORS
template <class VALUE>
inline
typename bsl::List_Iterator<VALUE>::reference
                                        List_Iterator<VALUE>::operator*() const
{
    return this->d_node_p->d_value;
}
 
template <class VALUE>
inline
typename bsl::List_Iterator<VALUE>::pointer
                                       List_Iterator<VALUE>::operator->() const
{
    return BloombergLP::bsls::Util::addressOf(this->d_node_p->d_value);
}
 
// FREE OPERATORS
template <class T1, class T2>
inline
bool operator==(bsl::List_Iterator<T1> lhs, bsl::List_Iterator<T2> rhs)
{
    // Make sure that this comparison will only compile if 'T1' and 'T2' match
    // except for a possible difference in 'const'-ness.
 
    BSLMF_ASSERT((bsl::is_same<typename bsl::remove_cv<T1>::type,
                               typename bsl::remove_cv<T2>::type>::value));
 
    return lhs.d_node_p == rhs.d_node_p;
}
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
template <class T1, class T2>
inline
bool operator!=(bsl::List_Iterator<T1> lhs, bsl::List_Iterator<T2> rhs)
{
    // Make sure that this comparison will only compile if 'T1' and 'T2' match
    // except for a possible difference in 'const'-ness.
 
    BSLMF_ASSERT((bsl::is_same<typename bsl::remove_cv<T1>::type,
                               typename bsl::remove_cv<T2>::type>::value));
 
    return ! (lhs == rhs);
}
#endif
 
                          // ------------------------------
                          // class List_AllocAndSizeWrapper
                          // ------------------------------
 
// CREATOR
template <class VALUE, class ALLOCATOR>
inline
List_AllocAndSizeWrapper<VALUE, ALLOCATOR>::List_AllocAndSizeWrapper(
                                               const NodeAlloc& basicAllocator,
                                               size_type        size)
: NodeAlloc(basicAllocator)
, d_size(size)
{
}
 
// MANIPULATORS
template <class VALUE, class ALLOCATOR>
inline
typename List_AllocAndSizeWrapper<VALUE, ALLOCATOR>::size_type&
List_AllocAndSizeWrapper<VALUE, ALLOCATOR>::size()
{
    return d_size;
}
 
// ACCESSORS
template <class VALUE, class ALLOCATOR>
inline
const typename List_AllocAndSizeWrapper<VALUE, ALLOCATOR>::size_type&
List_AllocAndSizeWrapper<VALUE, ALLOCATOR>::size() const
{
    return d_size;
}
 
                          // ----------------------
                          // class List_NodeProctor
                          // ----------------------
 
// CREATORS
template <class VALUE, class ALLOCATOR>
inline
List_NodeProctor<VALUE, ALLOCATOR>::List_NodeProctor(
                                               list<VALUE, ALLOCATOR> *listPtr,
                                               NodePtr                 nodePtr)
: d_list_p(listPtr)
, d_node_p(nodePtr)
{
    BSLS_ASSERT_SAFE(listPtr);
    BSLS_ASSERT_SAFE(nodePtr);
}
 
template <class VALUE, class ALLOCATOR>
inline
List_NodeProctor<VALUE, ALLOCATOR>::~List_NodeProctor()
{
    if (d_node_p) {
        d_list_p->freeNode(d_node_p);
    }
}
 
// MANIPULATORS
template <class VALUE, class ALLOCATOR>
inline
void List_NodeProctor<VALUE, ALLOCATOR>::release()
{
    d_node_p = 0;
}
 
                        // --------------------------
                        // class List_DefaultLessThan
                        // --------------------------
 
// ACCESSORS
template <class VALUE>
inline
bool List_DefaultLessThan<VALUE>::operator()(
                                      const VALUE& lhs, const VALUE& rhs) const
{
    return lhs < rhs;
}
 
                                // ---------------
                                // class bsl::list
                                // ---------------
 
// PRIVATE MANIPULATORS
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::NodeAlloc&
                                         list<VALUE, ALLOCATOR>::allocatorImp()
{
    return d_alloc_and_size;  // implicit cast to base class
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::NodePtr list<VALUE, ALLOCATOR>::allocateNode()
{
    NodePtr ret = AllocTraits::allocate(allocatorImp(), 1);
    ret->d_prev_p = 0;
    ret->d_next_p = 0;
    return ret;
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::createSentinel()
{
    BSLS_ASSERT_SAFE(size_type(-1) == sizeRef() || 0 == sizeRef());
 
    d_sentinel = allocateNode();
    linkNodes(d_sentinel, d_sentinel);  // circular
    sizeRef() = 0;
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::deleteNode(NodePtr node)
{
    BSLS_ASSERT_SAFE(node);
 
    AllocTraits::destroy(allocatorImp(),
                         BloombergLP::bsls::Util::addressOf(node->d_value));
    AllocTraits::deallocate(allocatorImp(), node, 1);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::destroyAll()
{
    clear();
    freeNode(d_sentinel);
    sizeRef() = size_type(-1);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::freeNode(NodePtr node)
{
    AllocTraits::deallocate(allocatorImp(), node, 1);
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::insertNode(const_iterator position, NodePtr node)
{
    NodePtr next = position.d_node_p;
    NodePtr prev = next->d_prev_p;
    linkNodes(prev, node);
    linkNodes(node, next);
    ++sizeRef();
    return iterator(node);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::linkNodes(NodePtr prev, NodePtr next)
{
    prev->d_next_p = next;
    next->d_prev_p = prev;
}
 
template <class VALUE, class ALLOCATOR>
template <class COMPARE>
typename list<VALUE, ALLOCATOR>::NodePtr
list<VALUE, ALLOCATOR>::mergeImp(NodePtr node1,
                                 NodePtr node2,
                                 NodePtr finish,
                                 COMPARE comparator)
{
    NodePtr pre = node1->d_prev_p;
 
    // The only possible throwing operation is the comparator.  Exception
    // neutrality is achieved by ensuring that this list is in a valid state,
    // with no disconnected nodes, before the comparator is called.
 
    // Having the two sublists be contiguous parts of the same list has the
    // following advantages:
    //: 1 When we reach the end of a sublist, there is no "finalization" step
    //:   where the end of the remaining sublist must be spliced onto the
    //:   merged list.
    //: 2 No cleanup needed if an exception is thrown; the size and validity of
    //:   the resulting list needs no adjustment.
 
    while (node1 != node2 && node2 != finish) {
        // Loop invariants:
        // - The open range (pre, node1) is the current merged result
        // - The half-open range [node1, node2) is the 1st unmerged sequence
        // - The half-open range [node2, finish) is the 2nd unmerged sequence
 
        if (comparator(node2->d_value, node1->d_value)) {
            // 'node2' should come before 'node1'.
 
            // Find the end of the sequence of elements that belong before
            // node1 so that we can splice them all at once.
 
            NodePtr lastMove = node2;
            NodePtr next2    = node2->d_next_p;
            while (next2 != finish && comparator(next2->d_value,
                                                 node1->d_value)) {
                lastMove = next2;
                next2 = lastMove->d_next_p;
            }
 
            linkNodes(node2->d_prev_p, next2);
            linkNodes(node1->d_prev_p, node2);
            linkNodes(lastMove, node1);
 
            // Advance to next node in the 2nd unmerged sequence.
 
            node2 = next2;
        }
        else {
            // Advance to next node in the 1st unmerged sequence.
 
            node1 = node1->d_next_p;
        }
    }
 
    return pre->d_next_p;
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::quickSwap(list *other)
{
    BSLS_ASSERT_SAFE(allocatorImp() == other->allocatorImp());
 
    using std::swap;
 
    swap(d_sentinel, other->d_sentinel);
    swap(sizeRef(),  other->sizeRef());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::AllocTraits::size_type&
list<VALUE, ALLOCATOR>::sizeRef() BSLS_KEYWORD_NOEXCEPT
{
    return d_alloc_and_size.size();
}
 
template <class VALUE, class ALLOCATOR>
template <class COMPARE>
typename list<VALUE, ALLOCATOR>::NodePtr
list<VALUE, ALLOCATOR>::sortImp(NodePtr        *nodePtrPtr,
                                size_type       size,
                                const COMPARE&  comparator)
{
    BSLS_ASSERT(size > 0);
 
    NodePtr node1 = *nodePtrPtr;
    if (size < 2) {
        return node1->d_next_p;                                       // RETURN
    }
 
    size_type half = size / 2;
 
    NodePtr node2 = sortImp(&node1, half,        comparator);
    NodePtr next  = sortImp(&node2, size - half, comparator);
 
    *nodePtrPtr = mergeImp(node1, node2, next, comparator);
    return next;
}
 
// PRIVATE ACCESSORS
template <class VALUE, class ALLOCATOR>
inline
const typename list<VALUE, ALLOCATOR>::NodeAlloc&
                                   list<VALUE, ALLOCATOR>::allocatorImp() const
{
    return d_alloc_and_size;  // implicit cast to base class
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::NodePtr list<VALUE, ALLOCATOR>::headNode()
                                                                          const
{
    return d_sentinel->d_next_p;
}
 
template <class VALUE, class ALLOCATOR>
inline
const typename list<VALUE, ALLOCATOR>::AllocTraits::size_type&
list<VALUE, ALLOCATOR>::sizeRef() const BSLS_KEYWORD_NOEXCEPT
{
    return d_alloc_and_size.size();
}
 
// CREATORS
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list()
: d_sentinel()
, d_alloc_and_size(ALLOCATOR(), 0)
{
    BSLMF_ASSERT((bsl::is_same<size_type,
                                     typename AllocTraits::size_type>::value));
    BSLMF_ASSERT((bsl::is_same<difference_type,
                               typename AllocTraits::difference_type>::value));
    createSentinel();
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(const ALLOCATOR& basicAllocator)
: d_sentinel()
, d_alloc_and_size(basicAllocator, 0)
{
    createSentinel();
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(size_type numElements)
: d_sentinel()
, d_alloc_and_size(ALLOCATOR(), size_type(-1))
{
    // '*this' is in an invalid but destructible state (size == -1).
 
    list tmp(this->allocatorImp());
 
    // Default-construct (value-initialize) 'n' elements into 'tmp'.  'tmp's
    // destructor will clean up if an exception is thrown.
 
    iterator pos = tmp.end();
    for (size_type i = 0; i < numElements; ++i) {
        tmp.emplace(pos);
    }
 
    quickSwap(&tmp);  // Leave 'tmp' in an invalid but destructible state.
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(size_type        numElements,
                             const ALLOCATOR& basicAllocator)
: d_sentinel()
, d_alloc_and_size(basicAllocator, size_type(-1))
{
    // '*this' is in an invalid but destructible state (size == -1).
 
    list tmp(this->allocatorImp());
 
    // Default-construct (value-initialize) 'n' elements into 'tmp'.  'tmp's
    // destructor will clean up if an exception is thrown.
 
    const_iterator pos = tmp.cend();
    for (size_type i = 0; i < numElements; ++i) {
        tmp.emplace(pos);
    }
 
    quickSwap(&tmp);  // Leave 'tmp' in an invalid but destructible state.
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(size_type        numElements,
                             const VALUE&     value,
                             const ALLOCATOR& basicAllocator)
: d_sentinel()
, d_alloc_and_size(basicAllocator, size_type(-1))
{
    // '*this' is in an invalid but destructible state (size == -1).
 
    list tmp(this->allocatorImp());
    tmp.insert(tmp.cbegin(), numElements, value);    // 'tmp's destructor will
                                                     // clean up on throw.
    quickSwap(&tmp);      // Leave 'tmp' in an invalid but destructible state.
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(const list& original)
: d_sentinel()
, d_alloc_and_size(
   AllocTraits::select_on_container_copy_construction(original.allocatorImp()),
   size_type(-1))
{
    list tmp(this->allocatorImp());
 
    tmp.insert(tmp.cbegin(), original.begin(), original.end());
 
    quickSwap(&tmp);  // Leave 'tmp' in an invalid but destructible state.
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(const list&                        original,
                 const typename type_identity<ALLOCATOR>::type& basicAllocator)
: d_sentinel()
, d_alloc_and_size(basicAllocator, size_type(-1))
{
    list tmp(this->allocatorImp());
 
    tmp.insert(tmp.cbegin(), original.begin(), original.end());
 
    quickSwap(&tmp);  // Leave 'tmp' in an invalid but destructible state.
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(BloombergLP::bslmf::MovableRef<list> original)
: d_sentinel()
, d_alloc_and_size(MoveUtil::access(original).allocatorImp(), 0)
{
    // Allocator should be copied, not moved, to ensure identical allocators
    // between this and 'original', otherwise 'swap' is undefined.
 
    // An rvalue must be left in a valid state after a move.
 
    createSentinel();
 
    // '*this' is now in a valid state.
 
    quickSwap(&MoveUtil::access(original));
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::list(
                 BloombergLP::bslmf::MovableRef<list>           original,
                 const typename type_identity<ALLOCATOR>::type& basicAllocator)
: d_sentinel()
, d_alloc_and_size(basicAllocator, size_type(-1))
{
    // '*this' is in an invalid but destructible state (size == -1).
 
    list& lvalue = original;
    if (this->allocatorImp() == lvalue.allocatorImp()) {
        // An rvalue must be left in a valid state after a move.
 
        createSentinel();      // '*this' is now in a valid state.
        quickSwap(&lvalue);
    }
    else {
        // different allocators, must copy
 
        list tmp(this->allocatorImp());
 
        // Avoid relying on VALUE's copy c'tor unless no move c'tor is
        // available.
 
        NodePtr endPtr = lvalue.d_sentinel;
        for (NodePtr p = lvalue.headNode(); endPtr != p;  p = p->d_next_p) {
            tmp.emplace_back(MoveUtil::move(p->d_value));
        }
 
        // Leave 'tmp' with all elements in a moved-from (but destructible)
        // state.
        quickSwap(&tmp);
    }
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE, class ALLOCATOR>
inline
list<VALUE, ALLOCATOR>::list(std::initializer_list<VALUE> values,
                             const ALLOCATOR&             basicAllocator)
: d_alloc_and_size(basicAllocator, size_type(-1))
{
    // '*this' is in an invalid but destructible state (size == -1).  Create a
    // temporary list, 'tmp', with the specified data.  If an exception is
    // thrown, 'tmp's destructor will clean up.  Otherwise, swap 'tmp' with
    // '*this', leaving 'tmp' in an invalid but destructible state and leaving
    // '*this' fully constructed.
 
    list tmp(this->allocatorImp());
    tmp.insert(tmp.cbegin(), values.begin(), values.end());
 
    quickSwap(&tmp);
}
#endif
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>::~list()
{
    // A size of -1 means a special incompletely-initialized state with no
    // sentinel, which requires no destruction.
 
    if (sizeRef() != size_type(-1)) {
        destroyAll();
    }
}
 
// MANIPULATORS
 
                            // *** assignment ***
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>& list<VALUE, ALLOCATOR>::operator=(const list& rhs)
{
    typedef typename
        AllocTraits::propagate_on_container_copy_assignment Propagate;
 
    if (this != &rhs) {
        if (Propagate::value && allocatorImp() != rhs.allocatorImp()) {
            // Fully destroy old list before assigning allocator, then reset to
            // the empty list state.
            destroyAll();
            BloombergLP::bslma::AllocatorUtil::assign(&allocatorImp(),
                                                      rhs.allocatorImp(),
                                                      Propagate());
            createSentinel();
        }
        assign(rhs.begin(), rhs.end()); // Copy elements
    }
 
    return *this;
}
 
template <class VALUE, class ALLOCATOR>
list<VALUE, ALLOCATOR>& list<VALUE, ALLOCATOR>::operator=(
                                      BloombergLP::bslmf::MovableRef<list> rhs)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocTraits::is_always_equal::value)
{
    typedef typename
        AllocTraits::propagate_on_container_move_assignment Propagate;
 
    list& lvalue = rhs;
 
    if (this == &lvalue) {
        return *this;                                                 // RETURN
    }
 
    if (this->allocatorImp() == lvalue.allocatorImp()) {
        // Equal allocators, just swap contents, will never throw.
 
        quickSwap(&lvalue);
    }
    else if (Propagate::value) {
        // An rvalue must be left in a valid state after a move.  Both '*this'
        // and 'rhs' must be left in valid states after a throw.
 
        // Note: tearing everything down, then changing the allocator, then
        // doing 'quickSwap(&lvalue)' has a problem in that it could leave
        // 'rhs' in an invalid state, since if 'this->createSentinel()' were
        // called after the tearing down to render '*this' to a valid value,
        // 'createSentinel' might throw, leaving '*this' in an invalid state.
 
        // Swap everything, including the allocator (here we are relying on the
        // C++11 standard, which requires that the allocator type not throw on
        // copy or assign).
 
        list other(MoveUtil::move(lvalue));
 
        using std::swap;
        using BloombergLP::bslma::AllocatorUtil;
 
        AllocatorUtil::swap(                       // won't throw
            &allocatorImp(), &other.allocatorImp(), Propagate());
        swap(d_sentinel,      other.d_sentinel);   // swap of pointer type
        swap(sizeRef(),       other.sizeRef());    // swap of fundamental type
    }
    else {
        // Unequal allocators and the allocator of the destination is to remain
        // unchanged.  Copy using 'move', which will use copy functions where
        // 'value_type' doesn't support moving.  Note that if this throws part
        // way through, both '*this' and 'rhs' may be left changed.
 
        NodePtr              dstPtr    = this->headNode();
        const const_iterator dstEnd    = this->cend();
        const NodePtr        dstEndPtr = dstEnd.d_node_p;
 
        NodePtr              srcPtr    = lvalue.headNode();
        const NodePtr        srcEndPtr = lvalue.d_sentinel;
 
        for (; srcEndPtr != srcPtr && dstEndPtr != dstPtr;
                        srcPtr = srcPtr->d_next_p, dstPtr = dstPtr->d_next_p) {
            dstPtr->d_value = MoveUtil::move(srcPtr->d_value);
        }
 
        erase(const_iterator(dstPtr), dstEnd);
 
        for (; srcEndPtr != srcPtr; srcPtr = srcPtr->d_next_p) {
            emplace(dstEnd, MoveUtil::move(srcPtr->d_value));
        }
    }
 
    return *this;
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE, class ALLOCATOR>
inline
list<VALUE, ALLOCATOR>& list<VALUE, ALLOCATOR>::operator=(
                                              std::initializer_list<VALUE> rhs)
{
    assign(rhs.begin(), rhs.end());
    return *this;
}
#endif
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::assign(size_type numElements, const VALUE& value)
{
    NodePtr              dst_p    = this->headNode();
    const const_iterator dstEnd   = this->cend();
    const NodePtr        dstEnd_p = dstEnd.d_node_p;
 
    for (; 0 < numElements && dstEnd_p != dst_p;
                                      --numElements, dst_p = dst_p->d_next_p) {
        dst_p->d_value = value;
    }
 
    erase(const_iterator(dst_p), dstEnd);
 
    for (; 0 < numElements; --numElements) {
        insert(dstEnd, value);
    }
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::assign(std::initializer_list<VALUE> values)
{
    assign(values.begin(), values.end());
}
#endif
 
                              // *** iterators ***
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::iterator list<VALUE, ALLOCATOR>::begin()
                                                          BSLS_KEYWORD_NOEXCEPT
{
    return iterator(headNode());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::iterator list<VALUE, ALLOCATOR>::end()
                                                          BSLS_KEYWORD_NOEXCEPT
{
    return iterator(d_sentinel);
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::reverse_iterator
list<VALUE, ALLOCATOR>::rbegin() BSLS_KEYWORD_NOEXCEPT
{
    return reverse_iterator(end());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::reverse_iterator
list<VALUE, ALLOCATOR>::rend() BSLS_KEYWORD_NOEXCEPT
{
    return reverse_iterator(begin());
}
 
                            // *** modify size ***
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::clear() BSLS_KEYWORD_NOEXCEPT
{
    const NodePtr e = d_sentinel;
    for (NodePtr p = d_sentinel->d_next_p; e != p; ) {
        NodePtr condemned = p;
        p = p->d_next_p;
        deleteNode(condemned);
    }
 
    linkNodes(d_sentinel, d_sentinel);
    sizeRef() = 0;
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::resize(size_type newSize)
{
    if (newSize > sizeRef()) {
        const_iterator ce = cend();
        do {
            emplace(ce);
        } while (newSize > sizeRef());
    }
    else {
        NodePtr e = d_sentinel;
        NodePtr p = e->d_prev_p;
        for (size_type d = sizeRef() - newSize; d > 0; --d) {
            NodePtr condemned = p;
            p = p->d_prev_p;
            deleteNode(condemned);
        }
        linkNodes(p, e);
        sizeRef() = newSize;
    }
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::resize(size_type newSize, const VALUE& value)
{
    if (newSize > sizeRef()) {
        const_iterator ce = cend();
        do {
            emplace(ce, value);
        } while (newSize > sizeRef());
    }
    else {
        NodePtr e = d_sentinel;
        NodePtr p = e->d_prev_p;
        for (size_type d = sizeRef() - newSize; d > 0; --d) {
            NodePtr condemned = p;
            p = p->d_prev_p;
            deleteNode(condemned);
        }
        linkNodes(p, e);
        sizeRef() = newSize;
    }
}
 
                                // element access:
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::reference
list<VALUE, ALLOCATOR>::back()
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    return d_sentinel->d_prev_p->d_value;
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::reference
list<VALUE, ALLOCATOR>::front()
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    return headNode()->d_value;
}
 
                                // *** end erase ***
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::pop_back()
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    erase(--cend());
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::pop_front()
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    erase(cbegin());
}
 
                         // *** random access erase ***
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::erase(const_iterator position)
{
    BSLS_ASSERT(position.d_node_p != d_sentinel);
 
    NodePtr  condemned = position.d_node_p;
    iterator ret(condemned->d_next_p);
 
    linkNodes(condemned->d_prev_p, condemned->d_next_p);
    deleteNode(condemned);
    --sizeRef();
    return ret;
}
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::erase(const_iterator dstBegin, const_iterator dstEnd)
{
    NodePtr       p = dstBegin.d_node_p;
    const NodePtr e = dstEnd.  d_node_p;
 
    linkNodes(p->d_prev_p, e);
 
    size_type numDeleted = 0;
    for (; e != p; ++numDeleted) {
        NodePtr condemned = p;
        p = p->d_next_p;
        deleteNode(condemned);
    }
 
    sizeRef() -= numDeleted;
 
    return iterator(e);
}
 
                            // *** end inserts ***
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class VALUE, class ALLOCATOR>
template <class... ARGS>
inline
typename list<VALUE, ALLOCATOR>::reference
list<VALUE, ALLOCATOR>::emplace_back(ARGS&&... arguments)
{
    emplace(cend(), BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
    return back();
}
#endif
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class VALUE, class ALLOCATOR>
template <class... ARGS>
inline
typename list<VALUE, ALLOCATOR>::reference
list<VALUE, ALLOCATOR>::emplace_front(ARGS&&... arguments)
{
    emplace(cbegin(), BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
    return front();
}
#endif
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::push_back(const VALUE& value)
{
    emplace(cend(), value);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::push_back(
                                   BloombergLP::bslmf::MovableRef<VALUE> value)
{
    emplace(cend(), MoveUtil::move(value));
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::push_front(const VALUE& value)
{
    emplace(cbegin(), value);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::push_front(
                                   BloombergLP::bslmf::MovableRef<VALUE> value)
{
    emplace(cbegin(), MoveUtil::move(value));
}
 
                       // *** random access inserts ***
 
#if !BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
template <class VALUE, class ALLOCATOR>
template <class... ARGS>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::emplace(const_iterator position, ARGS&&... arguments)
{
    NodePtr p = allocateNode();
    NodeProctor proctor(this, p);
    AllocTraits::construct(allocatorImp(),
                           BloombergLP::bsls::Util::addressOf(p->d_value),
                           BSLS_COMPILERFEATURES_FORWARD(ARGS, arguments)...);
    proctor.release();
    return insertNode(position, p);
}
#endif
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::insert(const_iterator dstPosition, const VALUE& value)
{
    return emplace(dstPosition, value);
}
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::insert(
                             const_iterator                        dstPosition,
                             BloombergLP::bslmf::MovableRef<VALUE> value)
{
    return emplace(dstPosition, MoveUtil::move(value));
}
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::insert(const_iterator dstPosition,
                               size_type      numElements,
                               const VALUE&   value)
{
    if (0 == numElements) {
        return dstPosition.unconst();                                 // RETURN
    }
 
    // Remember the position of the first node inserted before 'dstPosition'.
 
    iterator ret = emplace(dstPosition, value);
 
    // And put the rest of the nodes after it.
 
    for (--numElements; numElements > 0; --numElements) {
        emplace(dstPosition, value);
    }
 
    return ret;
}
 
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::iterator
list<VALUE, ALLOCATOR>::insert(const_iterator               dstPosition,
                               std::initializer_list<VALUE> values)
{
    return insert(dstPosition, values.begin(), values.end());
}
#endif
 
                          // *** list operations ***
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::merge(list& other)
{
    BSLS_ASSERT_SAFE(this->allocatorImp() == other.allocatorImp());
 
    merge(other, DefaultLessThan());
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::merge(BloombergLP::bslmf::MovableRef<list> other)
{
    list& lvalue = other;
 
    BSLS_ASSERT_SAFE(this->allocatorImp() == lvalue.allocatorImp());
 
    merge(lvalue, DefaultLessThan());
}
 
template <class VALUE, class ALLOCATOR>
template <class COMPARE>
void list<VALUE, ALLOCATOR>::merge(list& other, COMPARE comparator)
{
    if (&other == this) {
        return;                                                       // RETURN
    }
 
    BSLS_ASSERT(this->allocatorImp() == other.allocatorImp());
 
    if (other.empty()) {
        // This is an important special case to avoid pointing to sentinel.
 
        return;                                                       // RETURN
    }
 
    // Splice 'other' to the end of '*this', but remember the first node of the
    // appended sequence.
 
    NodePtr xfirst = other.d_sentinel->d_next_p;
    splice(end(), other);
 
    // Call 'mergeImp' with a pointer to the first node of the original list, a
    // pointer to the first node of 'other' (which also ends the original
    // list), and a pointer to the sentinel (which now ends 'other').
 
    mergeImp(d_sentinel->d_next_p, xfirst, d_sentinel, comparator);
}
 
template <class VALUE, class ALLOCATOR>
template <class COMPARE>
inline
void list<VALUE, ALLOCATOR>::merge(
                               BloombergLP::bslmf::MovableRef<list> other,
                               COMPARE                              comparator)
{
    list& lvalue = other;
 
    BSLS_ASSERT_SAFE(this->allocatorImp() == lvalue.allocatorImp());
 
    merge(lvalue, comparator);
}
 
template <class VALUE, class ALLOCATOR>
typename list<VALUE, ALLOCATOR>::size_type
list<VALUE, ALLOCATOR>::remove(const VALUE& value)
{
    const size_type origSize = this->size();
    const const_iterator e = cend();
    for (const_iterator i = cbegin(); e != i; ) {
        // Standard says to use 'operator==', not 'std::equal_to'.
 
        if (value == *i) {
            i = erase(i);
        }
        else {
            ++i;
        }
    }
 
    return origSize - this->size();
}
 
template <class VALUE, class ALLOCATOR>
template <class PREDICATE>
typename list<VALUE, ALLOCATOR>::size_type
list<VALUE, ALLOCATOR>::remove_if(PREDICATE predicate)
{
    const size_type origSize = this->size();
    const iterator e = end();
    for (iterator i = begin(); e != i; ) {
        if (predicate(*i)) {
            i = erase(i);
        }
        else {
            ++i;
        }
    }
 
    return origSize - this->size();
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::reverse() BSLS_KEYWORD_NOEXCEPT
{
    NodePtr sentinel = d_sentinel;
    NodePtr p = sentinel;
 
    do {
        NodePtr tmp = p->d_next_p;
        p->d_next_p = p->d_prev_p;
        p->d_prev_p = tmp;
        p = tmp;
    } while (p != sentinel);
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::sort()
{
    sort(DefaultLessThan());
}
 
template <class VALUE, class ALLOCATOR>
template <class COMPARE>
void list<VALUE, ALLOCATOR>::sort(COMPARE comparator)
{
    if (sizeRef() < 2) {
        return;                                                       // RETURN
    }
    NodePtr node1 = d_sentinel->d_next_p;
    sortImp(&node1, size(), comparator);
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::splice(const_iterator dstPosition, list& src)
{
    BSLS_ASSERT(allocatorImp() == src.allocatorImp());
    BSLS_ASSERT(&src != this);
 
    if (src.empty()) {
        return;                                                       // RETURN
    }
 
    NodePtr   pPos   = dstPosition.d_node_p;
    NodePtr   pFirst = src.headNode();
    NodePtr   pLast  = src.d_sentinel->d_prev_p;
    size_type n      = src.sizeRef();
 
    // Splice contents out of 'src'.
 
    linkNodes(src.d_sentinel, src.d_sentinel);
    src.sizeRef() = 0;
 
    // Splice contents into '*this'.
 
    linkNodes(pPos->d_prev_p, pFirst);
    linkNodes(pLast,          pPos);
    sizeRef() += n;
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::splice(
                              const_iterator                       dstPosition,
                              BloombergLP::bslmf::MovableRef<list> src)
{
    splice(dstPosition, MoveUtil::access(src));
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::splice(const_iterator dstPosition,
                                    list&          src,
                                    const_iterator srcNode)
{
    BSLS_ASSERT(allocatorImp() == src.allocatorImp());
 
    NodePtr pPos          = dstPosition.d_node_p;
    NodePtr pSrcNode      = srcNode.d_node_p;
    NodePtr pAfterSrcNode = pSrcNode->d_next_p;
 
    if (pPos == pSrcNode || pPos == pAfterSrcNode) {
        return;                                                       // RETURN
    }
 
    // Splice contents out of 'src'.
 
    linkNodes(pSrcNode->d_prev_p, pAfterSrcNode);
    --src.sizeRef();
 
    // Splice contents into '*this'.
 
    linkNodes(pPos->d_prev_p, pSrcNode);
    linkNodes(pSrcNode,       pPos);
    ++sizeRef();
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::splice(
                              const_iterator                       dstPosition,
                              BloombergLP::bslmf::MovableRef<list> src,
                              const_iterator                       srcNode)
{
    splice(dstPosition, MoveUtil::access(src), srcNode);
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::splice(const_iterator dstPosition,
                                    list&          src,
                                    const_iterator first,
                                    const_iterator last)
{
    BSLS_ASSERT(allocatorImp() == src.allocatorImp());
 
    size_type n = bsl::distance(first, last);
 
    if (0 == n) {
        return;                                                       // RETURN
    }
 
    NodePtr pPos     = dstPosition.d_node_p;
    NodePtr pFirst   = first.d_node_p;
    NodePtr pLast    = last.d_node_p;
    NodePtr pSrcLast = pLast->d_prev_p;
 
    // Splice contents out of 'src'.
 
    linkNodes(pFirst->d_prev_p, pLast);
    src.sizeRef() -= n;
 
    // Splice contents into '*this'.
 
    linkNodes(pPos->d_prev_p, pFirst);
    linkNodes(pSrcLast,       pPos);
    sizeRef() += n;
}
 
template <class VALUE, class ALLOCATOR>
inline
void list<VALUE, ALLOCATOR>::splice(
                              const_iterator                       dstPosition,
                              BloombergLP::bslmf::MovableRef<list> src,
                              const_iterator                       first,
                              const_iterator                       last)
{
    splice(dstPosition, MoveUtil::access(src), first, last);
}
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::unique()
{
    if (size() < 2) {
        return;                                                       // RETURN
    }
 
    iterator i = begin();
    iterator e = end();
    while (i != e) {
        reference match = *i++;
        while (i != e && *i == match) {
            i = erase(i);
        }
    }
}
 
template <class VALUE, class ALLOCATOR>
template <class EQ_PREDICATE>
void list<VALUE, ALLOCATOR>::unique(EQ_PREDICATE binaryPredicate)
{
    if (size() < 2) {
        return;                                                       // RETURN
    }
 
    iterator i = begin();
    iterator e = end();
    while (i != e) {
        reference match = *i++;
        while (i != e && binaryPredicate(*i, match)) {
            i = erase(i);
        }
    }
}
 
                              // *** misc ***
 
template <class VALUE, class ALLOCATOR>
void list<VALUE, ALLOCATOR>::swap(list& other)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(AllocTraits::is_always_equal::value)
{
    // C++11 behavior for member 'swap': undefined for unequal allocators.
    // BSLS_ASSERT(allocatorImp() == other.allocatorImp());
 
    typedef typename AllocTraits::propagate_on_container_swap Propagate;
 
    if (Propagate::value) {
        using std::swap;
        using BloombergLP::bslma::AllocatorUtil;
 
        AllocatorUtil::swap(  // Won't throw
            &allocatorImp(), &other.allocatorImp(), Propagate());
        swap(d_sentinel,      other.d_sentinel);
        swap(sizeRef(),       other.sizeRef());
    }
    else if (BSLS_PERFORMANCEHINT_PREDICT_LIKELY(
                                     allocatorImp() == other.allocatorImp())) {
        quickSwap(&other);
    }
    else {
        BSLS_PERFORMANCEHINT_UNLIKELY_HINT;
 
        // Create copies using the move constructor, then swap both containers
        // with them.  Note that if no move constructor exists, but a copy
        // constructor does, the copy constructor will be used.
 
        // Also note that if either of these copies throws, it could leave the
        // two containers in a changed state.  They are, however, guaranteed to
        // be left in valid state.
 
        list toOtherCopy(MoveUtil::move(*this), other.allocatorImp());
        list toThisCopy( MoveUtil::move(other), this->allocatorImp());
 
        toOtherCopy.quickSwap(&other);
        toThisCopy .quickSwap(this);
    }
}
 
// ACCESSORS
 
                               // *** iterators ***
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_iterator
list<VALUE, ALLOCATOR>::begin() const BSLS_KEYWORD_NOEXCEPT
{
    return const_iterator(headNode());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_iterator
list<VALUE, ALLOCATOR>::end() const BSLS_KEYWORD_NOEXCEPT
{
    return const_iterator(d_sentinel);
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_iterator
list<VALUE, ALLOCATOR>::cbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return begin();
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_iterator
list<VALUE, ALLOCATOR>::cend() const BSLS_KEYWORD_NOEXCEPT
{
    return end();
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reverse_iterator
list<VALUE, ALLOCATOR>::crbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return rbegin();
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reverse_iterator
list<VALUE, ALLOCATOR>::crend() const BSLS_KEYWORD_NOEXCEPT
{
    return rend();
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reverse_iterator
list<VALUE, ALLOCATOR>::rbegin() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(end());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reverse_iterator
list<VALUE, ALLOCATOR>::rend() const BSLS_KEYWORD_NOEXCEPT
{
    return const_reverse_iterator(begin());
}
 
                                  // *** size ***
 
template <class VALUE, class ALLOCATOR>
inline
bool list<VALUE, ALLOCATOR>::empty() const BSLS_KEYWORD_NOEXCEPT
{
    return 0 == sizeRef();
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::size_type
list<VALUE, ALLOCATOR>::max_size() const BSLS_KEYWORD_NOEXCEPT
{
    return AllocTraits::max_size(allocatorImp());
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::size_type list<VALUE, ALLOCATOR>::size() const
                                                          BSLS_KEYWORD_NOEXCEPT
{
    return sizeRef();
}
 
                           // *** element access ***
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reference
list<VALUE, ALLOCATOR>::back() const
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    return d_sentinel->d_prev_p->d_value;
}
 
template <class VALUE, class ALLOCATOR>
inline
typename list<VALUE, ALLOCATOR>::const_reference
list<VALUE, ALLOCATOR>::front() const
{
    BSLS_ASSERT_SAFE(sizeRef() > 0);
 
    return headNode()->d_value;
}
 
                                // *** misc ***
 
template <class VALUE, class ALLOCATOR>
inline
ALLOCATOR list<VALUE, ALLOCATOR>::get_allocator() const BSLS_KEYWORD_NOEXCEPT
{
    return allocatorImp();
}
 
}  // close namespace bsl
 
// FREE OPERATORS
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator==(const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
                                                    lhs.end(),
                                                    lhs.size(),
                                                    rhs.begin(),
                                                    rhs.end(),
                                                    rhs.size());
}
 
#ifndef BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
 
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator!=(const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return ! (lhs == rhs);
}
 
#endif  // BSLS_COMPILERFEATURES_SUPPORT_THREE_WAY_COMPARISON
 
#ifdef BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
template <class VALUE, class ALLOCATOR>
inline
BloombergLP::bslalg::SynthThreeWayUtil::Result<VALUE> bsl::operator<=>(
                                             const list<VALUE, ALLOCATOR>& lhs,
                                             const list<VALUE, ALLOCATOR>& rhs)
{
    return bsl::lexicographical_compare_three_way(
                              lhs.begin(),
                              lhs.end(),
                              rhs.begin(),
                              rhs.end(),
                              BloombergLP::bslalg::SynthThreeWayUtil::compare);
}
 
#else
 
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator< (const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return 0 > BloombergLP::bslalg::RangeCompare::lexicographical(lhs.begin(),
                                                                  lhs.end(),
                                                                  lhs.size(),
                                                                  rhs.begin(),
                                                                  rhs.end(),
                                                                  rhs.size());
}
 
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator> (const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return rhs < lhs;
}
 
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator<=(const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return !(rhs < lhs);
}
 
template <class VALUE, class ALLOCATOR>
inline
bool bsl::operator>=(const list<VALUE, ALLOCATOR>& lhs,
                     const list<VALUE, ALLOCATOR>& rhs)
{
    return !(lhs < rhs);
}
 
#endif // BSLALG_SYNTHTHREEWAYUTIL_AVAILABLE
 
// FREE FUNCTIONS
template <class VALUE, class ALLOCATOR, class BDE_OTHER_TYPE>
inline typename bsl::list<VALUE, ALLOCATOR>::size_type
bsl::erase(list<VALUE, ALLOCATOR>& l, const BDE_OTHER_TYPE& value)
{
    // We could use the erase/remove idiom here like we do in the other
    // sequence containers, but this is more efficient, since we just unlink
    // and delete nodes from the list.
    typename list<VALUE, ALLOCATOR>::size_type oldSize = l.size();
    for (typename list<VALUE, ALLOCATOR>::iterator it = l.begin();
                                                                it != l.end();)
    {
        if (value == *it) {
            it = l.erase(it);
        }
        else {
            ++it;
        }
    }
    return oldSize - l.size();
}
 
template <class VALUE, class ALLOCATOR, class PREDICATE>
inline typename bsl::list<VALUE, ALLOCATOR>::size_type
bsl::erase_if(list<VALUE, ALLOCATOR>& l, PREDICATE predicate)
{
    return BloombergLP::bslstl::AlgorithmUtil::containerEraseIf(l, predicate);
}
 
template <class VALUE, class ALLOCATOR>
inline
void bsl::swap(list<VALUE, ALLOCATOR>& a, list<VALUE, ALLOCATOR>& b)
    BSLS_KEYWORD_NOEXCEPT_SPECIFICATION(BSLS_KEYWORD_NOEXCEPT_OPERATOR(
                                                                    a.swap(b)))
{
    a.swap(b);
}
 
// ============================================================================
//                                TYPE TRAITS
// ============================================================================
 
// Type traits for STL *sequence* containers:
//: o A sequence container defines STL iterators.
//: o A sequence container uses 'bslma' allocators if the (template parameter)
//:   type 'ALLOCATOR' is convertible from 'bslma::Allocator*'.
 
 
 
namespace bslalg {
 
template <class VALUE, class ALLOCATOR>
struct HasStlIterators<bsl::list<VALUE, ALLOCATOR> >
    : bsl::true_type
{};
 
}  // close namespace bslalg
 
namespace bslma {
 
template <class VALUE, class ALLOCATOR>
struct UsesBslmaAllocator<bsl::list<VALUE, ALLOCATOR> >
    : bsl::is_convertible<Allocator*, ALLOCATOR>
{};
 
}  // close namespace bslma
 
namespace bslmf {
 
// A list is bitwise movable if its allocator is bitwise movable.
 
template <class VALUE, class ALLOCATOR>
struct IsBitwiseMoveable<bsl::list<VALUE, ALLOCATOR> >
    : BloombergLP::bslmf::IsBitwiseMoveable<ALLOCATOR>
{};
 
}  // close namespace bslmf
 
 
#endif // End C++11 code
 
#endif
 
// ----------------------------------------------------------------------------
// Copyright 2019 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 ----------------------------------
 
/** @} */
/** @} */
/** @} */