所谓序列式容器：其中的元素都可序但是不一定有序。
1、vector
vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率。
vector的迭代器实际上是普通指针。vector内部有3个iterator：start，finish，end_of_storage，分别表示容器的可使用空间头、目前已使用空间尾和目前和目前可使用空间尾。vector最关键的技术在于内存的管理。
下面这个例子是vector在尾部插入一个元素的时候的实际操作。
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T &x)
{
if(finish!=end_of_storge) //还有备用空间
{
construct(finish, *(finish-1)); //在备用空间处构造一个元素，并以最后一个元素为它的初值
++finish;
T x_copy = x;
copy_backward(position, finish-2, finish-1);//后移
*position = x_copy;
}
else //已经没有备用空间
{
const size_type old_size = size();
const size_type len = old_size!=0? 2*old_size:1;
//长度扩充到2倍
iterator new_start = data_allocator::allocate(len);
iterator new_finish = new_start;
try
{
//拷贝
new_finish = uninitialized_copy(start, position, new_start);
//为新元素设值
construct(new_finish, x);
++new_finish;
//将原vector的备用空间内容也拷贝过来（不知用途）
new_finish = uninitialized_copy(position, finish, new_finish);
}
catch()
{
destroy(new_start, new_finish);
data_allocator::deallocate(new_start, len);
throw;
}
//析构释放原vector
destroy(begin(), end());
deallocate();
//调整迭代器
start = new_start;
finish = new_finish;
end_of_storage = new_start + len;
}
}可以看到，当空间不足的时候，需要以下步骤：申请一个两倍的空间、用以前空间的元素将新空间的前半部分copy初始化、插入一个尾部元素、析构释放原空间、调整迭代器。
2、list
list本身和list的节点是两个不同的结构，需要分开设计。
list节点：
template<class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer prev; //型别为void*，其实可以为__list_node<T>*
void_pointer next;
T data;
};
list是一个双向链表，而且在空间上不是连续储存的，所以需要自定义迭代器，迭代器应该是Bidirectional iterators。除此之外，list 还被设计成一个循环链表，表尾加上一个空白的节点，使其符合“前闭后开”的规则，这样就只需要一个标记，就可以完整的表示整个链表。
list内部提供了一个很重要的迁移操作（transfer）：将某连续范围的元素迁移到某个特定的位置之前，技术只是用到了节点间的指针移动，这个操作为后面的splice、merge、sort等奠定了良好的基础。
由于list的迭代器不是随机迭代器，因此不能够使用STL算法sort()，所以其自己定义了一个sort()的member function。书上说用到的是quick sort，我感觉其实应该是merge sort的变形。代码如下：
template<class T, class Alloc>
void list<T, Alloc>::sort()
{
//以下判断如果是空链表或者仅有一个元素，就不进行操作
if(node->next==node||link_type(node->next)->next==node)
return ;
//一些新的lists，用于中介数据的存放
//counter[0]~counter[63]分别存储1、2、4 ~ (2^64） -1 个元素。都是已序状态（整体不一定已序）。
//每次从list取出来一个元素，就将其与counter[0]进行merge操作，如果counter[0]的元素>1，则将
//counter[0]与counter[1]进行merge操作，直到每个counter[]内的元素不超过前面说的数量。carry是
//进行中转的一个临时list。fill则表示counter现已用了多少个。
list<T, Alloc> carry;
list<T, Alloc> counter[64];
int fill=0;
while(!empty())
{
//将原来的list的元素一个个的取出来
carry.splice(carry.begin(), *this, begin());
int i=0;
while(i<fill&&!counter[i].empty())
{
counter[i].merge(carry);
carry.swap(counter[i++]);
}
carry.swap(counter[i]);
if(i==fill) ++fill;
}
//最后将counter内的所有元素合并到一起。
for(int i=1; i<fill; ++i)
counter[i].merge(counter[i-1]);
swap(counter[fill-1]);
}
个人理解是：由于list不支持随机读取数据，因此如果按照传统的merge sort，获取中间的元素将会耗时很多，因此才有了此改编的merge sort。看别人文章，此算法应该也是Nlog(N)的时间复杂度。空间上由于是直接对节点进行的操作，好像不需要多空间存储临时元素。
3、deque
deque相对于vector而言，不同之处是一个双向开口的连续线性空间。
deque的连续线性空间其实只是一个假象，其实deque是由一段段的定量连续空间组成，由一个中控器map（非STLmap）联系起来，map中的每个元素指向一段定量的连续线性空间。当需要在头或者尾扩充的时候deque之所以看起来像是一个连续的线性空间，其实是deque的迭代器的功劳。
deque在效率上来说是不够vector好的，因此有时候在对deque进行sort的时候，需要先将元素移到vector再进行sort，然后移回来。
template <class T, class Ref, class Ptr, csize_t BufSiz>
struct __deque_iterator //未继承std::iterator,所以需要自己写5个必要的迭代器型别
{
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
typedef __deque_iterator<T, const T&,const T*, BufSiz> const_iterator;
static size_t buffer_size(){return __deque_buf_size(BufSiz, sizeof(T));} //小块连续空间的大小
typedef random_access_iterator_tag iterator_category; //随机迭代器
typedef Ptr pointer;
typedef Ref reference;
typedef size_t seze_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer; //指向map的指针
typedef __deque_iterator;
T *cur; //此迭代器所指的缓冲区的现行元素
T *first; //此迭代器所指缓冲区的头
T *last; //此迭代器所指缓冲区的尾（含备用空间）
map_pointer node; //指向管控中心map
};
//buffer_size()调用的函数(一个全局函数)
inline size_t __deque_buf_size(size_t n, size_t sz)
{
return n!=0? n:(sz<512? size_t(512/sz):size_t(1));
}
在编写deque__iterator的重载操作符的时候有跳转缓冲区的情况。
deque的数据结构：
template<class T, class Alloc=alloc, size_t BufSiz=0>
class deque
{
public:
typedef T value_type;
typedef value_type* pointer;
typedef size_t size_type;
public:
typedef __deque_iterator<T, T&, T*, BufSiz> iterator;
protected:
iterator start; //第一个节点
iterator finish; //表现最后一个节点
map_pointer map; //指向map,map是块连续空间，内部有多个指针指向缓冲区
size_type map_size; //map内有多少指针
}
deque的构造与内存管理：
由于deque的设计思想就是由一块块的缓存区连接起来的，因此它的内存管理会比较复杂。插入的时候要考虑是否要跳转缓存区、是否要新建map节点（和vector一样，其实是重新分配一块空间给map，删除原来空间）、插入后元素是前面元素向前移动还是后面元素向后面移动（谁小移动谁）。而在删除元素的时候，考虑是将前面元素后移覆盖需要移除元素的地方还是后面元素前移覆盖（谁小移动谁）。移动完以后要析构冗余的元素，释放冗余的缓存区。
posted on 2010-05-29 02:45
dead_horse 阅读(336)
评论(0) 编辑 收藏 引用 所属分类:
STL读书笔记