課程目標(biāo)

• level 0: 淺嘗C++標(biāo)準(zhǔn)庫
• level 1: 深入認(rèn)識(shí)C++標(biāo)準(zhǔn)庫 (胸中自有丘壑)
• level 2: 良好使用C++標(biāo)準(zhǔn)庫
• level 3: 擴(kuò)充C++標(biāo)準(zhǔn)庫

C++ Standard Library vs. Standard Template Library

• C++ Standard Library (C++標(biāo)準(zhǔn)庫)
• Standard Template Library (STL, 標(biāo)準(zhǔn)模板庫) (note: STL 可以看成是C++標(biāo)準(zhǔn)庫的一個(gè)子集)

標(biāo)準(zhǔn)庫以header files形式呈現(xiàn):

• C++標(biāo)準(zhǔn)庫的header files不帶副檔名(.h), 例如#include<vector>
• 新式C header files不帶副名檔.h, 例如#include<cstdio>
• 舊式C header files(帶有副檔名.h)仍然可用, 例如#include<stdio.h>
• 新式headers內(nèi)的組件封裝于namespace "std"
  • using namespace std; or
  • using std::cout; (for example)
• 舊式headers內(nèi)的組件不封裝于namespace "std"

幾個(gè)重要網(wǎng)頁

• CPlusPlus.com -- The C++ Resources Network
• CppReference.com -- C++ 參考手冊
• gcc.gnu.org/onlinedocs -- GCC online documentation

書目志

1. The C++ Standard Library - A Tutorial and Reference (2nd Edition) by Nicolai M. Josuttis
2. STL源碼剖析 by 侯捷

STL六大部分

STL六大部件(Components):

• 容器(Containers)
• 分配器(Allocators)
• 算法(Algorithm)
• 迭代器(Iterators)
• 適配器(Adapters)
• 仿函式(Functors)

一個(gè)包含STL六大部件的程序

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

using namespace std;

int main()
{
  int ia[ 6 ] = { 27, 210, 12, 47, 109, 83 };
  vector<int, allocator<int>> vi(ia, ia+6);
  cout << count_if(vi.begin(), vi.end(), 
            not1(bind2nd(less<int>(), 40)));
  return 0;
}

stl-6-comp.png

復(fù)雜度, Complexity, Big O

目前常見的big O有下列幾種情形:

1. O(1)或O(c): 稱為常數(shù)時(shí)間(constant time)
2. O(n): 稱為線性時(shí)間(linear time)
3. O(log2(n)): 稱為次線性時(shí)間(sub-linear time)
4. O(n^2): 稱為平方時(shí)間(quadratic time)
5. O(n^3): 稱為立方時(shí)間(cubic time)
6. O(2^n): 稱為指數(shù)時(shí)間(exponential time)
7. O(nlog2(n)): 介于線性及二次方成長的中間之行為模式

前閉后開

Container<T> c;
...
Container<T>::iterator ite;
for (ite = c.begin(); ite != c.end(); ++ite)
  ...

關(guān)于end()的一些解釋 (摘自C++ Primer):

The iterator returned by end is an iterator positioned “one past the end” of the associated container (or string). This iterator denotes a nonexistent element “off the end” of the container. It is used as a marker indicating when we have processed all the elements. The iterator returned by end is often referred to as the off-the-end iterator or abbreviated as “the end iterator.” If the container is empty, begin returns the same iterator as the one returned by end. If the container is empty, the iterators returned by begin and end are equal—they are both off-the-end iterators.

ranged-based for statement (since C++11)

摘自C++ Primer:

The new standard introduced a simpler for statement that can be used to iterate through the elements of a container or other sequence. The syntactic form of the range for statement is:
for (declaration : expression) { statement }
expression must represent a sequence, such as a braced initializer list, an array, or an object of a type such as vector or string that has begin and end members that return iterators. declaration defines a variable. It must be possible to convert each element of the sequence to the variable’s type. The easiest way to ensure that the types match is to use the auto type specifier. That way the compiler will deduce the type for us. If we want to write to the elements in the sequence, the loop variable must be a reference type. On each iteration, the control variable is defined and initialized by the next value in the sequence, after which statement is executed. As usual, statement can be a single statement or a block. Execution ends once all the elements have been processed.

例子:

for (int i : {2 , 3, 5, 7, 9, 13, 17, 19}) {
  std::cout << i << std::endl;
}
std::vector<double> vec;
...
// pass by value
for (auto elem : vec) {
  std::cout << elem << std::endl;
}
// pass by reference
for (auto &elem : vec) {
  elem *= 3;
}

auto keyword (since C++11)

摘自C++ Primer:

It is not uncommon to want to store the value of an expression in a variable. To declare the variable, we have to know the type of that expression. When we write a program, it can be surprisingly difficult—and sometimes even impossible—to determine the type of an expression. Under the new standard, we can let the compiler figure out the type for us by using the auto type specifier. Unlike type specifiers, such as double, that name a specific type, auto tells the compiler to deduce the type from the initializer. By implication, a variable that uses auto as its type specifier must have an initializer.

例子:
不使用auto:

list<string> c;
...
list<string>::iterator ite;
ite = ::find(c.begin(), c.end(), target);

使用auto:

list<string> c;
...
auto ite = ::find(c.begin(), c.end(), target);

容器--結(jié)構(gòu)與分類

container.png

評(píng)論: 容器主要分為Sequence container和Associative container兩大類, 而Associative container又可按照Elements Ordered/Not Ordered by Key分成兩類. 具體的容器的定義和討論可見以下兩個(gè)小節(jié).

Sequence Containers

摘自C++ Primer:

The sequential containers, which are listed in the Table, all provide fast sequential access to their elements. However, these containers offer different performance trade-offs relative to 1. The costs to add or delete elements to the container; 2. The costs to perform nonsequential access to elements of the container
With the exception of array, which is a fixed-size container, the containers provide efficient, flexible memory management. We can add and remove elements, growing and shrinking the size of the container. The strategies that the containers use for storing their elements have inherent, and sometimes significant, impact on the
efficiency of these operations. In some cases, these strategies also affect whether a particular container supplies a particular operation.
For example, string and vector hold their elements in contiguous memory. Because elements are contiguous, it is fast to compute the address of an element from its index. However, adding or removing elements in the middle of one of these containers takes time: All the elements after the one inserted or removed have to be moved to maintain contiguity. Moreover, adding an element can sometimes require that additional storage be allocated. In that case, every element must be moved into the new storage.
The list and forward_list containers are designed to make it fast to add or remove an element anywhere in the container. In exchange, these types do not support random access to elements: We can access an element only by iterating through the container. Moreover, the memory overhead for these containers is often
substantial, when compared to vector, deque, and array.
A deque is a more complicated data structure. Like string and vector, deque supports fast random access. As with string and vector, adding or removing elements in the middle of a deque is a (potentially) expensive operation. However, adding or removing elements at either end of the deque is a fast operation, comparable to adding an element to a list or forward_list.
The forward_list and array types were added by the new standard. An array is a safer, easier-to-use alternative to built-in arrays. Like built-in arrays, library arrays have fixed size. As a result, array does not support operations to add and remove elements or to resize the container. A forward_list is intended to be comparable to the best handwritten, singly linked list. Consequently, forward_list does not have the size operation because storing or computing its size would entail overhead compared to a handwritten list. For the other containers, size is guaranteed to be a fast, constant-time operation.

Associative Container

摘自C++ Primer:

Associative and sequential containers differ from one another in a fundamental way: Elements in an associative container are stored and retrieved by a key. In contrast, elements in a sequential container are stored and accessed sequentially by their position in the container. Although the associative containers share much of the behavior of the sequential containers, they differ from the sequential containers in ways that reflect the use of keys.
Associative containers support efficient lookup and retrieval by a key. The two primary associative-container types are map and set. The elements in a map are key–value pairs: The key serves as an index into the map, and the value represents the data associated with that index. A set element contains only a key; a set supports efficient queries as to whether a given key is present. We might use a set to hold words that we want to ignore during some kind of text processing. A dictionary would be a good use for a map: The word would be the key, and its definition would be the value.
The library provides eight associative containers, listed in the Table. These eight differ along three dimensions: Each container is (1) a set or a map, (2) requires unique keys or allows multiple keys, and (3) stores the elements in order or not. The containers that allow multiple keys include the word multi; those that do not keep their keys ordered start with the word unordered. Hence an unordered_multiset is a set that allows multiple keys whose elements are not stored in order, whereas a set has unique keys that are stored in order. The unordered containers use a hash function to organize their elements.
The map and multimap types are defined in the map header; the set and multiset types are in the set header; and the unordered containers are in the unordered_map and unordered_set headers.