STL与泛型编程 week 1 (Boolan)

课程目标

• level 0: 浅尝C++标准库
• level 1: 深入认识C++标准库 (胸中自有丘壑)
• level 2: 良好使用C++标准库
• level 3: 扩充C++标准库

C++ Standard Library vs. Standard Template Library

• C++ Standard Library (C++标准库)
• Standard Template Library (STL, 标准模板库) (note: STL 可以看成是C++标准库的一个子集)

标准库以header files形式呈现:

• C++标准库的header files不带副档名(.h), 例如#include<vector>
• 新式C header files不带副名档.h, 例如#include<cstdio>
• 旧式C header files(带有副档名.h)仍然可用, 例如#include<stdio.h>
• 新式headers内的组件封装于namespace "std"
  • using namespace std; or
  • using std::cout; (for example)
• 旧式headers内的组件不封装于namespace "std"

几个重要网页

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

一个包含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

复杂度, Complexity, Big O

目前常见的big O有下列几种情形:

1. O(1)或O(c): 称为常数时间(constant time)
2. O(n): 称为线性时间(linear time)
3. O(log2(n)): 称为次线性时间(sub-linear time)
4. O(n^2): 称为平方时间(quadratic time)
5. O(n^3): 称为立方时间(cubic time)
6. O(2^n): 称为指数时间(exponential time)
7. O(nlog2(n)): 介于线性及二次方成长的中间之行为模式

前闭后开

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

关于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);

容器--结构与分类

container.png

评论: 容器主要分为Sequence container和Associative container两大类, 而Associative container又可按照Elements Ordered/Not Ordered by Key分成两类. 具体的容器的定义和讨论可见以下两个小节.

Sequence Containers

摘自C++ Primer:

Sequential Container	Description
vector	Flexble-size array. Supports fast random access. Inserting or deleting elements other than at the back may be slow.
deque	Double-ended queue. Supports fast random access. Fast insert/delete at front or back.
list	Doubly linked list. Supports only bidirectional sequential access. Fast insert/delete at any point in the list.
forward_list	Singly linked list. Supports only sequential access in one direction. Fast insert/delete at any point in the list.
array	Fixed-size array. Supports fast random access. Cannot add or remove elements.
string	A specialized container, similar to vector, that contains characters. Fast random access. Fast insert/delete at the back.

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 Container	Description
Elements Ordered by Key
map	Associative array; holds key-value pairs
set	Container in which the key is the value
multimap	map in which a key can appear multiple times
multiset	set in which a key can appear multiple times
Unordered Collections
unordered_map	map organized by a hash function
unordered_set	set organized by a hash function
unordered_multimap	Hashed map; keys can appear multiple times
unordered_multiset	Hashed set; keys can appear multiple times

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.