文档章节

STL 源码注释(2)——Vector

突然帅了
 突然帅了
发布于 2015/04/19 15:02
字数 1645
阅读 17
收藏 0

(为了保证代码的简洁性,源码中若干地方省去了异常处理环节,后续还有其他容器的源码注释)

1、vector的初始化和回收机制:

2、vector内存的动态增长

3、vector的API如下:

构造函数:

      vector() : start(0), finish(0), end_of_storage(0) {}"初始化的vector为空"
      vector(size_type n, const T& value) { fill_initialize(n, value); }
      vector(int n, const T& value) { fill_initialize(n, value); }
      vector(long n, const T& value) { fill_initialize(n, value); }
      explicit vector(size_type n) { fill_initialize(n, T()); }
      vector(const vector<T, Alloc>& x) {"把另一个vector中每一个元素都拷贝到新的vector(先分配空间再拷贝容器中元素)"
        start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());"见初始位置"
        finish = start + (x.end() - x.begin());
        end_of_storage = finish;
      }
      template <class InputIterator>
      vector(InputIterator first, InputIterator last) :"按迭代器所指的范围拷贝,注意:迭代器的类型应覆盖所有迭代器的类型"
        start(0), finish(0), end_of_storage(0)
      {
        range_initialize(first, last, iterator_category(first));"见初始位置"
      }

      内部函数:    fill_initialize(赋初值初始化方式)

                          allocate_and_fill

                          range_initialize(拷贝元素初始化方式)

                          allocate_and_copy

void fill_initialize(size_type n, const T& value) {"批量分配并初始化,然后修改vector的位置元素"
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish;
      }
      iterator allocate_and_fill(size_type n, const T& x) {"批量分配n个value_type大小的空间,并赋值初始化"
        iterator result = data_allocator::allocate(n);
          uninitialized_fill_n(result, n, x);
          return result;
      }
  template <class InputIterator>
      void range_initialize(InputIterator first, InputIterator last,"一次分配一个空间并初始化(重复n次),每一次都修改vector的位置元素"
                            input_iterator_tag) {
        for ( ; first != last; ++first)
          push_back(*first);""
      }
      template <class ForwardIterator>
      void range_initialize(ForwardIterator first, ForwardIterator last,"批量分配n个空间并初始化,再修改vector的位置元素"
                            forward_iterator_tag) {
        size_type n = 0;
        distance(first, last, n);
        start = allocate_and_copy(n, first, last);
        finish = start + n;
        end_of_storage = finish;
      }
      template <class ForwardIterator>
      iterator allocate_and_copy(size_type n,"批量分配n个value_type大小的空间,并进行拷贝初始化"
                                 ForwardIterator first, ForwardIterator last) {
        iterator result = data_allocator::allocate(n);
        __STL_TRY {
          uninitialized_copy(first, last, result);
          return result;
        }
        __STL_UNWIND(data_allocator::deallocate(result, n));
      }

析构函数:

      ~vector() { "析构函数"
        destroy(start, finish);""
        deallocate();
      }

      内部函数:destroy(析构函数)

                       deallocate(释放空间)

template <class T>
inline void destroy(T* pointer) {
    pointer->~T();
}
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
  for ( ; first < last; ++first)
    destroy(&*first);
}
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
  typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
  __destroy_aux(first, last, trivial_destructor());
}
template <class ForwardIterator>"依次调用每一个迭代器指向元素的析构函数"
inline void destroy(ForwardIterator first, ForwardIterator last) {
  __destroy(first, last, value_type(first));
}
void deallocate() {"空间释放"
        if (start) data_allocator::deallocate(start, end_of_storage - start);
      }

重载操作符:=、==、!=、>、<、>=、<=、[]

template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {
  if (&x != this) {
    if (x.size() > capacity()) {"自身容量不足,需重新分配更大的内存"
      iterator tmp = allocate_and_copy(x.end() - x.begin(),
                                       x.begin(), x.end());
      destroy(start, finish);
      deallocate();
      start = tmp;
      end_of_storage = start + (x.end() - x.begin());
    }
    else if (size() >= x.size()) {"自身空间足够"
      iterator i = copy(x.begin(), x.end(), begin());
      destroy(i, finish);
    }
    else {"自身空间不足,但自身容量足够"
      copy(x.begin(), x.begin() + size(), start);
      uninitialized_copy(x.begin() + size(), x.end(), finish);
    }
    finish = start + x.size();
  }
  return *this;
}
template <class T, class Alloc>
inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}

        内部函数:equal

template <class T, class Alloc>
inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {
  return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}

        内部函数:lexicographical_compare

reference operator[](size_type n) { return *(begin() + n); }"下标操作"
      const_reference operator[](size_type n) const { return *(begin() + n); }

begin():

iterator begin() { return start; }"begin函数"
      const_iterator begin() const { return start; }

end():

      iterator end() { return finish; }"end函数"
      const_iterator end() const { return finish; }

rbegin():

      reverse_iterator rbegin() { return reverse_iterator(end()); }"rbegin函数"
      const_reverse_iterator rbegin() const { 
        return const_reverse_iterator(end()); 
      }

rend():

      reverse_iterator rend() { return reverse_iterator(begin()); }"rend函数"
      const_reverse_iterator rend() const { 
        return const_reverse_iterator(begin()); 
      }

front():

      reference front() { return *begin(); }"返回第一个元素的值"
      const_reference front() const { return *begin(); }

back():

      reference back() { return *(end() - 1); }"返回最后一个元素的值"
      const_reference back() const { return *(end() - 1); }

insert():

iterator insert(iterator position, const T& x) {"在指定的位置插入一个新元素,值为x"
        size_type n = position - begin();
        if (finish != end_of_storage && position == end()) {"恰好插入位置是end位置"
          construct(finish, x);
          ++finish;
        }
        else
          insert_aux(position, x);
        return begin() + n;
      }
      
      iterator insert(iterator position) { return insert(position, T()); }"在指定的位置插入一个新元素,值为默认"
      
      template <class InputIterator>
      void insert(iterator position, InputIterator first, InputIterator last) {"从指定的位置开始插入一段新元素"
        range_insert(position, first, last, iterator_category(first));
      }

      内部函数:range_insert

  void insert (iterator pos, size_type n, const T& x){"在指定的位置插入n个值为x的新元素"
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {"剩余空间足够用于插入n个元素"
      T x_copy = x;
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        fill(position, position + n, x_copy);
      }
      else {
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        fill(position, old_finish, x_copy);
      }
    }
    else {
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}
void insert (iterator pos, int n, const T& x) {
        insert(pos, (size_type) n, x);
      }
      void insert (iterator pos, long n, const T& x) {
        insert(pos, (size_type) n, x);
      }

      内部函数:range_insert

template <class InputIterator>"range_insert函数"
void range_insert(iterator pos,
                                    InputIterator first, InputIterator last,
                                    input_iterator_tag) {
  for ( ; first != last; ++first) {
    pos = insert(pos, *first);
    ++pos;
  }
}
template <class ForwardIterator>
void range_insert(iterator position,
                                    ForwardIterator first,
                                    ForwardIterator last,
                                    forward_iterator_tag) {
  if (first != last) {
    size_type n = 0;
    distance(first, last, n);
    if (size_type(end_of_storage - finish) >= n) {
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        copy(first, last, position);
      }
      else {
        ForwardIterator mid = first;
        advance(mid, elems_after);
        uninitialized_copy(mid, last, finish);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        copy(first, mid, position);
      }
    }
    else {
      const size_type old_size = size();
      const size_type len = old_size + max(old_size, n);
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_copy(first, last, new_finish);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
      destroy(start, finish);
      deallocate();
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

push_back():

  void push_back(const T& x) {"push_back函数"
        if (finish != end_of_storage) {
          construct(finish, x);"调用元素的构造函数并初始化"
          ++finish;
        }
        else
          insert_aux(end(), x);
      }

pop_back():

      void pop_back() {"pop_back函数"
        --finish;
        destroy(finish);
      }

clear():

      void clear() { erase(begin(), end()); }"clear函数"

at():

assign():

erase():

    iterator erase(iterator position) {"释放某个位置的元素"
        if (position + 1 != end())
          copy(position + 1, finish, position);
        --finish;
        destroy(finish);
        return position;
      }
      iterator erase(iterator first, iterator last) {"释放一段区间的元素"
        iterator i = copy(last, finish, first);
        destroy(i, finish);
        finish = finish - (last - first);
        return first;
      }

capacity():

  size_type capacity() const { return size_type(end_of_storage - begin()); }"capacity函数"

size():

   size_type size() const { return size_type(end() - begin()); }"size函数"

resize():

    void resize(size_type new_size, const T& x) {"resize改变了vector的capacity同时也增加了它的size"
        if (new_size < size()) 
          erase(begin() + new_size, end());//并不做赋值初始化动作
        else
          insert(end(), new_size - size(), x);
      }

max_size():

  size_type max_size() const { return size_type(-1) / sizeof(T); }"max_size函数"(疑惑)

empty():

  bool empty() const { return begin() == end(); }"empty函数"

swap():

template <class T, class Alloc>
inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {"只交换位置元素而已"
  x.swap(y);
}
      void swap(vector<T, Alloc>& x) {
        __STD::swap(start, x.start);
        __STD::swap(finish, x.finish);
        __STD::swap(end_of_storage, x.end_of_storage);
      }

reserve():

void reserve(size_type n) {"reserve增加了vector的capacity,但是它的size没有改变"
        if (capacity() < n) {
          const size_type old_size = size();
          iterator tmp = allocate_and_copy(n, start, finish);
          destroy(start, finish);
          deallocate();
          start = tmp;
          finish = tmp + old_size;
          end_of_storage = start + n;
        }
      }

    

    注:由于本人水平有限,若有不对的地方,欢迎指正!谢谢


© 著作权归作者所有

共有 人打赏支持
突然帅了
粉丝 8
博文 90
码字总数 28698
作品 0
西安
C++ STL学习——vector

学过C++的人肯定会很熟悉STL标准模板库,STL其实就是封装了一系列的接口,供我们调用。很多函数或者算法的实现不需要我们从头开始写,大大提高我们的编程效率。这篇博客在简单介绍STL的情况下...

chenyufeng1991
2016/08/21
0
0
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
0
0
STL vector 介绍连载1-2-3

STL简介: STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。这可能是...

天远
2012/05/20
0
0
C++ STL学习——algorithm

在之前的博客中我们学习了很多STL中的模板库,包括deque,queue,stack,list等,他们都是一种数据结构,也就是说STL已经为我们实现了。今天我们来讲讲STL中比较大的一个库. 主要是一些算法的...

chenyufeng1991
2016/09/24
0
0
C语言编程新手入门基础知识学习:程序注释

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
05/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

74.expect脚本同步文件以及指定host同步文件 构建分发系统文件和命令

20.31 expect脚本同步文件: 在expect脚本中去实现在一台机器上把文件同步到另外一台机器上去。核心命令用的是rsync ~1.自动同步文件 #!/usr/bin/expect set passwd "123456" spawn rsync -a...

王鑫linux
37分钟前
0
0
TypeScript项目引用(project references)

转发 TypeScript项目引用(project references) TypeScript新特性之项目引用(project references) 项目引用是TypeScript 3.0中的一项新功能,允许您将TypeScript程序构建为更小的部分。 通过这...

durban
41分钟前
0
0
爬虫入门

导读 网络爬虫(Web crawler),是一种按照一定的规则,自动地抓取万维网信息的程序或者脚本,它们被广泛用于互联网搜索引擎或其他类似网站,可以自动采集所有其能够访问到的页面内容,以获取...

问题终结者
41分钟前
0
0
ppwjs之bootstrap文字排版:无序列表项不换行

<!DOCTYPT html><html><head><meta http-equiv="content-type" content="text/html; charset=utf-8" /><title>ppwjs欢迎您</title><link rel="icon" href="/favicon.ico" ......

ppwjs
48分钟前
0
0
SpringBoot 学习一

本文将从以下几个方面介绍: 前言 HelloWorld 读取配置文件 例子(CURD) 前言 Spring Boot是由Pivotal团队提供的全新框架,其设计目的是用来简化新Spring应用的初始搭建以及开发过程。该框架...

tsmyk0715
48分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部