bslstl_list

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Requirements on VALUE
  • Memory Allocation
    • bslma-Style Allocators
    • Comparators and Strict Weak Ordering
  • Glossary
  • Operations
  • Usage
    • Example 1: Filter "Twinkle Star"
    • Example 2: Combine Two Star Surveys

Purpose

Provide an STL-compliant list class.

Classes

• bsl::list: STL-compatible list template

Canonical header: bsl_list.h

See also

bslstl_deque

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

A list is a fully Value-Semantic Type (see 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

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

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 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

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

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

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

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

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]               |
+----------------------------------------------------+--------------------+

Usage

This section illustrates intended usage of this component.

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 <:

#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);

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.

void readData(list<Star> *starList, FILE *input)
{
    Star s;
    while (s.read(input)) {
        starList->push_back(s);
    }
}

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:

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
        }
    }
}

Finally, we use the methods defined in above steps to put together our program to find twinkle stars:

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;
}

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:

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());

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:

    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.

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:

    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.

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:

    tmp1.sort();

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:

    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.

Now, since the two star surveys may overlap, we want to eliminate duplicates. We accomplish this by using the unique member function:

    starList1.unique();             // Eliminate duplicates in 'starList1'.
    assert(6 == starList1.size());  // Verify size after elimination.

Finally, we print the result:

    if (verbose) {
        for (list<Star>::const_iterator i = starList1.begin();
             i != starList1.end(); ++i) {
            i->write(stdout);
        }
    }
    return 0;
}

For completeness, the implementations of the read, write, and comparison functions for class Star are shown below:

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();
}