Learning

STL学习笔记-4-序列式容器

vector

vector实际上是一个大小不定的线性空间。

vector提供的是Random Access Iterators。

如果加入新的元素时，空间不足以容纳，就会去请求更大的空间，来容纳。

1
2
3
4
5
6
7
8
void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }
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
template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
  if (finish != end_of_storage) {
    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;
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      new_finish = uninitialized_copy(start, position, new_start);
      construct(new_finish, x);
      ++new_finish;
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    destroy(begin(), end());
    deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

list

list是一种链表。

list.sort()

STL为list设计的sort算法速度及其高，但是占用内存还挺多的。因为它建立65个空的list来作为中间介质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class T, class Alloc>
void list<T, Alloc>::sort() {
  if (node->next == node || link_type(node->next)->next == node) return;
  list<T, Alloc> carry;
  list<T, Alloc> counter[64];
  int fill = 0;
  while (!empty()) {
    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;
  } 

  for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
  swap(counter[fill-1]);
}

对应的counter[i]在使用的时候会存储2^i个元素，否则就存储0个元素。大量使用了merge，速度极快。原书中作者注释有误，此处应该是归并排序而非quick sort（快排）。

deque

deque从逻辑上来看，是连续空间的，同vector不同的在于它可以在连续空间的两端进行操作，而且deque在空间需要增长的时候不像vector需要大量的操作，因为它的空间连续性是个假象。因此，deque的最大任务便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

deque采用一块所谓的map作为主控，这里所谓的map是一小块连续空间，其中每个元素都是一个指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区。

分享到