C++工程

c++编程之标准库和STL

梳理 C++ 标准库与 STL 的核心组成，并概览常见容器、算法与工具。

1. C++标准库

C++提供了很多库：

  1. 标准 ANSI C 库都可以移植到 C++中。不同于 ANSI C 库的是，C++中需要在库名前加上"c"前缀，而且去掉".h"，例如<cmath>对应于 C 语言就是<math.h>，<cstdlib>对应于 C 语言的<stlib.h>
  2. C++新增的库，例如 <iostream>，<iomanip>，<string>，<fstream>，<sstream>
  3. C++STL：包括容器，迭代器，算法和函数对象
  4. Boost C++库

1.1 C 库和相关头文件

  • <cstring>：待会解释
  • <cmath>：数学计算相关的库
  • <cstdlib>：通用工具，例如异常（abort, exit, EXIT_SUCCESS, EXIT_FAILURE）；环境相关（getenv）；动态内存管理（malloc, free, calloc, realloc），字符解析（atoi, atof, atol, strtod）， 伪随机序列生成（rand, srand, RAND_MAX）；数组搜索和排序（bsearch, qsort）
  • <cctype>：字符类型检测（isalpha, isdigit, isalnum, isspace, isupper, islower, isblank, iscntrl, isgraph, isprint, ispunct, isxdigit）和字符转换（toupper, tolower）
  • <climits>, <cfloat>：Size and limit of integer types (INT_MAX, INT_MIN, UINT_MAX, CHAR_BIT; and SHRT_XXX for short, LONG_XXX for long, LLONG_XXX for long long, CHAR_XXX for char) and floating-point types (DBL_MIN, DBL_MAX, DBL_DIG, DBL_MIN_EXP, DBL_MAX_EXP; and FLT_XXX for float, LDBL_XXX for long double)
  • <ctime>：time, difftime, clock, gmttime, localtime, and etc.
  • <cstdio>: C’s IO operations (scanf, printf, fscanf, fprintf, fopen, fclose, etc)
  • <cassert>, <cerrno>, csignal>: 断言和错误
  • <clocale>：本地化
  • <cstdbool>, <cstdint>, <cstddef>, <cstdarg>:
  • <cuchar>, <cwchar>, <cwcchar>: Unicode 字符

1.2 C++库和相关头文件

  • <ios>, <iostream>, <istream>, <ostream>, <fstream>, <sstream>
  • <iomanip>
  • <string>
  • <regex>
  • <random>
  • <limits>
  • <stdexception>, <exception>
  • <complex>, <tuple>, <valarry>
  • <locale>
  • <typeinfo>
  • <chrono>
  • 其它：<codecvt>, <new>, <ratio>, <system_error>, <type_traits>

1.3 C++ STL 和相关头文件

STL 主要由以下头文件提供：

  • <vector>, <list>, <deque>, <queue>, <stack>, <map>, <set>, <bitset>, <forward_list> (C++11), <unordered_map> (C++11), <unordered_set> (C++11), <array> (C++11)：容器和数据结构模板类
  • <iterator>：迭代器
  • <algorithm>, <numeric>, <functional>, <utility>：算法和函数对象
  • <initializer_list> (C++11), <memroy> (C++11)

1.4 Boost C++库

  • TODO

2. C++ STL

2.1 初探 C++ STL 中的 vector 类

示例 1：构造vector<>和访问元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;


void print(const vector<int> &v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(int argc, char *argv[]) {
	const int SIZE = 10;
	vector<int> numbers(SIZE);

	cout << "size = " << numbers.size() << endl;
	cout << "capacity = " << numbers.capacity() << endl;
	print(numbers);

	srand(time(0));

	for (size_t i = 0; i < numbers.size(); ++i) {
		numbers.at(i) = rand() % 100;
	}

	print(numbers);

	// no error compile and run
	cout << "First element is " << numbers.front() << endl;
	// runtime out_of_range exception
	cout << "Last element is " << numbers.back() << endl;

	cout << numbers[55] << endl;
	// cout << numbers.at(55) << endl;

	return 0;
}

特别说明：

size 是当前 vector 容器真实占用的大小，也就是容器当前拥有多少个容器。

capacity 是指在发生 realloc 前能允许的最大元素数，即预分配的内存空间。

示例 2：使用push_back()和pop_back()来添加和删除元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

void print(const vector<int> &v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << " ";
	}
	cout << endl;
}

int main(int argc, char *argv[]) {
	vector<int> numbers;
	cout << "size = " << numbers.size() << endl;
	cout << "capacity = " << numbers.capacity() << endl;

	srand(time(0));
	for (int i = 0; i < 5; ++i) {
		numbers.push_back(rand() % 100);
	}
	print(numbers);
	cout << "size = " << numbers.size() << endl;
	cout << "capacity = " << numbers.capacity() << endl;

	numbers.pop_back();
	numbers.pop_back();
	print(numbers);
	cout << "size = " << numbers.size() << endl;
	cout << "capacity = " << numbers.capacity() << endl;
	numbers.clear();
	cout << "size = " << numbers.size() << endl;
	cout << "capacity = " << numbers.capacity() << endl;
	return 0;
}

示例 3：使用iterator来访问容器元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>

using namespace std;

void print(vector<string> &v) {
	for (vector<string>::iterator iter = v.begin(); iter != v.end(); ++iter) {
		cout << *iter << " ";
	}
	cout << endl;
}

int main(int argc, char *argv[]) {
	vector<string> strs;
	strs.push_back("apple");
	strs.push_back("orange");
	strs.push_back("banana");
	print(strs);
	cout << "size = " << strs.size() << endl;

	// Test insert()
	strs.insert(strs.begin() + 2, "b4-banana");
	strs.insert(strs.begin() + 1, 2, "b4-orange");
	print(strs);

	// Test arase()
	strs.erase(strs.begin() + 1, strs.begin() + 4);
	print(strs);
	cout << "size + " << strs.size() << endl;

	// insert() from another vector
	vector<string> newStrs;
	newStrs.push_back("1");
	newStrs.push_back("2");
	newStrs.push_back("3");
	strs.insert(strs.begin() + 1, newStrs.begin(), newStrs.end());
	print(strs);
	cout << "size = " << strs.size() << endl;
	return 0;
}

说明：

  • 每一种容器类都有其对应的迭代器
  • vector的begin()和end()成员函数分别返回一个指向集合第一个元素的iterator和指向最后一个元素后的iterator
  • Iterator 很像指针，可以使用*iter来访问元素，++iter来移动到下一个元素
  • insert(iter, item)，在当前 iter 元素前插入 item，insert(iter, n , item)，在当前 iter 前插入 n 个 item
  • erase(first, last)，删除区间$[first, last)$中的所有元素
  • 在 C++11 中可以使用auto来作为 iterator 的类型，从而告诉编译器自动匹配类型：
1
2
3

for (auto iter = strs.begin(); iter != strs.end(); ++iter) {
	cout << *iter << " ";
}
  • C++引入了一种 for-each 循环
1
2
3

for (auto item:strs) {
	cout << item << " ";
}

2.2 vector 模板类

Constructor

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

vector (const allocator_type & alloc = allocator_type());
   // Default Constructor: construct a vector object
vector (size_type n, const value_type & val = value_type(),
        const allocator_type & alloc = allocator_type());
   // Fill Constructor: construct a vector object with n-element filled with val
vector (const vector & v);
   // Copy Constructor
template <class InputIterator>
vector (InputIterator first, InputIterator last,
        const allocator_type & alloc = allocator_type());
   // Range Copy Constructor

Size and Capacity

1
2
3
4
5
6
7
8

size_type size () const;      // Return the size (number of elements)
size_type capacity () const;  // Return the storage allocated (in term of element)
bool empty () const;          // Return true if size is 0
void reserve (size_type n);   // Request for storage to hold n elements
void resize (size_type n, value_type val = value_type());
      // resize to n, remove extra element or fill with val
size_type max_size () const;  // Return the maximum number of element
void shrink_to_fit ();        // (C++11) Request to shrink storage

Accessing Element

1
2
3
4

value_type & operator[] (size_type n);  // [n] operator (without index-bound check)
value_type & at (size_type n);          // Return a reference to n-th element with index-bound check
value_type & front ();    // Return a reference to the first element
value_type & back ();     // Return a reference to the last element

Modifying Contents

1
2
3

void push_back (const value_type & val); // Append val at the end
void pop_back ();                        // Remove the last element
void clear ();                           // Remove all elements

Non-member Friend Functions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

==, !=, <, >, <=, >=    // Comparison Operators
// E.g.
template <class T, class Alloc>
bool operator== (const vector<T,Alloc> & left, const vector<T, Alloc> & right);
   // Compare two vectors
   // For == and !=, first compare the size, then each element with equal algorithm.
   //   Stop at the first mismatch.
   // For <, >, <=, >=, use lexicographical_compare algorithm. Stop at first mismatch.

template <class T, class Alloc>
void swap (vector<T,Alloc> & v1, vector<T,Alloc> v2);
   // Swap the contents of containers v1 and v2.
   // Both shall has the same type, but can have different sizes.

Iterator

1
2
3
4
5
6

iterator begin();  // Return an iterator pointing to the first element
iterator end();    // Return an iterator pointing to the pass-the-end element

reverse_iterator rbegin(); // Return a reverse iterator pointing to the reverse beginning (last element)
                           // increasing a reverse iterator to transverse in reverse order
reverse_iterator rend();   // Return a reverse iterator pointing to the reverse past-the-end

Iterator-based Operations

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

iterator insert (iterator pos, const value_type & val);  // Single-Element: insert element val before iterator pos
void     insert (iterator pos, size_type n, const value_type & val);  // Fill: insert n copies of val before pos
template <class InputIterator>
void     insert (iterator pos, InputIterator first, InputIterator last)
    // Range-copy: copy the range [first, last) and insert before pos.

iterator erase (iterator pos);  // Single-element: remove element pointed to by iterator pos
iterator erase (iterator first, iterator last);  // Range: remove elements between [first,last)

void assign (size_type n, const value_type & val);  // Fill: clear old contents and assign n copies of val
template <class InputIterator>
void assign (InputIterator first, InputIterator last);  // Range: assign [first, last)

2.3 容器

顺序型容器，关联型容器和容器适配器

STL 提供了以下几种类型的容器：

顺序型容器：元素是线性结构组织的

  • vector: dynamically resizable array.
  • deque: double-ended queue.
  • list: double-linked list.

关联型容器：存储 key-value 对的非线性结构

  • set: 没有重复元素，支持快速查找
  • multiset: 允许重复元素，支持快速查找
  • map: 一对一隐射（关联数组），没有重复元素，支持快速 key 查找
  • multimap: 一对一隐射，允许有重复元素，支持快速 key 值查找

容器适配器类：

  • Stack: 后进先出
  • queue: 先进先出
  • priority_queue: 高优先级的位于队列前面