C++ Primer Plus study notes - STL

1 auto_ptr

The auto_ptr template defines a pointer-like object, which is a smart pointer. When the auto_ptr object expires, its destructor will use delete to release the memory.

void test1()
{
    int* ip = new int(10); //Dynamic memory is not freed
    return;
}

void test2()
{
    auto_ptr<int> ip(new int(10)); //After the auto_ptr object expires, the dynamic memory will be released
    return;
}

Note that the auto_ptr object can only be used on memory allocated by new, not on memory allocated by new[] or by declaring a variable.

2 STL

The STL provides a set of templates representing containers, iterators, function objects, and algorithms.

STL is a general-purpose programming technique. Templates provide a general representation of data types stored in containers, and iterators are general representations for traversing values in containers.

2.1 Container

2.1.1 Container concept

The container concept describes elements that are common to all container classes, in other words, the container concept specifies a set of requirements that all STL container classes must satisfy.

The basic container concept can be improved by adding requirements.

2.1.2 Container Type

Various container templates accept an optional template parameter that specifies which allocator object to use to manage memory, such as the vector template:

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >

class vector : protected _Vector_base<_Tp, _Alloc> {...}

deque, list, queue, priority_queue, stack, and vector are all sequence type containers.

The sequence concept adds the requirement that the iterators be at least forward iterators to ensure that the elements are in a specific order that does not change between iterations.

set, multiset, map, and multimap are all union type containers.

Union containers associate values with keys, which are used to look up values.

2.2 Iterators

STL defines 5 kinds of iterators - input iterator, output iterator, forward iterator, bidirectional iterator, random access iterator.

Why do we need so many iterators? The purpose is to use the least demanding iterator possible when writing an algorithm, and make it suitable for the largest range of the container.

Input iterators: For single-pass, read-only algorithms, input iterators can be used.
Output iterators: For single-pass, write-only algorithms, output iterators can be used.
Forward iterators: have all the features of input/output iterators, but also support multi-pass algorithms.
Bidirectional iterator: It has all the characteristics of a forward iterator and supports bidirectional traversal of containers.
Random Access Iterator: Has all the features of a bidirectional iterator, with the addition of operations that support random access and relational operators for sorting elements.

The STL describes algorithms in terms of the type of iterator required, e.g. the prototype of find() states that such an algorithm requires an input iterator.

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& value);

2.2.1 Pointers as iterators

Iterators are generalized pointers, and pointers satisfy all iterator requirements, so STL algorithms can use pointers to operate on pointer-based non-STL containers.

For example, use sort() to sort an array:

double nums[10];

sort(nums, nums + 10);

2.2.2 Other iterators

The header file <Iterator> also provides special predefined iterator types such as ostream_iterator, istream_iterator, reverse_iterator, back_insert_iterator, front_insert_iterator and insert_iterator.

2.3 Function objects

Many STL algorithms use function objects—also called functor s. A function symbol is any object that can be used in conjunction with () in a functional way, including function names, pointers to functions, and class objects that overload the () operator (that is, classes that define the function operator()()).

2.3.1 Concept of function notation

STL also defines the concept of function notation:

Generator: A function symbol that can be called without parameters.
Unary function: A function symbol that can be called with one argument.
Binary function: A function symbol that can be called with two arguments.

The corresponding improved version concept:

A unary function that returns a bool value is an assertion.
A binary function that returns a bool value is a binary assertion.

For example, the sort() function can take a binary assertion as its 3rd argument:

bool Compare(const Book& book1, const Book& books);
...
sort(books.begin(), books.end(), Compare);

2.3.2 Predefined function symbols

In order to support STL functions that take functions as parameters, STL defines a number of basic function symbols, which perform operations such as adding two values and comparing two values for equality.

For example, assuming that two arrays need to be added, the common implementation and the implementation using predefined function symbols are:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <Iterator>

using namespace std;

double add(double d1, double d2) { return d1 + d2; }

int main()
{
    ostream_iterator<double, char> out(cout, " ");
    vector<double> ds1 = { 1.1, 2.2, 3.3, 4.4 };
    vector<double> ds2 = { 1, 2, 3, 4 };

    // 1. Common implementations must define a separate function for each type
    transform(ds1.begin(), ds1.end(), ds2.begin(), out, add);

    cout << endl;

    // 2. A better way is to define a template, and STL has already predefined such a template
    plus<double> add2;
    transform(ds1.begin(), ds1.end(), ds2.begin(), out, add2);
}

2.3.3 Function Adapter (Deprecated)

If an STL function expects a unary function, and there is an adaptive binary function that does the job, you can use bind1st or bind2nd to adapt the binary function to the unary interface.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <Iterator>
#include <binders.h>

using namespace std;

double sqrt(double d1) { return d1 * 2.5; }

int main()
{
    ostream_iterator<double, char> out(cout, " ");
    vector<double> ds1 = { 1.1, 2.2, 3.3, 4.4 };

    // 1. Common implementation
    transform(ds1.begin(), ds1.end(), out, sqrt);

    cout << endl;

    // 2. Another implementation is to adapt the existing binary function that can realize this function into a unary function
    transform(ds1.begin(), ds1.end(), out, binder1st<multiplies<double>>(multiplies<double>(), 2.5));
}

2.4 Algorithms

For algorithmic function design, there are two main general parts. First, they both use templates to provide common types; second, they both use iterators to provide a common representation for accessing data in containers.

2.4.1 Algorithm group

STL divides the algorithm library into 4 groups:

Non-modifying sequence operations.
Modified sequence operations.
Sorting and related operations.
General digital calculations.

2.4.2 Functions and container methods

STL methods are usually a better choice than STL functions. First, it is more suitable for a specific container; second, as a member function, it can use the memory management tools of the template class to adjust the length of the container when needed.

2.5 Other Libraries

The Complex header file provides a complex class template for complex numbers, specialized for float, long and long double.

The valarray header file provides the valarray template class, which is designed to represent numeric arrays and supports various numeric array operations.

Tags: C++ Algorithm

Posted by The Midnighter on Thu, 06 Apr 2023 03:31:48 +0930

Programs Wiki