当前位置： 首页 > news >正文

C++ - 浅看vector源码

news 2025/6/29 14:05:30

目录

前言

一、了解

二、抓核心

三、其他函数

总结
​​​​​

前言

路漫漫其修远兮，吾将上下而求索；

一、了解

我们所看的是 sgi stl3.0版本中的vector源码；

其中只有 .h 文件没有 .cpp 文件，因为模板不支持声明与定义(分离到两个文件)放到 .h 和 .cpp中，否则会出现链接错误； 

在vector 之中，用来包含头文件：

Q：这些头文件之中主要包含什么？

  • vector 之中，进行拷贝、交换会用到一些基础的算法 --> stl_algobase.h; 使用空间配置器是从内存池中申请来的 --> stl_alloc.h ; 从内存池中申请，而有些空间只开了而未初始化就需要去使用定位new  --> stl_constuct.h……

Q：什么时候会用 replace new（定位 new）呢？

  • 有些地方使用内存池，而内存池只会管开辟了多大的空间，而不会去初始化这块空间；想要初始化空间就是去使用定位new ，而在 stl_construct.h 之中有 replace new 的封装，如下：

而 vector 核心地实现是在 stl_vector.h 和 stl_bvector.h 之中；

其中最重要的就是 stl_vector.h:

stl_vector.h 中的源码如下：

/*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*** Copyright (c) 1996* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Silicon Graphics makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*//* NOTE: This is an internal header file, included by other STL headers.*   You should not attempt to use it directly.*/#ifndef __SGI_STL_INTERNAL_VECTOR_H
#define __SGI_STL_INTERNAL_VECTOR_H__STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endiftemplate <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type>  const_reverse_iterator;typedef reverse_iterator<iterator, value_type, reference, difference_type>reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:typedef simple_alloc<value_type, Alloc> data_allocator;iterator start;iterator finish;iterator end_of_storage;void insert_aux(iterator position, const T& x);void deallocate() {if (start) data_allocator::deallocate(start, end_of_storage - start);}void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;}
public:iterator begin() { return start; }const_iterator begin() const { return start; }iterator end() { return finish; }const_iterator end() const { return finish; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }size_type size() const { return size_type(end() - begin()); }size_type max_size() const { return size_type(-1) / sizeof(T); }size_type capacity() const { return size_type(end_of_storage - begin()); }bool empty() const { return begin() == end(); }reference operator[](size_type n) { return *(begin() + n); }const_reference operator[](size_type n) const { return *(begin() + n); }vector() : start(0), finish(0), end_of_storage(0) {}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) {start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());finish = start + (x.end() - x.begin());end_of_storage = finish;}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>vector(InputIterator first, InputIterator last) :start(0), finish(0), end_of_storage(0){range_initialize(first, last, iterator_category(first));}
#else /* __STL_MEMBER_TEMPLATES */vector(const_iterator first, const_iterator last) {size_type n = 0;distance(first, last, n);start = allocate_and_copy(n, first, last);finish = start + n;end_of_storage = finish;}
#endif /* __STL_MEMBER_TEMPLATES */~vector() { destroy(start, finish);deallocate();}vector<T, Alloc>& operator=(const vector<T, Alloc>& x);void reserve(size_type n) {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;}}reference front() { return *begin(); }const_reference front() const { return *begin(); }reference back() { return *(end() - 1); }const_reference back() const { return *(end() - 1); }void push_back(const T& x) {if (finish != end_of_storage) {construct(finish, x);++finish;}elseinsert_aux(end(), x);}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);}iterator insert(iterator position, const T& x) {size_type n = position - begin();if (finish != end_of_storage && position == end()) {construct(finish, x);++finish;}elseinsert_aux(position, x);return begin() + n;}iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last) {range_insert(position, first, last, iterator_category(first));}
#else /* __STL_MEMBER_TEMPLATES */void insert(iterator position,const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */void insert (iterator pos, size_type n, const T& x);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);}void pop_back() {--finish;destroy(finish);}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;}void resize(size_type new_size, const T& x) {if (new_size < size()) erase(begin() + new_size, end());elseinsert(end(), new_size - size(), x);}void resize(size_type new_size) { resize(new_size, T()); }void clear() { erase(begin(), end()); }protected:iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_fill_n(result, n, x);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}#ifdef __STL_MEMBER_TEMPLATEStemplate <class ForwardIterator>iterator allocate_and_copy(size_type n,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));}
#else /* __STL_MEMBER_TEMPLATES */iterator allocate_and_copy(size_type n,const_iterator first, const_iterator last) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_copy(first, last, result);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}
#endif /* __STL_MEMBER_TEMPLATES */#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void range_initialize(InputIterator first, InputIterator last,input_iterator_tag) {for ( ; first != last; ++first)push_back(*first);}// This function is only called by the constructor.  We have to worry//  about resource leaks, but not about maintaining invariants.template <class ForwardIterator>void range_initialize(ForwardIterator first, ForwardIterator last,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 InputIterator>void range_insert(iterator pos,InputIterator first, InputIterator last,input_iterator_tag);template <class ForwardIterator>void range_insert(iterator pos,ForwardIterator first, ForwardIterator last,forward_iterator_tag);#endif /* __STL_MEMBER_TEMPLATES */
};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());
}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());
}#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <class T, class Alloc>
inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */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>
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;}
}template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {if (n != 0) {if (size_type(end_of_storage - finish) >= 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);}
#         ifdef  __STL_USE_EXCEPTIONS catch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#ifdef __STL_MEMBER_TEMPLATEStemplate <class T, class Alloc> template <class InputIterator>
void vector<T, Alloc>::range_insert(iterator pos,InputIterator first, InputIterator last,input_iterator_tag) {for ( ; first != last; ++first) {pos = insert(pos, *first);++pos;}
}template <class T, class Alloc> template <class ForwardIterator>
void vector<T, Alloc>::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);}
#         ifdef __STL_USE_EXCEPTIONScatch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#else /* __STL_MEMBER_TEMPLATES */template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, const_iterator first, const_iterator last) {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 {uninitialized_copy(first + elems_after, last, finish);finish += n - elems_after;uninitialized_copy(position, old_finish, finish);finish += elems_after;copy(first, first + elems_after, 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);}
#         ifdef __STL_USE_EXCEPTIONScatch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#endif /* __STL_MEMBER_TEMPLATES */#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif__STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_VECTOR_H */// Local Variables:
// mode:C++
// End:

看源码的关键就是：不关注其细节，只关注核心；

需要注意的是，未来到公司之中，第一件事不是写代码而是读代码；读代码大致分为三步：

  • 1、大体地理清代码的功能、需求；
  • 2、梳理框架(这个类的功能是什么，写好注释，只看核心部分)
  • 3、画图以弄清类与类之间的关系；

Q：而一个类的核心框架是什么？

  • 成员变量以及核心的成员函数；

二、抓核心

小技巧：在VS之中，可以右击类型、函数然后转到定义，这样做可以进行跳转到对应类型、函数等定义的地方，如下：

eg. 将 iterator 转到定义：

Q：而 value_type 又是什么呢？可以继续转到定义：

走到这个地方，我们可以得到一个结论： vector 迭代器的底层其实是一个指针；

下一步就是搞清楚vector 中三个成员变量的关系：

  iterator start;iterator finish;iterator end_of_storage;

可以先从命名进行揣摩：

先从构造函数看起；因为构造函数会进行初始化，可以大致知道这三个成员变量初始化的关系、结构是什么；

此处还有一个小技巧，可以利用 ctrl+f 进行搜索：

构造函数有很多，选其中一个大致地看一下就可以了：

但是我们仍然不知道这三个指针之间的关系；如果想要了解vector 的结构需求的情况下，看哪一个函数的实现而大概可以理解呢？看一下其 size、capacity 以及迭代器是如何计算的：

其中的 begin() 、 end() 又是什么？

原来 start 和 finish 是维护vector 有效数组区间的指针；

接下来汇总一下：

根据汇总的逻辑，我们可以梳理得到这三个成员变量之间的关系：

三、其他函数

接下来我们看一下vector 实现的尾插：push_back

  void push_back(const T& x) {if (finish != end_of_storage) {construct(finish, x);++finish;}elseinsert_aux(end(), x);}

当空间足够的时候，就会去调用construct 先初始化然后再插入数据；

需要注意的是，没有初始化就不可以进行赋值操作，这是因为如果 vector 当中是一个一个的string ， 而未初始化，那么string 当中的指针均为随机值，那么此时去赋值就是非法的；

而调用 construct 就可以将要赋值的值拷贝到指针finish 指向的空间；construct 所调用的是拷贝构造，而拷贝构造也是构造的一种，也可能调用构造；

而当空间不够的时候，理论上来说应该扩容+插入数据，源码中直接调用了函数 insert_aux，接下来我们可以去看一下函数 insert_aux：

insert_aux 的大体实现逻辑如下：

总结

读代码大致分为三步：

  • 1、大体地理清代码的功能、需求；
  • 2、梳理框架(这个类的功能是什么，写好注释，只看核心部分)
  • 3、画图以弄清类与类之间的关系；
http://www.lqws.cn/news/560755.html

相关文章：

  • SpringBoot -- 以 jar 包运行(以及常见错误分析)
  • HarmonyOS NEXT仓颉开发语言实战案例：动态广场
  • Java面试题030：一文深入了解MySQL（2）
  • SpringMVC系列（六）（Restful架构风格（中））
  • Python助力自动驾驶：深度学习模型优化全攻略
  • 什么是 PoS（权益证明）
  • 如何用VS Code、Sublime Text开发51单片机
  • uni-app subPackages 分包加载：优化应用性能的利器
  • Geollama 辅助笔记：raw_to_prompt_strings_geo.py
  • IDEA2024.3 tomcat需要按两次停止按钮停止问题
  • 区块链使用那些技术？
  • 太速科技-670-3U VPX PCIe桥扩展3路M.2高速存储模块
  • Linux测试是否能联网
  • 大事件项目记录8-文章分类接口开发-文章分类列表
  • 2025年健康医疗大数据开放共享：现状、挑战与未来发展
  • 计算机操作系统（十七）内存管理
  • Grab×亚矩阵云手机：以“云端超级节点”重塑东南亚出行与数字生活生态
  • 用鸿蒙打造真正的跨设备数据库：从零实现分布式存储
  • 【AI智能体】Dify 核心组件从使用到实战操作详解
  • 信号处理学习——文献精读与code复现之TFN——嵌入时频变换的可解释神经网络（上）
  • 数据湖 vs 数据仓库：数据界的“自来水厂”与“瓶装水厂”？
  • 阿里 Qwen3 模型更新，吉卜力风格get
  • 对话式数据分析与Text2SQL Agent产品可行性分析思考
  • 安卓中静态和动态添加子 View 到容器
  • Zotero 7 插件：翻译与护眼主题
  • 如何快速学习一门新编程语言
  • 使用asyncio构建高性能网络爬虫
  • Vue 项目中 Excel 导入导出功能笔记
  • 开疆智能CCLinkIE转ModbusTCP网关连接傲博机器人配置案例
  • 道路交通标志检测数据集-智能地图与导航 交通监控与执法 智慧城市交通管理-2,000 张图像