9月 18, 2020

C++ Primer, Part II : The C++ Library

C++ Primer, Fifth Edition

Stanley B. Lippman
Josée Lajoie
Barbara E. Moo

Chapter 9. Sequential Containers

A container holds a collection of objects of a specified type.
The sequential containers let the programmer control the order in which the elements are stored and accessed.

9.1 Overview of the Sequential Containers

There are a few rules of thumb that apply to selecting which container to use:

Unless you have a reason to use another container, use a vector.
If your program has lots of small elements and space overhead matters, don’t use list or forward_list.
If the program requires random access to elements, use a vector or a deque.
If the program needs to insert or delete elements in the middle of the container, use a list or forward_list.
If the program needs to insert or delete elements at the front and the back, but not in the middle, use a deque.
If the program needs to insert elements in the middle of the container only while reading input, and subsequently needs random access to the elements:

First, decide whether you actually need to add elements in the middle of a container. It is often easier to append to a vector and then call the library sort function to reorder the container when you’re done with input.
If you must insert into the middle, consider using a list for the input phase. Once the input is complete, copy the list into a vector.

If you’re not sure which container to use, write your code so that it uses only operations common to both vectors and lists: Use iterators, not subscripts, and avoid random access to elements. That way it will be easy to use either a vector or a list as necessary.

9.2 Container Library Overview

Some operations are provided by all container types.

Some operations are specific to the sequential containers

In general, each container is defined in a header file with the same name as the type.
The containers are class templates, we must supply additional information to generate a particular container type.


list<Sales_data>   // list that holds Sales_data objects
deque<double>      // deque that holds doubles

9.2.1. Iterators

An iterator range is denoted by a pair of iterators : [ begin, end).

If begin equals end, the range is empty
If begin is not equal to end, there is at least one element in the range, and begin refers to the first element in that range
We can increment begin some number of times until begin == end

The following loops to process a range of elements:


while (begin   != end) {
    *begin =  val;    // ok: range isn't empty so begin denotes an element
    ++begin;          // advance the iterator to get the next element
}

9.2.2. Container Type Members

9.2.3. begin and end Members

The begin and end operations yield iterators that refer to the first and one past the last element in the container.
There are several versions of begin and end:


list a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin();  // list<string>::iterator
auto it2 = a.rbegin(); // list<string>::reverse_iterator
auto it3 = a.cbegin(); // list<string>::const_iterator
auto it4 = a.crbegin();// list<string>::const_reverse_iterator

9.2.4. Defining and Initializing a Container

9.2.5. Assignment and swap

The assignment operator replaces the entire range of elements in the left-hand container with copies of the elements from the right-hand operand
The swap operation exchanges the contents of two containers of the same type.


vector<string> svec1(10); // vector with 10 elements
vector<string> svec2(24); // vector with 24 elements
swap(svec1, svec2);             // svec1 contains 24 string elements and svec2 contains 10

9.2.6. Container Size Operations

The container types have three size-related operations:

The size member returns the number of elements in the container
empty returns a bool that is true if size is zero and false otherwise
max_size returns a number that is greater than or equal to the number of elements a container of that type can contain

9.2.7. Relational Operators

Comparing two containers performs a pairwise comparison of the elements.


vector v1 = { 1, 3, 5, 7, 9, 12 };
vector v2 = { 1, 3, 9 };
vector v3 = { 1, 3, 5, 7 };
vector v4 = { 1, 3, 5, 7, 9, 12 };
v1 < v2  //true; v1 and v2 differ at element [2]: v1[2] is less than v2[2]
v1 < v3  //false; all elements are equal, but v3 has fewer of them;
v1 == v4 //true; each element is equal and v1 and v4 have the same size()
v1 == v2 //false; v2 has fewer elements than v1

9.3 Sequential Container Operations

9.4 How a vector Grows

9.5 Additional string Operations

9.6 Container Adaptors

Chapter 10. Generic Algorithms

10.1 Overview

10.2 A First Look at the Algorithms

10.3 Customizing Operations

10.4 Revisiting Iterators

10.5 Structure of Generic Algorithms

10.6 Container-Specific Algorithms

Chapter 11. Associative Containers

Section 11.1 Using an Associative Container

11.2 Overview of the Associative Containers

11.3 Operations on Associative C

Chapter 12. Dynamic Memory

C++ automatic and static objects have well-defined lifetimes,

Global objects are allocated at program start-up and destroyed when the program ends.
Local, automatic objects are created and destroyed when the block in which they are defined is entered and exited.
Local static objects are allocated before their first use and are destroyed when the program ends.

Dynamically allocated objects have a lifetime that is independent of where they are created; they exist until they are explicitly freed. To make using dynamic objects safer, the library defines two smart pointer types that manage dynamically allocated objects. Smart pointers ensure that the objects to which they point are automatically freed when it is appropriate to do so.

12.1 Dynamic Memory and Smart Pointers

In C++, dynamic memory is managed through a pair of operators:

new
delete

The new library provides two smart pointer types that manage dynamic objects.

shared_ptr
unique_ptr

weak_ptr that is a weak reference to an object managed by a shared_ptr.

12.1.1. The shared_ptr Class

The smart pointers are templates . Therefore, when we create a smart pointer, we must supply the type to which the pointer can point.


shared_ptr<string> p1;    // shared_ptr that can point at a string
shared_ptr< list< int> > p2; // shared_ptr that can point at a list of ints

The safest way to allocate and use dynamic memory is to call a library function named make_shared<T>().
make_shared uses its arguments to construct an object of the given type.


// shared_ptr that points to an int with value 42
shared_ptr<int> p3 = make_shared<int>(42);
// p4 points to a string with value 9999999999
shared_ptr<string> p4 = make_shared<string>(10, '9');
// p5 points to an int that is value initialized to 0
shared_ptr<int> p5 = make_shared<int>();
// p6 points to a dynamically allocated, empty vector<string>
auto p6 = make_shared<vector<string>>();

When we copy or assign a shared_ptr, each shared_ptr keeps track of how many other shared_ptrs point to the same object We can think of a shared_ptr as if it has an associated counter, usually referred to as a reference count. Once a shared_ptr’s counter goes to zero, the shared_ptr automatically frees the object that it manages


auto r = make_shared<int>(42); // int to which r points has one user
r = q;  // assign to r, making it point to a different address
        // increase the use count for the object to which q points
        // reduce the use count of the object to which r had pointed
        // the object r had pointed to has no users; that object is automatically freed

Automatically Free the Associated Memory

outside the function


// factory returns a shared_ptr pointing to a dynamically allocated object
shared_ptr<Foo> factory(T arg)
{
    // process arg as appropriate
    // shared_ptr will take care of deleting this memory
    return make_shared<Foo>(arg);
}

inside the function


void use_factory(T arg)
{
    shared_ptr<Foo> p = factory(arg);
    // use p
} // p goes out of scope; the memory to which p points is automatically freed

If you put shared_ptrs in a container, and you subsequently need to use some, but not all, of the elements, remember to erase the elements you no longer need. Using new to Dynamically Allocate and Initialize Objects,


int *pi = new int;      // pi points to a dynamically allocated,
                        // unnamed, uninitialized int
int *pi = new int(1024); // object to which pi points has value 1024

When we provide an initializer inside parentheses, we can use auto to deduce the type of the object we want to allocate from that initializer.


auto p1 = new auto(obj);   // p points to an object of the type of obj
                           // that object is initialized from obj
// allocate and initialize a const int
const int *pci = new const int(1024);

By default, if new is unable to allocate the requested storage, it throws an exception of type bad_alloc


// if allocation fails, new returns a null pointer
int *p1 = new int; // if allocation fails, new throws std::bad_alloc
int *p2 = new (nothrow) int; // if allocation fails, new returns a null pointer

A delete expression performs two actions:

destroys the object to which its given pointer points
frees the corresponding memory


delete p;      // p must point to a dynamically allocated object or be null

Deleting a pointer to memory that was not allocated by new, or deleting the same pointer value more than once, is undefined. Functions that return pointers (rather than smart pointers) to dynamic memory put a burden on their callers—the caller must remember to delete the memory. When we delete a pointer, that pointer becomes invalid. Although the pointer is invalid, on many machines the pointer continues to hold the address of the (freed) dynamic memory. We can assign nullptr to the pointer after we use delete

搜尋此網誌

I'm Jay's father