**侯捷老师的C++笔记1--STL**
p1. Basics
OOP
vs.GP
OOP
: 将data
和methods
关联起来,GP
: 将data
和methods
分开来Containers
andAlgorithms
可以各自闭门造車,中间以iterator
连通Algorithms
通过Iterators
确定操作范围,来取Container
的数据1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// default comparator
template<class T>
inline const T& max(const T& a, const T& b) {
return a < b ? b : a;
}
// comparator as one argument
template<class T>
inline const T& max(const T& a, const T& b, Compare comp) {
return comp(a, b) ? b : a;
}
// new comparator
bool strLonger(const string& s1, const string& s2) {
return s1.size() < s2.size();
}
// test
cout << "max of zoo and hello: "
<< max(string("zoo"), string("hello")) << endl; // zoo
cout << "max of zoo and hello: "
<< max(string("zoo"), string("hello"), strLonger) << endl; // hello
C++ Standard Library > Standard Template Library (STL - Generic programming)
- 重要网站:
- Cplusplus[http://cplusplus.com/]
- CppReference[https://en.cppreference.com/w/]
- gcc.gnu.org[http://gcc.gnu.org/]
- 书籍:
The C++ standard Library
STL源码剖析
- STL六大部件(
Components
):- 容器(
containers
) - 分配器(
allocator
) - 算法(
algorithms
) - 迭代器(
iterators
) - 适配器(
adapters
) - 仿函数(
functors
)
- 容器(
- 前闭后开区间:
end
指向最后一个元素的下一个,地址不一定是连续的1
2
3
4
5Container<T> c;
...
Container<T>::iterator ite = c.begin();
for (; ite != c.end(); ++ite)
... range-based for statement (since C++11)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// e.g.1
for (int i : {1, 3, 2, 4}) {
std::cout << i << std::endl;
}
// e.g.2
std::vector<double> vec;
...
//不改变值
for (auto elem: vec) {
std::cout << ekem << std::endl;
}
// 改变值
for (auto& elem: vec) {
elem *= 3;
}- Specialization(特化): 对指定的类型有不一样的操作
- Partial Specialization(偏特化):
- 两个模板参数变成一个
- 范围: 是指针,或者const
ALLocators
VC6
orBC5
orG2.9
的allocator
只是以::operator new
–>malloc()
和::operator delete
–>free()
来完成allocate()
和deallocate()
,没有其他特殊的设计, 会有很多的overhead,每一个数据都需要多余的空间- G2.9的容器用的是另一个分配器(
alloc
)- 根据数据的大小来分配内存块,按照block来分配
malloc()
会直接去拿一个block,所以只带一份overhead- 在G4.9中,变成了
_pool_alloc
Container(容器)
- 分类
Composition
的关系,并非inheritance
C++11
中,slist
–>forward_list
hash_set, hash_map
–>unordered_set, unordered_map
,hash_multiset, hash_multimap
–>unordered_multiset, unordered_multimap
List (双向环状链表)
不能用
::sort()
来排序,因为要randomAccessIterator
, 而list
不属于iterator
的end()
指向一个空白节点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// G2.9
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer prev; // 需要后期转型, 在G4.9有所改变
void_pointer next;
T data;
};
// list's iterators
template<class T, class Ref, class Ptr> // 多余了,只需要传一个即可
struct __list_iterator {
// Iterator必须提供的5种associated types
typedef __list_iterator<T, Ref, Ptr> self;
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef __list_node<T>* link_type;
typedef ptrdiff_t difference_type;
link_type node;
reference operator*() const { return (*node).data; }
pointer operator->() const { return &(operator*()); }
// prefix add, ++i, return reference
self& operator++()
{
node = (link_type)((*node).next); // node是迭代器的指针
return *this; //return by reference
}
// postfix add, i++, with an int argument, return value
self operator++(int)
{
self tmp = *this; // 先唤起copy ctor,所以不会唤起operator*
++*this; // 不会唤起operator*, 因为*this会作为++()的参数
return tmp; // return by value, 唤起copy ctor
}
...
};vector :
当空间不够时,会扩充为原来大小的二倍,需要将原来的数据拷贝到新的地址
连续空间,iterator可以用单纯的指针来表示
const size_type len = old_size != 0 ? 2 * old_size : 1;
vector’s iterator:
vector<int> vec;
vector<int>::iterator ite = vec.begin();
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
26template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator; // T*
typedef value_type& reference;
typedef size_t size_type;
protected:
iterator start;
iterator finish;
iterator end_of_storage;
public:
iterator begin() {return start;}
iterator end() {return finish;}
size_type size() const
{return size_type(finish() - begin());}
size_type capacity() const
{return size_type(end_of_storage - begin());}
// 不直接使用begin和finish是以防之后设计的变化
bool empty() const {return begin() == end();}
// []重载
reference operator[](size_type n)
{return *(begin() + n);}
reference front() {return *begin();}
reference back() {return (*end() - 1);}
};
Array
固定数量的数组,没有ctor也没有dtor
连续空间存储
1
2
3
4
5
6
7
8
9
10
11
12
13
14template<typename _Tp, std::size_t _Nm>
struct array
{
typedef _Tp value_type;
typedef _Tp* pointer;
typedef value_type* iterator;
// support for zero-sized arrays mandatory
value_type _M_instance[_Nm ? _Nm : 1];
iterator begin()
{return iterator(&_M_instance[0]);}
iterator end()
{return iterator(&_M_instance[_Nm]);}
...
};forwar_list: 单向链表
类似于双向链表