C++模板Queue
最后更新于：2022-04-01 19:55:04
《C++ primer》中的一个例子，感觉对模板编程很有帮助，便从头到尾实现了一遍。内部机制实际上是一个链表，但对外呈现队列的特性。代码如下：
~~~
#ifndef __MYQUEUE_H__
#define __MYQUEUE_H__
#include
// 这里必须提前声明
template
class Queue;
template
std::ostream& operator << (std::ostream &, const Queue &);
template
class QueueItem {
// 声明友元关系
friend class Queue;
friend std::ostream& operator << (std::ostream &, const Queue &);
QueueItem(const Type &t) : item(t), next(NULL)
{}
Type item;
QueueItem *next;
};
template
class Queue {
public:
// 声明友元关系
friend std::ostream& operator << (std::ostream &, const Queue &);
Queue() : head(NULL), tail(NULL)
{}
Queue(const Queue &q) : head(NULL), tail(NULL)
{
copy_elems(q);
}
Queue& operator= (const Queue &);
~Queue()
{
destroy();
}
Type& front()
{
if (head == NULL)
throw exception("Queue is empty.");
return head->item;
}
const Type& front() const
{
if (head == NULL)
throw exception("Queue is empty.");
return head->item;
}
void push(const Type&);
void pop();
bool empty() const
{
return head == NULL;
}
private:
QueueItem *head; // 指向Queue头节点
QueueItem *tail; // 指向Queue尾节点
void copy_elems(const Queue &);
void destroy();
};
template
Queue& Queue::operator= (const Queue &q)
{
if (&q == this)
return *this;
destroy();
copy_elems(q);
return *this;
}
// 从尾添加一个节点
template
void Queue::push(const Type &t)
{
QueueItem *tmp = new QueueItem(t);
if (empty())
{
head = tail = tmp;
}
else
{
tail->next = tmp;
tail = tmp;
}
}
// 从头删除一个节点
template
void Queue::pop()
{
if (head != NULL)
{
QueueItem *tmp = head;
head = tmp->next;
delete tmp;
}
}
template
void Queue::destroy()
{
while (!empty())
pop();
}
template
void Queue::copy_elems(const Queue &q)
{
QueueItem *tmp = q.head;
while (tmp != NULL)
{
push(tmp->item);
tmp = tmp->next;
}
}
template
std::ostream& operator << (std::ostream &os, const Queue &q)
{
QueueItem *tmp = q.head;
while (tmp != NULL)
{
os << tmp->item << ' ';
tmp = tmp->next;
}
return os;
}
// Queue的特化版本
template <>
class Queue {
public:
// 声明特化版本的 operator<< 为友元
friend std::ostream& operator <<
(std::ostream &os, const Queue &q);
void push(const char *);
void pop()
{
real_queue.pop();
}
bool empty() const
{
return real_queue.empty();
}
std::string& front()
{
return real_queue.front();
}
const std::string& front() const // 基于const的成员函数重载
{
return real_queue.front();
}
private:
Queue real_queue;
};
void Queue::push(const char *val)
{
real_queue.push(val);
}
template <>
std::ostream& operator << (std::ostream &os, const Queue &q)
{
os << q.real_queue;
return os;
}
#endif
~~~
参考：
《C++ primer》
';
STL算法实现
最后更新于：2022-04-01 19:55:02
写了一点STL算法，模板编程确实有点复杂，编译起来一个error接一个error。有一点体会，STL中的迭代器全都是pass by value，也就是值传递，这一点在《Effective C++》也有说明：内置类型、迭代器、仿函数作为参数应该传值，其它类型尽量传址。
~~~
using namespace std;
// 求给定区域内的和
template
T accumulate(InputIterator begin, InputIterator end, T init)
{
while (begin != end)
{
init += *begin;
begin++;
}
return init;
}
// 给定区域用BinOp仿函数计算结果
template
T accumulate(InputIterator begin, InputIterator end, T init, BinOp op)
{
while (begin != end)
{
init = op(init, *begin);
begin++;
}
return init;
}
// 容器中后一个数减前一个数
template
OutputIterator adjacent_difference(InputIterator begin, InputIterator end, OutputIterator output)
{
if (begin == end)
return output;
// 萃取InputIterator迭代器所指元素的类型
iterator_traits::value_type last = *begin;
*output++ = *begin++;
while (begin != end)
{
iterator_traits::value_type current = *begin++;
*output++ = current - last;
last = current;
}
return output; // 返回迭代器指向输出区间之后
}
// 容器中后一个数和前一个数做BinOp运算
template
OutputIterator adjacent_difference(InputIterator begin, InputIterator end,
OutputIterator output, BinOP op)
{
if (begin == end)
return output;
// 萃取InputIterator迭代器所指元素的类型
iterator_traits::value_type last = *begin;
*output++ = *begin++;
while (begin != end)
{
iterator_traits::value_type current = *begin++;
*output++ = op(current, last);
last = current;
}
return output; // 返回迭代器指向输出区间之后
}
// 求两个序列的内积
template
T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init)
{
while (begin1 != end1)
{
init += *begin1 * *begin2;
++begin1;
++begin2;
}
return init;
}
// 两个序列进行BinOp操作
template
T inner_product(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2, T init)
{
while (begin1 != end1)
{
init += *begin1 * *begin2;
++begin1;
++begin2;
}
return init;
}
// 交换两个迭代器的元素
template
void Iter_swap(ForwardIterator1 iter1, ForwardIterator2 iter2)
{
iterator_traits::value_type value = *iter1;
*iter1 = *iter2;
*iter2 = value;
}
// 针对前向迭代器
template
ForwardIterator __Lower_bound(ForwardIterator first, ForwardIterator last, const T &value, forward_iterator_tag)
{
int len = 0;
distance(first, last, len); // 计算区间长度，前向迭代器无法直接相减
int half;
ForwardIterator middle;
while (len > 0)
{
half = len >> 1;
middle = first;
advance(middle, half); // 一步步向前走
if (*middle < value) // value在右边
{
first = middle;
++first;
len = len - half - 1;
}
else // value在左边
len = half;
}
return first;
}
// 针对随机迭代器
template
RandomIterator __Lower_bound(RandomIterator first, RandomIterator last, const T &value, random_access_iterator_tag)
{
int len = 0;
len = last - first; // 计算区间长度，随即迭代器可直接相减
int half;
RandomIterator middle;
while (len > 0)
{
half = len >> 1;
middle = first + half; // 迭代器直接跳到中间
if (*middle < value) // value在右边
{
first = middle + 1;
len = len - half - 1;
}
else // value在左边
len = half;
}
return first;
}
// 应用于有序区间[first,last)，返回第一个等于value的迭代器
template
ForwardIterator Lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
{
// 萃取迭代器类型，前向迭代器或随机迭代器，最后一个参数是一个临时对象
return __Lower_bound(first, last, value, iterator_traits::iterator_category());
}
~~~
';
C++简易list
最后更新于：2022-04-01 19:55:00
list不同于vector，每个节点的结构需要自行定义，迭代器属于双向迭代器（不是随即迭代器），也需要自行定义。和通用迭代器一样，list的迭代器需要实现的操作有：++、--、*、->、==、!=。节点的数据结构命名为list_node，迭代器的数据结构命名为list_iterator。list中对迭代器的操作不应该使用算数运算，如+2、-3这样的操作，只应该使用++、--来移动迭代器。STI版本的STL使用了一个环形list，list.end()指向一个空白节点（不存放数据）作为尾节点，空白节点的next指针指向第一个节点，空白节点的prev指针指向最后一个节点，这样就能方便的实现begin()和end()操作，当list为空时，空白节点的next和prev均指向自己。这样的设计是很巧妙的，省去了很多插入、删除操作时需要考虑的边界条件。
~~~
#ifndef __MYLIST_H__
#define __MYLIST_H__
// list节点
template
class list_node {
public:
list_node *prev;
list_node *next;
Type data;
};
// list迭代器
template
class list_iterator {
public:
// 迭代器必须定义的五个相应类型
typedef Type value_type;
typedef Type* pointer;
typedef Type& reference;
typedef size_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
list_iterator() : node(NULL)
{}
list_iterator(list_node *x) : node(x)
{}
list_iterator(const list_iterator &x) : node(x.node)
{}
// 成员函数尽量加const
bool operator== (const list_iterator &rhs) const
{
return node == rhs.node;
}
bool operator!= (const list_iterator &rhs) const
{
return !(operator==(rhs)); // 调用现有函数，好的策略
}
// 对迭代器接引用返回指向数据的引用
reference operator* () const
{
return node->data;
}
pointer operator-> () const
{
return &(operator*()); // 调用现有函数，好的策略
}
list_iterator& operator++ ()
{
node = node->next;
return *this;
}
list_iterator operator++ (int)
{
list_iterator old = *this;
++(*this);
return old;
}
list_iterator& operator-- ()
{
node = node->prev;
return *this;
}
list_iterator operator-- (int)
{
list_iterator old = *this;
--(*this);
return old;
}
// 迭代器通过这个指针与某个节点相联系
list_node *node;
};
// list数据结构，SGI中的list是一个环形链表，这里相同
// list内部使用list_node访问每一个保存数据的节点，对外则返回给用户一个list_iterator迭代器，这是需要注意的
template
class List {
public:
typedef list_iterator iterator; // iterator类型是每个容器必备的，应该尽早定义它
typedef size_t size_type;
// 构造函数
List()
{
node = get_node();
// 前后指针都指向自己，表示此list为空
node->next = node;
node->prev = node;
}
iterator begin()
{
return (list_iterator)node->next;
}
iterator end()
{
return (list_iterator)node;
}
bool empty()
{
return node->next == node; // 参见默认构造函数
}
size_type size()
{
size_type len = 0;
distance(begin(), end(), len);
return len;
}
Type& front()
{
return *begin();
}
Type& back()
{
return *(--end());
}
// 插入操作
iterator insert(iterator position, const Type &value)
{
list_node *newNode = create_node(value);
newNode->next = position.node;
newNode->prev = position.node->prev;
position.node->prev->next = newNode;
position.node->prev = newNode;
return (iterator)newNode; // 显示类型转换
}
void push_back(const Type &value)
{
insert(end(), value);
}
void push_front(const Type &value)
{
insert(begin(), value);
}
// 删除操作
iterator erase(iterator position)
{
list_node *next = position.node->next;
list_node *prev = position.node->prev;
prev->next = next;
next->prev = prev;
destroy_node(position.node);
return (iterator)next;
}
void pop_back()
{
iterator tmp = end();
erase(--tmp);
}
void pop_front()
{
erase(begin());
}
// 清除所有节点
void clear()
{
list_node *pnode = node->next;
while (pnode != node)
{
list_node *tmp = pnode->next;
destroy_node(pnode);
pnode = tmp;
}
node->next = node;
node->prev = node;
}
// 删除值为value的所有节点
void remove(const Type &value)
{
// 为了使用上面的erase，这里定义iterator而不是list_node
iterator first = begin();
iterator last = end();
while (first != last)
{
iterator next = first;
++next;
if (*first == value)
erase(first);
first = next;
}
}
private:
// 分配一个节点
list_node* get_node()
{
return alloc.allocate(1);
}
// 释放一个节点
void put_node(list_node *p)
{
alloc.deallocate(p, 1);
}
// 分配并构造一个节点
list_node* create_node(const Type &value)
{
list_node *p = get_node();
alloc.construct(&(p->data), value);
return p;
}
// 析构并释放一个节点
void destroy_node(list_node *p)
{
alloc.destroy(&(p->data));
put_node(p);
}
private:
list_node *node; // 空白节点，指向list.end()
static std::allocator< list_node > alloc; // 空间配置器
};
// 类中的静态成员一定要记得在类外定义，否则链接时会出错
template
std::allocator< list_node > List::alloc;
#endif
~~~
析构函数忘记写了，这里补上：
~~~
~List()
{
clear();
if (node != NULL)
delete node;
}
~~~
测试代码：
~~~
int main()
{
List l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 1 2 3 4 5
List::iterator iter = find(l.begin(), l.end(), 3);
iter = l.erase(iter);
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 1 2 4 5
l.insert(iter, 123);
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 1 2 123 4 5
l.push_front(0);
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 0 1 2 123 4 5
l.pop_back();
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 0 1 2 123 4
l.pop_front();
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// 1 2 123 4
l.clear();
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
// null
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_front(4);
l.push_front(5);
l.push_front(6);
l.remove(1);
l.remove(2);
l.remove(3);
l.remove(5);
copy(l.begin(), l.end(), ostream_iterator(cout, " "));
cout << endl;
system("pause");
return 0;
}
~~~
运行结果：
参考：
《STL源码剖析》
';
C++简易vector
最后更新于：2022-04-01 19:54:57
好久没动手写一点C++程序了，以后没事多模仿STL吧，虽然达不到标准的STL的程序，但简单的功能还是要实现的。STL确实博大精深：泛型编程、容器、算法、适配器...有的是内容可以学。下面是根据STL源码，写的一个非常简单的vector，实现了部分接口。其实vector还是相对很简单的容器了，元素按在内存中连续排列，只需要三个指针就能实现很多的接口。还有一个就是内存的分配，这里采用了一个C++提供的allocator配置器，所以分配起来还是蛮简单的，SGI版本的STL中的配置器为了达到效率的极致，使用了另外的分配器，相当复杂，这里就没有写了。
~~~
#ifndef __MYVECTOR_H__
#define __MYVECTOR_H__
template
class Vector {
public:
typedef T value_type;
typedef value_type* iterator; // vector的迭代器就是原生指针
typedef value_type* pointer;
typedef value_type& reference;
typedef size_t size_type;
public:
Vector() : start(NULL), finish(NULL), end_of_storage(NULL)
{
}
Vector(size_type n, const value_type &value)
{
start = alloc.allocate(n);
end_of_storage = finish = start + n;
uninitialized_fill_n(start, n, value);
}
Vector(size_type n)
{
start = alloc.allocate(n);
end_of_storage = finish = start + n;
uninitialized_fill_n(start, n, value_type());
}
~Vector()
{
// 顺序调用元素的析构函数
for (iterator i = start; i != finish; ++i)
alloc.destroy(i);
// 销毁分配的空间
if (start != NULL)
alloc.deallocate(start, end_of_storage - start);
}
iterator begin() const
{
return start;
}
iterator end() const
{
return finish;
}
size_type size() const
{
return end() - begin(); // 使用接口函数，包裹性更好
}
size_type capacity() const
{
return end_of_storage - begin(); // 使用接口函数，包裹性更好
}
bool empty() const
{
return begin() == end();
}
// 返回的引用可被修改
reference front()
{
return *(begin());
}
// 返回的引用可被修改
reference back()
{
return *(end() - 1);
}
reference operator[] (const size_type n)
{
return *(begin() + n);
}
const reference operator[] (const size_type n) const
{
return *(begin() + n);
}
void push_back(const value_type &value)
{
if (finish == end_of_storage)
reallocate(); // 存储空间已满，则重新分配内存
alloc.construct(finish, value);
++finish;
}
void reallocate();
void pop_back()
{
--finish;
alloc.destroy(finish); // 析构最后一个函数，但不释放空间
}
// 清除一个元素
iterator erase(iterator position)
{
if (position + 1 != finish)
copy(position + 1, finish, position);
--finish;
alloc.destroy(finish);
return position;
}
// 清除一段元素
iterator erase(iterator first, iterator last)
{
if (first < start || last > finish)
throw exception("Invalid input.");
copy(last, finish, first);
int len = last - first;
while (len--)
alloc.destroy(--finish);
return first;
}
void clear()
{
erase(begin(), end());
}
private:
iterator start;
iterator finish;
iterator end_of_storage;
private:
static std::allocator alloc; // 空间配置器，采用静态属性节省空间
};
template
std::allocator Vector::alloc;
template
void Vector::reallocate()
{
size_type oldsize = size();
size_type newsize = 2 * (oldsize == 0 ? 1 : oldsize);
// 分配新的内存空间
iterator newstart = alloc.allocate(newsize);
uninitialized_copy(start, finish, newstart);
// 顺序调用每个元素的析构函数
for (iterator i = start; i != finish; ++i)
alloc.destroy(i);
// 销毁分配的空间，销毁之前主要检查是否为NULL
if (start != NULL)
alloc.deallocate(start, end_of_storage - start);
// 更新下标
start = newstart;
finish = start + oldsize;
end_of_storage = start + newsize;
}
#endif
~~~
insert操作应该算是最复杂的一个接口了，设计到元素的搬移、（可能）重新分配内存等等，这里我只实现了一个最简单的形式：
~~~
template
void Vector::insert(iterator position, const value_type &value)
{
size_type diff = position - start;
if (finish == end_of_storage)
reallocate();
position = start + diff;
// 注意，这里不能使用copy，因为目的地最后一个位置还没有被构造，
// 赋值涉及析构操作，对未构造的对象进行析构，行为未定义
alloc.construct(finish, *(finish - 1));
++finish;
copy_backward(position, finish - 1, finish);
// 不能使用uninitialized_copy，因为这个函数是从前向后构造，这会造成覆盖
//uninitialized_copy(position, finish, position + 1);
// 插入新对象，直接赋值即可
*position = value;
}
~~~
测试程序：
~~~
int main()
{
Vector v;
v.push_back(1);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(2);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(3);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(4);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(5);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
Vector::iterator iter1 = v.begin();
Vector::iterator iter2 = iter1 + 3;
v.erase(iter1, iter2);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.clear();
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(123);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
for (Vector::iterator iter = v.begin(); iter != v.end(); ++iter)
cout << *iter << endl;
system("pause");
return 0;
}
~~~
运行结果：
参考：
《STL源码剖析》
《C++ primer》
';
适配器（adapters）
最后更新于：2022-04-01 19:54:55
定义：将一个class的接口转换为另一个class的接口，使原本因接口不兼容而不能合作的classes，可以一起运作。适配器扮演者轴承、转换器的角色。
分类：
1、容器适配器：改变容器接口。
STL提供两个容器迭代器：queue和stack。它们都是修饰deque后成为另一种风貌的容器。
2、迭代器适配器：改变迭代器接口。
- Insert Iterator：将容器绑定到back_insert_iterator、front_insert_iterator、insert_iterator。它们都是一个类，对它们的赋值操作将转换为对绑定容器的插入操作。为了操作方便，向用户提供的是一个函数，函数中才创建上述类。
以back_inserter为例：
~~~
template
inline back_insert_iterator back_inserter(Container& x) {
return back_insert_iterator(x); // 以容器为参数，创建迭代器适配器
}
~~~
注意，一般迭代器适配器不会以迭代器作为参数，这里通过传入一个容器创建一个迭代器适配器。
下面是back_insert_iterator类的定义：
~~~
template
class back_insert_iterator {
protected:
Container* container; // 注意，这里是一个指向容器的指针
public:
typedef output_iterator_tag iterator_category; // 输出迭代器，只支持自增
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
explicit back_insert_iterator(Container& x) : container(&x) {} // 与容器相绑定
back_insert_iterator&
operator=(const typename Container::value_type& value) {
container->push_back(value);
return *this;
}
back_insert_iterator& operator*() { return *this; }
back_insert_iterator& operator++() { return *this; }
back_insert_iterator& operator++(int) { return *this; }
};
~~~
可以看到，迭代器适配器提供了自增和接引用的接口，但是实际的功能被关闭了。上述代码的关键在于，对迭代器适配器的赋值变为了对容器的插入操作。
下面是我自己写的一个类似于上面的迭代器适配器：
~~~
#include
#include
using namespace std;
template
class my_back_insert_iterator {
protected:
Container* container;
public:
explicit my_back_insert_iterator(Container& x) : container(&x) {}
my_back_insert_iterator&
operator=(const typename Container::value_type& value) {
container->push_back(value);
return *this;
}
};
int main()
{
vector vec;
my_back_insert_iterator< vector > back_insert(vec);
back_insert = 1;
back_insert = 2;
back_insert = 3;
back_insert = 4;
vector::iterator iter = vec.begin();
for ( ; iter != vec.end(); ++iter)
cout << *iter << endl;
return 0;
}
~~~
运行结果：
对迭代器的赋值即是对容器的插入操作。
- Reverse Iterator：使迭代器行进方向逆转。逆向迭代器一般用在容器中，容器都会提供一些接口，如下所示，使它可以和某些算法配合，逆向完成某些操作。
容器中的接口如下：
~~~
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }
~~~
在看一下reverse_iterator的构造函数：
~~~
Iterator current; // 保存传入的迭代器
....
typedef Iterator iterator_type;
typedef reverse_iterator self;
explicit reverse_iterator(iterator_type x) : current(x) {} // 构造函数
~~~
构造函数的任务就是把传入的迭代器保存在内部的current中。
下面是反向迭代器的关键所在：
~~~
reference operator*() const {
Iterator tmp = current;
return *--tmp; // 先自减，再接引用
}
self& operator++() {
--current;
return *this;
}
self& operator--() {
++current;
return *this;
}
~~~
这里要注意的是接引用操作，先要把迭代器减1，这样才能保证对尾端元素的接引用是正确的。
测试代码如下：
~~~
int a[] = {9,5,4,8,3,6,7};
reverse_iterator reverite(a+7);
cout << *reverite++ << " ";
cout << *reverite++ << " ";
cout << *reverite++ << " ";
~~~
运行结果：
- IOStream Iterator：将迭代器（istream_iterator或ostream_iterator）绑定到某个iostream对象（cin/cout）上，从而操作这些IO对象。
以绑定标准输出为例，测试代码如下：
~~~
int a[] = {9,5,4,8,3,6,7};
ostream_iterator outite(cout, " "); // 输出数组元素时附带输出空格
copy(a, a+7, outite);
~~~
运行结果：
上述代码将迭代器适配器绑定到标准输出，并且每输出一个元素，附带输出一个空格符。对迭代器的赋值（operator=）就是对它的输出操作（operator<<）。源代码如下：
~~~
template
class ostream_iterator {
protected:
ostream* stream; // 绑定的标准输出
const char* string; // 分隔符
public:
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
ostream_iterator(ostream& s) : stream(&s), string(0) {}
ostream_iterator(ostream& s, const char* c) : stream(&s), string(c) {}
ostream_iterator& operator=(const T& value) {
*stream << value; // 关键点
if (string) *stream << string; // 输出间隔符
return *this;
}
// 以下三个操作都返回自己
ostream_iterator& operator*() { return *this; }
ostream_iterator& operator++() { return *this; }
ostream_iterator& operator++(int) { return *this; }
};
~~~
注意最后三个操作都只是本身，这样做的目的是可以配合copy()等算法：
*result = *first;
result就是该迭代器，对它接引用然后进行赋值操作将调用上面的operator=函数，使得copy()算法能够把一段范围内的元素输出到标准输出。这也正是泛型算法的精妙之处：算法只负责做固定工作，至于具体如何实现，由各个迭代器来完成。
3、函数适配器：改变仿函数/函数接口，用于特化和扩展一元和二元函数对象，使其能够适应STL算法的参
数接口。标准库将它分两类：
- 绑定器（bind1st/bind2nd）：将一个操作数绑定到给定值而将二元函数对象转换为一元函数对象。
- 求反器：将谓词函数对象的真值求反。
以count_if为例，应用程序调用如下代码：
~~~
// 计算容器中小于等于3的元素个数
cout << count_if(vec.begin(), vec.end(), bind2nd(less_equal(), 3));
~~~
则会调用如下函数：
~~~
template
void count_if(InputIterator first, InputIterator last, Predicate pred,
Size& n) {
for ( ; first != last; ++first)
if (pred(*first)) /* 对每个元素调用仿函数 */
++n; /* 满足条件则累加 */
}
~~~
下面看看pred，也就是bind2nd的源代码：
~~~
template
class binder2nd
: public unary_function {
protected:
Operation op;
typename Operation::second_argument_type value;
public:
binder2nd(const Operation& x, // 仿函数
const typename Operation::second_argument_type& y) // 绑定的第二个数
: op(x), value(y) {}
typename Operation::result_type
operator()(const typename Operation::first_argument_type& x) const {
return op(x, value); // 关键点
}
};
~~~
代码一目了然。需要注意一点，此函数适配器必须要继承自unary_function对象，满足可配接性。解释一下可配接性。less_equal类继承自binary_function，便有了内部嵌套类型second_argument_type，而这个类型正好需要用在binder2nd中，以保存（绑定）某个参数。这样，less_equal就变为了可配接的。如果还有其它的适配器需要继续作用在binder2nd上，那么binder2nd也需要提供这样的嵌套类型，使它变为可配接的。这在另一篇文章“仿函数”中也有所说明。
总结：
纵观整个适配器系统，基本上都是把某个对象或指向对象的指针封装在一个适配器类中，对适配器的操作最终都会传递到对所包含对象的操作上来。
参考：
《C++ primer》 P453.
《STL源码剖析》 第八章。
';
仿函数
最后更新于：2022-04-01 19:54:53
仿函数就是函数对象，只不过仿函数是老的叫法。仿函数和函数指针都可以作为参数传入函数，但仿函数的优势在于，它对类型抽象度高，并且能够和函数适配器进行匹配，但函数指针却不行。
类似于迭代器需要包含五种相应类型，为了满足可配接能力，仿函数需要定义一些类型，这在分析适配器代码的时候会看到。这个任务交给了一个基类来完成，它的内部定义了这些类型，其它的仿函数只需要继承这些基类即可。基类定义如下：
~~~
template
struct unary_function { // 一元仿函数
typedef Arg argument_type; // 函数/仿函数唯一参数类型
typedef Result result_type; // 函数/仿函数返回值
};
template
struct binary_function { // 二元仿函数
typedef Arg1 first_argument_type; // 仿函数参数1
typedef Arg2 second_argument_type; // 仿函数函数2
typedef Result result_type; // 仿函数返回类型
};
~~~
用户自定义的仿函数，只要继承了相应的基类，就具有了可配接能力。以下是测试代码：
~~~
#include
#include
#include
using namespace std;
template
class les: public binary_function {
public:
bool operator() (const T &lhs, const T &rhs) const
{ return lhs < rhs; }
};
int main()
{
int array[] = {3,4,1,7,5,9,5};
vector vec(array, array+7);
// 找出容器内小于10的元素个数
cout << count_if(vec.begin(), vec.end(), bind2nd(les(), 7));
return 0;
}
~~~
运行结果：
注意上面的les仿函数继承自二元仿函数binary_function，这样它就能与适配器bind2nd正常配接，否则会在运行期发生错误。
按操作数个数划分，可分为：
- 一元仿函数
- 二元仿函数
按功能划分，可分为：
- 算术运算
- 关系运算
- 逻辑运算
以plus仿函数为例：
~~~
template
struct plus : public binary_function {
T operator()(const T& x, const T& y) const { return x + y; }
};
~~~
其它的仿函数几乎都是这个模样，有些细节上略有不同，这是根据操作符本身的性质决定的。
参考：
《STL源码剖析》 第七章。
';
算法 — sort
最后更新于：2022-04-01 19:54:51
能使用STL的sort系列算法的前提是容器的迭代器必须为随机迭代器。所以，vector和deque天然适用。STL的sort算法采用了一些策略，在不同情况下采用不同的排序算法，以达到各种算法优势互补的效果。基本的原则是：数据量大时采用快速排序，数据量小时采用插入排序（这是对快排常用的一种优化策略），递归层次过深改用堆排序。
首先是插入排序。它的平均和最坏时间复杂度都为O(N²)，量级小于千，那么插入排序还是一个不错的选择。SGI STL的插入排序默认以增序排列，另外还可以传入一个仿函数作为比较规则，这里只说明前者。
外层循环确定一个子区间，i位置的元素需要插入到已排序区间的正确位置上：
~~~
template
void __insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first == last) return; // 容器为空，直接返回
for (RandomAccessIterator i = first + 1; i != last; ++i) // 确定子区间
__linear_insert(first, i, value_type(first));
}
~~~
进入__linear_insert函数：
~~~
template
inline void __linear_insert(RandomAccessIterator first,
RandomAccessIterator last, T*) {
T value = *last; // 新插入元素
if (value < *first) { // 如果比已排序区间的第一个元素还要小
copy_backward(first, last, last + 1); // 使已排序区间整体后移一个位置
*first = value; // 新元素放在开头位置
}
else
__unguarded_linear_insert(last, value);
}
~~~
上面代码的注释已经说明了一种简单的情况，这是只需借用copy_backward算法将元素整体搬移，以腾出第一个位置给新插入元素。但其它情况下就要进入__unguarded_linear_insert函数了：
~~~
template
void __unguarded_linear_insert(RandomAccessIterator last, T value) {
RandomAccessIterator next = last; // 指向新插入元素
--next; // 指向之前一个元素
while (value < *next) { // 发现逆转对
*last = *next; // 较大的元素往后走
last = next;
--next;
}
*last = value; // 新元素放入正确位置
}
~~~
上述函数的目标就是要找到value也就是新插入元素的正确插入位置。以value位置为起点，前向遍历已排序区间，遇到比value大的就后移一个位置，以消除逆转对的存在。注意，这里不需要进行越界判断，因为value肯定不会插入到区间头部。
当遇到大数据量时，效率为平方级的插入排序就不适用了。这时STL改用快速排序，平均效率为O(NlogN)，最坏效率为O(N²)。
快排首先要选取枢轴，STL采用的方法是选取前、中、后三点的中值作为枢轴。接下来是分割，遍历整个迭代器，小于枢轴的放左边，大于枢轴的放右边。具体做法如下：
- first迭代器向后移动，*first大于或等于枢轴时停止。
- last迭代器向前移动，*last小于或等于枢轴时停止。
- 若first仍在last的左边，则交换*first和*last，并调整两个迭代器指向下一个位置。
- 重复上述行为直到first和last交叉，first即为右半部分起始位置。
分割代码如下：
~~~
template // 快排的分割函数
RandomAccessIterator __unguarded_partition(RandomAccessIterator first,
RandomAccessIterator last,
T pivot) {
while (true) {
while (*first < pivot) ++first; // 向后移动直到*first大于或等于枢轴
--last;
while (pivot < *last) --last; // 向前移动直到*last小于或等于枢轴
if (!(first < last)) return first; // 交叉后停止，返回的迭代器作为右子区间的开头
iter_swap(first, last); // 交换两个迭代器所指元素
++first;
}
}
~~~
现在来看看sort算法的对外接口：
~~~
template
inline void sort(RandomAccessIterator first, RandomAccessIterator last) {
if (first != last) {
__introsort_loop(first, last, value_type(first), __lg(last - first) * 2);
__final_insertion_sort(first, last);
}
}
~~~
要阅读__introsort_loop函数，先要了解introsort。以下是维基百科里的解释：
内省排序（英语：Introsort）是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度（深度为排序元素数量的对数值）后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持O(nlogn)的时间复杂度。
个人理解，最坏情况发生在分割深度过深时，以中值作为枢轴的方法并不能选出合适的枢轴，导致分割时频繁地交换元素，使效率下降到O(N)。
上述代码中的__lg(last - first) * 2就是根据元素个数计算深度阈值，当分割深度超过阈值时，转而采用堆排序，是效率继续保持为O(nlogn)。
~~~
template
inline Size __lg(Size n) { // 控制分割恶化的情况，求2^k <= n的最大k值
Size k;
for (k = 0; n != 1; n >>= 1) ++k;
return k;
}
~~~
例如，当元素个数为40时，最多允许分割10层。
有了上面内省排序的基础，下面的代码就很容易看了：
~~~
template
void __introsort_loop(RandomAccessIterator first,
RandomAccessIterator last, T*,
Size depth_limit) {
while (last - first > __stl_threshold) { // 大于某个值才进行快速排序，这里__stl_threshold = 16
if (depth_limit == 0) {
partial_sort(first, last, last); // 分割恶化，采用堆排序
return;
}
--depth_limit;
RandomAccessIterator cut = __unguarded_partition
(first, last, T(__median(*first, *(first + (last - first)/2),
*(last - 1)))); // 采用三点中值作为枢轴进行快速排序
__introsort_loop(cut, last, value_type(first), depth_limit); // 对右半部分递归进行排序
last = cut; // 调整last位置，下一次while循环将对左半部分排序
}
}
~~~
partial_sort已经在另一篇文章中详细分析过了，实际上就是对整个区间进行堆排序。__median函数就是求取前、中、后三个元素中值作为枢轴，其它函数都已经在上面讲解过了。递归分段排序，典型的分治策略。当__introsort_loop函数返回时，要么完全已排序，要么大体已排序。大体已排序则要进行微调，即sort函数调用完__introsort_loop之后调用__final_insertion_sort进行微调：
~~~
template
void __final_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
if (last - first > __stl_threshold) { // 超过16个元素，则分割为两段
__insertion_sort(first, first + __stl_threshold); // 前段使用插入排序
__unguarded_insertion_sort(first + __stl_threshold, last); // 剩余元素逐个插入
}
else
__insertion_sort(first, last); // 元素个数不超过16，直接使用插入排序
}
~~~
注意，为了效率，STL又开始折腾了...，再进入__unguarded_insertion_sort瞧瞧：
~~~
template
void __unguarded_insertion_sort_aux(RandomAccessIterator first,
RandomAccessIterator last, T*) {
for (RandomAccessIterator i = first; i != last; ++i)
__unguarded_linear_insert(i, T(*i)); // 将i所指元素插入已排序的16个元素的序列中，前面已经介绍过了
}
template
inline void __unguarded_insertion_sort(RandomAccessIterator first,
RandomAccessIterator last) {
__unguarded_insertion_sort_aux(first, last, value_type(first));
}
~~~
为什么要这样？当从__introsort_loop函数返回时，要么完全有序，要么大体有序。大体有序时，前面的子区间整体是要小于后面的子区间的，这是introsort操作之后的结果。在__final_insertion_sort中，如果元素个数超过16，先对前16个元素进行插入排序，后面剩下的元素再逐个插入到此有序区间。刚才说了由于已经是大体有序了，所以逐个插入操作不会出现过多的逆转对，这正是插入排序的优势所在。
至此，STL的sort算法分析完了。要读懂STL的心思确实不是意见容易的事情啊。
参考：
《STL源码剖析》 P389.
';
算法 — partial_sort
最后更新于：2022-04-01 19:54:48
partial_sort接受一个middle迭代器，使序列中的middle-first个最小元素以递增顺序排序，置于[first, middle)内。下面是测试代码：
~~~
#include
#include
#include
using namespace std;
int main()
{
int a[] = {10,9,8,7,6,5,4,3,2,1,0};
vector vec(a, a+11);
vector::iterator b = vec.begin();
vector::iterator e = vec.end();
partial_sort(b, b+6, e); // 前6个最小元素排序
while (b != e)
cout << *(b++) << ' ';
return 0;
}
~~~
运行结果：
从结果可以看出，前6个最小元素放在了前6个位置上，而剩下的元素则放于容器后面未排序。
实现partial_sort的思想是：对原始容器内区间为[first, middle)的元素执行make_heap()操作构造一个最大堆，然后拿[middle, last)中的每个元素和first进行比较，first内的元素为堆内的最大值。如果小于该最大值，则互换元素位置，并对[first, middle)内的元素进行调整，使其保持最大堆序。比较完之后在对[first, middle)内的元素做一次对排序sort_heap()操作，使其按增序排列。注意，堆序和增序是不同的。
下面分析STL的源码。partial_sort有两个版本，一个默认以小于作为比较规则，出来的顺序为递增排列。另一个可以传入一个仿函数，即自定义比较规则。这里只分析前者。
~~~
template
inline void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last) {
__partial_sort(first, middle, last, value_type(first));
}
~~~
进入__partial_sort函数：
~~~
template
void __partial_sort(RandomAccessIterator first, RandomAccessIterator middle,
RandomAccessIterator last, T*) {
make_heap(first, middle); // [first, middle)区间构造一个heap
for (RandomAccessIterator i = middle; i < last; ++i)
if (*i < *first) // 当前元素比堆中最大的元素小
__pop_heap(first, middle, i, T(*i), distance_type(first)); // first值放i中，i的原值融入heap并调整
sort_heap(first, middle);
}
~~~
此函数和上面的文字描述基本相同。有一点小的区别在于当*i < *first时，代码中没有互换i所指元素和first所指元素。到底怎么做的？来看看__pop_heap函数：
~~~
template
inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
RandomAccessIterator result, T value, Distance*) {
*result = *first; // 弹出元素放vector尾端
__adjust_heap(first, Distance(0), Distance(last - first), value);
}
~~~
此函数把first中的元素放在了result，也就是i位置上，成功地把最大值挤出了[first, middle)区间。但此时first位置形成了一个空洞，即索引值Distance(0)，所以需要调整heap，这由__adjust_heap函数负责。调整大致过程是找出最大元素放入first，然后把value保存的值插入到堆的适当位置，在这里value即为T(*i)，即把i所指元素融入到了[first, middle)区间。由此可见，__adjust_heap的复用性还是很高的。
再回到__partial_sort函数。for循环就是重复上面的“挤出”和“融入”操作直到容器末尾。当跳出for循环时，区间[first, middle)中已经存放有容器的前middle-first个最小元素了。最后执行sort_heap()，由堆序变为增序排列：
~~~
template
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
while (last - first > 1) pop_heap(first, last--);
}
~~~
弹出堆的最大值并放入尾部，然后缩小堆的范围，循环执行弹出操作直至堆只剩下最后一个元素。这样就可以达到排序效果了。注意，此函数只能用于堆上。若要对整个普通容器施行堆排序操作，可以借partial_sort接口，只需把middle参数改为last即可：
partial_sort(first, last, last);
这种方法用到了STL的快速排序身上，感觉越来越有意思了。
个人觉得这个局部排序还是蛮重要的，至少是它的排序思想很好，要不然STL也不会使用它了。
参考：
《STL源码剖析》 P386.
';
迭代器以及“特性萃取机”iterator_traits
最后更新于：2022-04-01 19:54:46
迭代器是一种行为类似指针的对象，而指针的各种行为中最常见的便是解引用（*）和成员访问（->），此外还有operator++。因此，迭代器最重要的编程工作是对operator*和operator->进行重载工作。关于这部分的代码，可以参考class auto_ptr。
迭代器一般会和某种容器相关联，指向某种类型的元素，这种元素的类型（value_type）叫做相应类型。常用的相应类型有五种：
value_type：迭代器所指对象的类型。
difference_type：两个迭代器之间的距离。
reference：容器内元素的引用。
pointer：容器内元素的指针。
iterator_category：表示迭代器类型，根据迭代器类型激活重载函数。关于这一点，可以参考STL算法advance()。
如果某个函数的返回类型为迭代器的相应类型，那么靠“模板实参推断”是无法实现的，而“特性萃取”技术能够很好的解决这个问题。
为了获得迭代器的相应类型，STL采用了一种称为特性萃取的技术，能够获得迭代器（包括原生指针）的相应类型：
~~~
template
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
~~~
针对原生指针的特化版本：
~~~
template
struct iterator_traits { // 特化版本，接受一个T类型指针
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
template
struct iterator_traits { // 特化版本，接受一个T类型const指针
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef const T* pointer;
typedef const T& reference;
};
~~~
当然，为了符合STL规范，用户自定义的迭代器必须添加这些相应类型，特性萃取机才能有效运作。
参考：
《STL源码剖析》 P80、P85.
';
函数适配器
最后更新于：2022-04-01 19:54:44
《C++ primer》中只说了适用于函数对象的适配器，其实还有针对函数和成员函数的适配器。这些适配器使我们能够将函数/成员函数当作仿函数使用，例如搭配各种泛型算法。从本质上说，是因为让这些函数变成为“可配接的”，即一元仿函数必须继承自unary_function，二元仿函数必须继承自binary_function。
一般函数必须以ptr_fun处理：
一般函数当作仿函数传给STL算法，就语言层面是可以的，但它仍然是不可配接的，因为它还没有具备标准库中仿函数（例如plus）的性质。所以，它无法运用于其它的适配器（例如not1）。
成员函数必须以mem_fun处理：
当容器的元素类型是引用或指针，而我们又以虚成员函数作为仿函数，便可以通过泛型算法完成所谓的多态调用。这是泛型与多态之间的一个重要接轨（稍后解释）。
例如：
~~~
#include
#include
#include
using namespace std;
class Shape {
public: virtual void display() = 0;
};
class Rect : public Shape {
public: virtual void display() { cout << "Rect "; }
};
class Circle : public Shape {
public: virtual void display() { cout << "Circle "; }
};
class Square : public Rect {
public: virtual void display() { cout << "Square "; }
};
int main()
{
vector v;
v.push_back(new Rect);
v.push_back(new Circle);
v.push_back(new Square);
v.push_back(new Circle);
v.push_back(new Rect);
for (int i = 0; i < v.size(); i++)
(v[i])->display();
cout << endl;
for_each(v.begin(), v.end(), mem_fun(&Shape::display));
cout << endl;
return 0;
}
~~~
关于上述代码的语法，参见文章“类成员函数指针”。
代码红色部分把成员函数转换成了可配接的仿函数，通过这句话就可以解释“这是泛型与多态之间的一个重要接轨”的含义了。
泛型：for_each能够接纳各种类型的函数。
多态：根据容器实际对象进行多态调用。
参考：
《STL源码剖析》 P430、P454.
';
空间配置器
最后更新于：2022-04-01 19:54:42
STL定义了两种空间配置器：
- allocator：位于
- alloc：在包含以下头文件，将功能分离：
-
- 全局函数construct()/destroy()：位于，用于构造/析构对象。
- 配置器alloc：位于，用于空间配置，分为一级配置器和二级配置器。
- uninitialized_copy/uninitialized_fill/uninitialized_fill_n：位于，用于填充或复制大块数据。
allocator配置器在分配空间时使用标准库函数operator new/operator delete。处于效率考虑，STL没有使用这个allocator，而是使用了更为精细的alloc配置器，将空间管理和对象管理两个阶段分离开来。
这样是为了解决内存碎片问题，TSL的空间配置器分两级。当申请空间大于128bytes时，使用第一级配置器；当申请空间小于128bytes时，使用第二级配置器。
- 第一级：__malloc_alloc_template，直接使用malloc、realloc、free管理内存。
- 第二级：__default_alloc_template，采用memory pool，由free-list维护。总共有16个free-list，每个free-list串联了一个个的内存块，当申请内存时就从一个适当的free-list中拔出一个区块给用户，用完后在返还给free-list。
两个空间配置器都是通过标准接口allocate()、deallocate()进入空间分配和空间释放的过程的。
无论alloc被定义为第一级或第二级配置器，SGI还为它再包装一个接口simple_alloc，每一个容器都直接包含这个类，当需要配置空间时，再由此类转调用allocate或deallocate：
~~~
template
class simple_alloc { // 对配置器alloc再进行一次封装，容器就使用这个类进行空间管理
public:
static T *allocate(size_t n)
{ return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
static void deallocate(T *p, size_t n)
{ if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
};
~~~
容器内部直接使用这个类分配空间，例如在vector中：
~~~
typedef T value_type;
typedef simple_alloc data_allocator;
~~~
注意只是定义了空间分配器的类型，并没有定义实际对象。
当要分配或删除节点时：
~~~
iterator new_start = data_allocator::allocate(len); // 分配元素空间
data_allocator::deallocate(new_start, len); // 删除元素空间
~~~
利用类型限定符进行空间分配和释放。
参考：
《STL源码剖析》第二章。
';
construct()和destroy()
最后更新于：2022-04-01 19:54:39
STL定义了五个全局函数，作用于未初始化的空间上。
其中两个全局函数construct()和destroy()负责对象的构造和析构，它们隶属于STL标准规范。
构造对象直接使用定位new：
~~~
template
inline void construct(T1* p, const T2& value) {
new (p) T1(value); // 定位new
}
~~~
析构对象分多个版本
版本1：
~~~
template
inline void destroy(T* pointer) {
pointer->~T(); // 直接调用析构函数
}
~~~
版本2：
~~~
template
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(first, last, value_type(first));
}
~~~
它调用：
~~~
template
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
typedef typename __type_traits::has_trivial_destructor trivial_destructor; // 这里使用了萃取器
__destroy_aux(first, last, trivial_destructor());
}
~~~
再根据对象有无必要析构分别调用：
~~~
template
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) { // non-trivial destructor
for ( ; first < last; ++first)
destroy(&*first); // 逐个调用析构函数
}
template
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} // trivial destructor
~~~
另外还有两个版本2的重载版本：
~~~
// 两个重载版本，无需析构
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}
~~~
很显然，对象为字符，则什么也不做。
另外三个全局函数：
- uninitialized_copy
- uninitialized_fill
- uninitialized_fill_n
这三个函数都有不同的重载版本，根据元素是否为POD（传统C struct类型），执行相应的操作，或者直接memmove()，或者调用STL泛型函数，或者分别对每个元素调用构造函数。P77的图已经概括的非常好了。详情参见《“类型萃取器”__type_traits》。
参考：
《STL源码剖析》 P51、P70.
';
顺序容器 — slist
最后更新于：2022-04-01 19:54:37
slist属于单链表，不在标准规格之内，是SGI STL特有的一种顺序容器。由于slist的迭代器属于前向迭代器，不能往前走，所以插入操作和list有所不同。根据STL的习惯，插入操作会将新元素插入于指定位置之前，但slist无法记录前驱节点（需要从头遍历找出前驱节点），所以插入操作提供了insert_after()和erase_after()版本。
slist节点和迭代器的设计比list要复杂许多，它运用了继承关系：
- __slist_node_base作为节点基本结构，派生出__slist_node
- __slist_iterator_base作为迭代器基本结构，派生出__slist_iterator
__slist_iterator_base类中的有一个指向__slist_node_base节点的指针，名叫node，以此来关联迭代器和节点。slist将__slist_iterator作为它的迭代器。至于为什么要搞这么复杂，还没有弄清楚，源码剖析中说是为了更大的弹性。
参考：
《STL源码剖析》 P186.
';
顺序容器 — priority_queue
最后更新于：2022-04-01 19:54:35
拥有权值的queue，权值最高者永远排在最前面。priority_queue以vector为底层容器，配合heap的一套泛型算法，就能实现相应功能。
代码如下：
~~~
template ,
class Compare = less >
class priority_queue {
....
protected:
Sequence c; // 底层容器
Compare comp; // 比较标准
....
template
priority_queue(InputIterator first, InputIterator last, const Compare& x)
: c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); } // 将vector变为heap
template
priority_queue(InputIterator first, InputIterator last)
: c(first, last) { make_heap(c.begin(), c.end(), comp); } // 将vector变为heap
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type& x) {
__STL_TRY {
c.push_back(x); // 先压入vector
push_heap(c.begin(), c.end(), comp); // 再调整
}
__STL_UNWIND(c.clear());
}
void pop() {
__STL_TRY {
pop_heap(c.begin(), c.end(), comp); // 最大元素放vector尾部
c.pop_back(); // 弹出
}
__STL_UNWIND(c.clear());
}
};
~~~
priority_queue内部代码很简单，都是直接调用vector或heap的提供的一些接口。由于priority_queue和queue一样也具有“先进先出”的性质，所以没有定义迭代器。
参考：
《STL源码剖析》 P183.
';
顺序容器 — queue
最后更新于：2022-04-01 19:54:33
作为一种先进先出数据机构，同样不允许遍历行为，不存在迭代器。同stack一样，queue也是将deque作为底层容器。
源码如下：
~~~
template >
class queue {
....
protected:
Sequence c; // 底层容器
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); } // 尾端进
void pop() { c.pop_front(); } // 前端出
};
~~~
所有对queue的操作都转调用底层容器deque的的接口。
queue的底层容器默认使用deque，用户可以自己修改：
queue > iqueue;
参考：
《STL源码剖析》 P169.
';
顺序容器 — stack
最后更新于：2022-04-01 19:54:30
具有修改某物接口，形成另一种风貌之性质者，称为适配器。stack便是以deque为底层容器，适当封闭一些功能而形成一种具有“先进后出”特性，并不允许遍历行为的容器适配器。因为不能遍历容器，故stack没有迭代器。
源码如下：
~~~
template >
class stack {
....
protected:
Sequence c; // 底层容器
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); } // deque末端进
void pop() { c.pop_back(); } // deque末端出
};
~~~
从代码可以看出，stack的所有操作都是转调用了底层容器deque的相应操作，所以stack的定义非常简单，这里就不做多的分析了。
stack默认使用deque作为底层容器，但定义stack时可以自己定义底层容器，如：
stack > istack;
由于list也具有empty、size、back、push_back、pop_back等功能，所以用list作为底层容器是合法的。
参考：
《STL源码剖析》 P167.
';
算法 — copy
最后更新于：2022-04-01 19:54:28
为了效率，copy算法可谓无所不用其极，通过分析copy算法能够体会STL的精妙。
首先是三个对外接口：
~~~
template // 泛化版本
inline OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result)
{
return __copy_dispatch()(first, last, result);
}
inline char* copy(const char* first, const char* last, char* result) { // 针对原生指针的重载
memmove(result, first, last - first);
return result + (last - first);
}
inline wchar_t* copy(const wchar_t* first, const wchar_t* last, // 针对原生指针的重载
wchar_t* result) {
memmove(result, first, sizeof(wchar_t) * (last - first));
return result + (last - first);
}
~~~
如果传入的迭代器是字符型的原生指针，那么直接使用底层的memmove拷贝，效率是非常高的，但如果是普通的迭代器，则需要进一步分析了。再看看__copy_dispatch函数，此函数又兵分三路，包括一个泛化版本和两个偏特化版本：
~~~
template // 泛化版本
struct __copy_dispatch
{
OutputIterator operator()(InputIterator first, InputIterator last,
OutputIterator result) {
return __copy(first, last, result, iterator_category(first));
}
};
template
struct __copy_dispatch // 特化版本
{
T* operator()(T* first, T* last, T* result) {
typedef typename __type_traits::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
template
struct __copy_dispatch // 特化版本
{
T* operator()(const T* first, const T* last, T* result) {
typedef typename __type_traits::has_trivial_assignment_operator t;
return __copy_t(first, last, result, t());
}
};
~~~
首先分析泛化版本。如果迭代器仍为普通迭代器，则调用泛化版本。它要根据迭代器的类型（输入或随机）调用不同的函数：
~~~
template
inline OutputIterator __copy(InputIterator first, InputIterator last,
OutputIterator result, input_iterator_tag) // 输入迭代器
{
for ( ; first != last; ++result, ++first)
*result = *first;
return result;
}
template
inline OutputIterator
__copy(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, random_access_iterator_tag) // 随机迭代器
{
return __copy_d(first, last, result, distance_type(first));
}
~~~
由于输入迭代器的移动只能靠operator++，所以采用逐个赋值。如果是随机迭代器，则继续往下调用：
~~~
template
inline OutputIterator
__copy_d(RandomAccessIterator first, RandomAccessIterator last,
OutputIterator result, Distance*)
{
for (Distance n = last - first; n > 0; --n, ++result, ++first)
*result = *first;
return result;
}
~~~
这里之所以要再单独定义一个函数是因为下述的原生指针版本也可能会调用它。由于是随机迭代器，所以它是以n是否大于0为循环判断条件。相比于输入迭代器的判断条件first != last，这个版本显然效率是要高一些的。这就充分利用了迭代器之间的区别尽可能的进行效率优化。
下面分析两个特化版本。当迭代器为原生指针时，调用__copy_t，它的第三个参数是用来判断指针所指类型是否真的需要用复制操作符来一个个复制（也就是判断是trivial还是non-trivial），这种判断工作就交给了类型萃取器__type_traits来完成。
根据是否需要单独复制可以把__copy_t分成两个版本：
~~~
template
inline T* __copy_t(const T* first, const T* last, T* result, __true_type) { // trivial
memmove(result, first, sizeof(T) * (last - first));
return result + (last - first);
}
template
inline T* __copy_t(const T* first, const T* last, T* result, __false_type) { // non-trivial
return __copy_d(first, last, result, (ptrdiff_t*) 0);
}
~~~
trivial版本就很容易了，直接memmove，不需要做过多的复制动作。而non-trivial版本的拷贝则需要逐一进行。由于原生指针属于随机迭代器，所以它可以退而求其次，调用刚才介绍的__copy_d函数。
至此，一个既支持泛化，又具有极高效率的copy函数诞生了！
参考：
《STL源码剖析》 P314.
';
关联容器 — hash_map
最后更新于：2022-04-01 19:54:26
hash_map和map的用法很相似，只是底层机制有所不同。
hash_map容器采用的底层机制是hash table代码：
~~~
template ,
class EqualKey = equal_to,
class Alloc = alloc>
class hash_map
{
private:
typedef hashtable, Key, HashFcn,
select1st >, EqualKey, Alloc> ht;
ht rep; // 底层机制——hash table
....
}
~~~
注意，hashtable类型的第一个类型参数是pair，继续跟踪hashtable代码：
~~~
template
class hashtable { // hash table数据结构
public:
typedef Key key_type;
typedef Value value_type;
....
typedef __hashtable_node node;
typedef simple_alloc node_allocator; // 空间配置器
vector buckets; // 桶的集合
....
}
~~~
可以看出，Value或value_type的实际类型是一个pair，那么一个node中也存储了一个pair，而vector中的bucket还是指针不变。即每个bucket指向一串nodes，每个node中存放一个pair。这和map容器是类似的，map容器底层的红黑树中，每个节点也是存储了一个pair。
下面是测试代码：
~~~
#include
#include
#include
using namespace std;
using namespace __gnu_cxx;
struct eqstr {
bool operator() (const char *s1, const char *s2) const
{ return strcmp(s1, s2) == 0; }
};
int main()
{
hash_map, eqstr> m;
// 两种插入方法
m["hello"] = 123;
m["byebye"] = 234;
m["test"] = 345;
m.insert(pair("a", 222));
hash_map, eqstr>::iterator iter = m.begin();
for ( ; iter != m.end(); ++iter)
cout << iter->first << ' ' << iter->second << endl;
return 0;
}
~~~
运行结果：
由于hash_map提供的默认键值比较标准为equal_to：
~~~
template
struct equal_to : public binary_function {
bool operator()(const T& x, const T& y) const { return x == y; }
};
~~~
这个仿函数只是简单的拿两个值进行比较，如果传入的key为const char *，那么比较的将会是两个地址，这不是我们想要的。正确的字符串比较应该是逐个字符进行比较，这就是为什么要定义eqstr的原因。
从运行结果也能够看出，和hash_set一样，hash_map内的元素无特定排序。
参考：
《STL源码剖析》 P275.
';
关联容器 — hash_set
最后更新于：2022-04-01 19:54:24
容器hash_set是以hash table为底层机制的，几乎所有的操作都是转调用hash table提供的接口。由于插入无法存储相同的键值，所以hash_set的插入操作全部都使用hash table的insert_unique接口，代码如下：
~~~
pair insert(const value_type& obj)
{
pair p = rep.insert_unique(obj);
return pair(p.first, p.second);
}
~~~
再看一下一个构造函数：
~~~
private:
typedef hashtable,
EqualKey, Alloc> ht;
ht rep; // 底层机制——hash table
public:
hash_set() : rep(100, hasher(), key_equal()) {} // 默认大小为100
~~~
这里把hash table的表格大小，也就是vector大小设置为了100，那么在初始化hash table时，会自动选择最接近的质数为197。也就是说一开始hash_set便拥有了197个“桶”。
下面来比较一下set和hash_set的异同：
set的底层机制为红黑树，hash_set的底层机制为hash table，两者都能进行高效率的搜索。红黑树利用了二叉搜索树的特性，而hash table则利用散列技术。但红黑树有自动排序功能而hash table没有，反映出来的结果就是，set的元素有自动排序功能而hash_set没有。下面是测试代码：
~~~
#include
#include
using namespace std;
using namespace __gnu_cxx;
int main()
{
hash_set set;
set.insert(3);
set.insert(196);
set.insert(1);
set.insert(389);
set.insert(194);
set.insert(387);
hash_set::iterator iter = set.begin();
for ( ; iter != set.end(); ++iter)
cout << *iter << ' ';
return 0;
}
~~~
运行结果：
由于有197个桶，所以元素1、194、387被散列到1号桶；3、196、389被散列到3号桶。但新元素是插入到每个桶指向的链表的前端，所以就有了这样的输出顺序。
参考：
《STL源码剖析》 P270.
';
关联容器 — hashtable
最后更新于：2022-04-01 19:54:21
C++ 11已将哈希表纳入了标准之列。hashtable是hash_set、hash_map、hash_multiset、hash_multimap的底层机制，即这四种容器中都包含一个hashtable。
解决碰撞问题的办法有许多，线性探测、二次探测、开链等等。SGI STL的hashtable采用的开链方法，每个hash table中的元素用vector承载，每个元素称为桶（bucket），一个桶指向一个存储了实际元素的链表（list），链表节点（node）结构如下：
~~~
template
struct __hashtable_node
{
__hashtable_node* next;
Value val; // 存储实际值
};
~~~
再来看看hash table的迭代器定义：
~~~
template
struct __hashtable_iterator { // 迭代器
typedef hashtable
hashtable;
....
typedef __hashtable_node node;
// 定义迭代器相应类型
typedef forward_iterator_tag iterator_category; // 前向迭代器
typedef Value value_type;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef Value& reference;
typedef Value* pointer;
node* cur; // 迭代器目前所指节点
hashtable* ht; // 和hashtable之间的纽带
__hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {}
__hashtable_iterator() {}
reference operator*() const { return cur->val; }
pointer operator->() const { return &(operator*()); }
iterator& operator++();
iterator operator++(int);
bool operator==(const iterator& it) const { return cur == it.cur; }
bool operator!=(const iterator& it) const { return cur != it.cur; }
};
~~~
hash table的迭代器不能后退，这里关注迭代器的自增操作，代码如下：
~~~
template
__hashtable_iterator&
__hashtable_iterator::operator++() // 注意类模板成员函数的定义
{
const node* old = cur;
cur = cur->next; // 移动到下一个node
if (!cur) { // 到了list结尾
size_type bucket = ht->bkt_num(old->val); // 根据节点值定位旧节点所在桶号
while (!cur && ++bucket < ht->buckets.size()) // 计算下一个可用桶号
cur = ht->buckets[bucket]; // 找到，另cur指向新桶的第一个node
}
return *this;
}
~~~
hashtable数据结构内容很多，这里只列出少量代码：
~~~
template
class hashtable { // hash table数据结构
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher; // 散列函数类型
typedef EqualKey key_equal;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
....
private:
hasher hash; // 散列函数
key_equal equals; // 判断键值是否相等
ExtractKey get_key; // 从节点取出键值
typedef __hashtable_node node;
typedef simple_alloc node_allocator; // 空间配置器
vector buckets; // 桶的集合，可以看出一个桶实值上是一个node*
size_type num_elements; // node个数
....
}
~~~
SGI STL将hash table的大小，也就是vector的大小设计为28个质数，并存放在一个数组中：
~~~
static const int __stl_num_primes = 28; // 28个质数
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
~~~
当vector容量不足时，会以两倍的容量进行扩充。
下面介绍插入操作，以insert_unique为例：
~~~
// 插入新元素，键值不能重复
pair insert_unique(const value_type& obj)
{
resize(num_elements + 1); // 判断vector是否需要扩充
return insert_unique_noresize(obj); // 直接插入obj
}
~~~
insert操作大致分两步：第一步是扩充（如果需要的话），第二步是插入。
resize代码如下：
~~~
template
void hashtable::resize(size_type num_elements_hint) // 判断是否需要扩充vector
{
const size_type old_n = buckets.size();
if (num_elements_hint > old_n)
{ // 元素个数大于vector容量，则需要扩充vector
const size_type n = next_size(num_elements_hint);
if (n > old_n)
{
vector tmp(n, (node*) 0); // 建立一个临时的vector作为转移目的地
for (size_type bucket = 0; bucket < old_n; ++bucket)
{ // 一个桶一个桶进行转移
node* first = buckets[bucket];
while (first)
{ // 一个节点一个节点进行转移
size_type new_bucket = bkt_num(first->val, n); // 散列过程，对n取模
buckets[bucket] = first->next;
first->next = tmp[new_bucket]; // 这一句和下一句表示从链表前端插入
tmp[new_bucket] = first;
first = buckets[bucket]; // first指向旧vector的下一个node
}
buckets.swap(tmp); // 两个vector的内容互换，使buckets彻底改变
}
}
}
}
~~~
上述代码基本思路就是：先扩充，再移动，最后交换。
- 扩充利用next_size函数。next_size的作用就是从质数表中选取最接近并且不小于num_elements_hint的质数并返回，利用这个较大值开辟一个新vector。
- 移动实质上就是指针的移动。重新对每个节点进行散列，然后从前链入到新的vector中。
- 交换过程就是上面代码红色部分。这里使用了vector内部的swap成员函数，将*this和tmp的内容进行了互换，这是copy-and-swap技术，《Effective C++》条款11有说明这个技术。扩充完vector后，就可以顺利插入需要插入的元素了。
insert_unique_noresize代码如下：
~~~
template
pair::iterator, bool> // 注意，返回一个pair
hashtable::insert_unique_noresize(const value_type& obj) // 直接插入节点，无需扩充
{
const size_type n = bkt_num(obj); // 对obj进行散列，然后模上vector大小，从而确定桶号
node* first = buckets[n]; // first指向对应桶的第一个node
for (node* cur = first; cur; cur = cur->next)
if (equals(get_key(cur->val), get_key(obj))) // 遇到相同node，则直接返回这个node
return pair(iterator(cur, this), false);
// 没有遇到相同node，则在list开头插入
node* tmp = new_node(obj);
tmp->next = first;
buckets[n] = tmp;
++num_elements;
return pair(iterator(tmp, this), true);
}
~~~
这里也是将新节点插入list的开头，详细过程已在注释中说明。
参考：
《STL源码剖析》 P253.
';