文档章节

STL 源码注释(2)——Vector

突然帅了
 突然帅了
发布于 2015/04/19 15:02
字数 1645
阅读 16
收藏 0
点赞 0
评论 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
博文 86
码字总数 28698
作品 0
西安
C语言编程新手入门基础知识学习:程序注释

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

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

C语言/C++程序员编程学习:版权和版本

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

小辰带你看世界 ⋅ 05/16 ⋅ 0

C++ STL学习——vector

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

chenyufeng1991 ⋅ 2016/08/21 ⋅ 0

C++ STL学习——algorithm

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

chenyufeng1991 ⋅ 2016/09/24 ⋅ 0

C语言编程学习:出错信息的处理

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

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

腾讯阿里网易游戏华为科大讯飞面经

本人是一非科班妹子,在找实习的过程中面试了腾讯、阿里、网易游戏、华为、科大讯飞(面试的顺序),前面三个都挂了。。。 1.腾讯提前批——游戏客户端开发 自我介绍+项目经历(问的很细) ...

牛客网 ⋅ 06/13 ⋅ 0

BOOST.ASIO源码剖析(一)

前言 源码之前,了无秘密。 ——侯捷 Boost库是一个可移植、提供源代码的C++库,作为标准库的后备,是C++标准化进程的开发引擎之一。Boost库由C++标准委员会库工作组成员发起,其中有些内容有...

moki_oschina ⋅ 04/11 ⋅ 0

小朋友学经典算法(12):分割字符串

一、准备知识 在分割字符串之前,先来了解一些跟字符串相关的变量或函数: (1)sizetype:sizetype由string类类型和vector类类型定义的类型,用以保存任意string对象或vector对象的长度,标...

海天一树X ⋅ 06/14 ⋅ 0

C语言/C++编程学习强势之处的体现

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

小辰带你看世界 ⋅ 05/12 ⋅ 0

C语言编程学习:把相同或近乎相同的代码形成函数和宏

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

小辰带你看世界 ⋅ 05/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim编辑模式、命令模式

编辑模式 vim要从一般模式进入编辑模式只要按字母 i 、I、a、A、o、O键就可以了 要从编辑模式回到一般模式按键盘上的Esc键即可。 按键 作用 i 在当前字符前插入 I 在光标所在行的行首插入 o ...

黄昏残影 ⋅ 24分钟前 ⋅ 0

OSChina 周五乱弹 —— 如果有一天不当程序员了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @guanglun :分享off的单曲《我唱情歌给你听》 《我唱情歌给你听》- off 手机党少年们想听歌,请使劲儿戳(这里) @小小编辑 :#如果不做程序...

小小编辑 ⋅ 31分钟前 ⋅ 4

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

Java8新增的DateTimeFormatter与SimpleDateFormat的区别

两者最大的区别是,Java8的DateTimeFormatter也是线程安全的,而SimpleDateFormat并不是线程安全。 在并发环境下使用SimpleDateFormat 为了能够在多线程环境下使用SimpleDateFormat,有这三种...

人觉非常君 ⋅ 今天 ⋅ 0

多线程如何控制执行顺序

线程的生命周期说明: 当线程被创建并启动以后,它既不是一启动就进入了执行状态,也不是一直处于执行状态,在线程的生命周期中,它要经过新建(New)、就绪(Runnable)、运行(Running)、...

MarinJ_Shao ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Django第一期

安装Django 去https://www.djangoproject.com/download/ 下载最新版的Django,然后解压放到Anaconda\Lib\site-packages目录下,然后cmd进入此目录,输入安装命令: python setup.py install ...

大不了敲一辈子代码 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部