C++  STL _ Vector使用及模拟实现

目录
  • 1.Vector的介绍
    • 1.1 Vector的介绍
  • 2.Vector的使用
    • 2.1 vector的定义
    • 2.2 vector 迭代器的使用
    • 2.3 vector的空间增长问题
  • 3. vector的增删查改
    • 3.1 push_back (重点)
    • 3.2 pop_back (重点)
    • 3.3 insert
    • 3.4 erase
    • 3.5 operator [ ]

1.Vector的介绍

1.1 Vector的介绍

​ ​vector官方文档介绍​​

  • 1.vector是表示可变大小数组的序列容器。
  • 2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
  • 3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小 为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
  • 4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  • 5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
  • 6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好

2.Vector的使用

vector在实际中非常重要且使用,因此我们需要熟悉使用常用的接口,以下将从常用的接口入手并进行模拟实现

vector模拟实现的基本结构:

template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

//无参构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{}

//资源管理
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstoage = nullptr;
}
}
size_t size() const{
return _finish - _start;
}

size_t capacity() const{
return _endofstoage - _start;
}
private:
iterator _start;
iterator _finish;
iterator _endofstoage;
};

2.1 vector的定义


构造函数声明​​constructor​​


接口说明


vector()(重点)


无参构造


vector (const vector& x); (重点)


拷贝构造


vector(size_type n, const value_type& val = value_type())


构造并初始化n个val


vector (InputIterator first, InputIterator last);


使用迭代器进行初始化构造

//无参构造
vector()
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{}

//拷贝构造
void swap(vector<T>& v){
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstoage, v._endofstoage);
}

//vector(const vector& v)
vector(const vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
vector tmp(v.begin(), v.end());
swap(tmp);
}

//初始化n个val
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}

//使用迭代化区间初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr)
, _finish(nullptr)
, _endofstoage(nullptr)
{
while (first != last)
{
push_back(*first);
++first;
}
}

2.2 vector 迭代器的使用


iterator的使用


接口说明


begin+end (重点)


获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置

的iterator/const_iterator


rbegin+rend(反向迭代器)


获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的

reverse_iterator

iterator begin(){
return _start;
}
iterator end(){
return _finish;
}

const iterator begin() const{
return _start;
}
const iterator end() const{
return

2.3 vector的空间增长问题


容量空间


接口说明


size


获取数据个数


capacity


获取容量大小


empty


判断是否为空


resize(重点)


改变vector的size


reserve(重点)


改变vector的capacity

void resize(size_t{
if (n > capacity())
{
reserve(n);
}
if (n > size())
{
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
else
void reserve(size_t{
size_t sz = size();
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
//这里会造成浅拷贝问题
//memcpy(tmp, _start, size() * sizeof(T));
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}

delete[] _start;
}
_start = tmp;
}
_finish = _start + sz;
_endofstoage = _start + n;

}

注意:

1、我们在扩容的时候有一个小细节,capacity的容量扩容在vs和g++下分别运行是有区别的,在Vs下caoacity的扩容是按1.5倍增长的;在g++下是按2倍增长的。不能固化的认为,vector的增长都是2倍,具体增长的多少要根据需求定义。Vs是PJ盘本的STL,g++是SGI版本的STL。

//vs下
int main(){
vector<int> v;
size_t sz = v.capacity();
for (int i = 0; i < 100; ++i)
{
v.push_back(i);
if (sz != v.capacity())
{
sz = v.capacity();
cout << "capacity changed: " << sz << '\n';
}
}

return 0;
}

3. vector的增删查改


vector增删查改


接口说明


​ ​push_back​​(重点)


尾插


pop_back ​​(重点)


尾删


​ ​find​​


查找。(注意这个是算法模块实现,不是vector的成员接口)


​ ​insert​​


在pos之前插入val


​ ​erase​​


删除pos位置的数据


​ ​swap​​


交换两个vector的数据空间


​ ​operator[] ​​(重点)


像数组一样访问

3.1 push_back (重点)

void push_back(const{
if (_finish == _endofstoage)
{
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
}
*_finish = x;
++_finish;

//insert(end(), x);

 方法:

  • 1、实现要考虑是否需要扩容,如果 _finish == _endofstoage 则需要扩容
  • 2、尾插元素, ++_finish

3.2 pop_back (重点)

pop_back比较简单,尾删的逻辑不是删除而是覆盖,因此只需要--_finish即可

void pop_back(){
if (_finish > _start)
{
--_finish;
}
//erase(end() - 1);

3.3 insert

insert插入是在pos位置之前插入x

方法:

  • 1、判断pos位置的合法性。
  • 2、判断是否需要扩容,如果需要扩容则注意,这里会引发迭代器失效问题。

由于迭代器失效问题比较复杂,情况多样,我总结了一篇单独的博客供大家参考:

  • 3、 挪动数据,由后往前走,让前一个覆盖后一个。
  • 4、插入数据,++_finish, 返回pos位置
iterator insert(iterator pos, const{
//检查
assert(pos >= _start && pos <= _finish);
//空间不够 扩容
//扩容以后 pos就失效了
if (_finish == _endofstoage)
{
//使用相对距离来计算确定pos位置
size_t n = pos - _start;
size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newCapacity);
pos = _start + n;
}

//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;

return

3.4 erase

erase是删除pos位置的数据

方法:

  • 1、判断pos位置的合法性。
  • 2.、拿到pos位置下一个位置的迭代器,从前往后,后一个覆盖前一个。
  • 3、最后--_finish,返回pos位置
iterator erase(iterator pos){
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;

return

3.5 operator [ ]

重载的operator [ ] 就是取到pos位置对应的数据即可,比较简单

operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}

const T& operator[](size_t pos) const
{
assert(pos < size());
return

到此这篇关于C++  STL _ Vector使用及模拟实现的文章就介绍到这了,更多相关C++  STL _ Vector使用 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++(STL库)之顺序容器vector的使用

    一.特点 ①总的来说:可变大小数组.支持快速随机访问.在尾部之外的位置插入或删除元素可能很慢 ②元素保存在连续的内存空间中,因此通过下标取值非常快 ③在容器中间位置添加或删除元素非常耗时 ④一旦内从重分配,和原vector相关的指针,引用,迭代器都失效.内存重分配耗时很长 二.头文件.using声明 头文件:#include <vector> using声明:using std::vector; 三.初始化 vector<T>  v1; ==>v1是一个空的vector ve

  • C++ STL中vector容器的使用

    目录 一.vector (1)区分size()和capacity() (2)迭代器失效 (3)区分const_iterator和constiterator (4)区分reserve()和resize() (5)push_back和emplace (6)关于原位构造(定位new+完美转发) 总结 一.vector (1)区分size()和capacity() size():返回容纳的元素个数 capacity():返回当前分配存储的容量 (2)迭代器失效 (3)区分const_iterator和c

  • C++ STL入门教程(1) vector向量容器使用方法

    一.简介 Vectors 包含着一系列连续存储的元素,其行为和数组类似. 访问Vector中的任意元素或从末尾添加元素都可以在O(1)内完成,而查找特定值的元素所处的位置或是在Vector中插入元素则是O(N). 二.完整程序代码 /*请务必运行以下程序后对照阅读*/ #include <vector> #include <iostream> #include <algorithm> #include <stdexcept> using namespace

  • C++ STL标准库std::vector的使用详解

    目录 1.简介 2.使用示例 3.构造.析构.赋值 3.1std::vector::vector构造函数 3.2std::vector::~vector析构函数 3.3std::vector::operator=“=”符号 4.Iterators迭代器 4.1std::vector::begin 4.2std::vector::end 4.3std::vector::rbegin 4.4std::vector::rend 4.5std::vector::cbegin(C++11) 4.6std:

  • C++ 基础函数的介绍及使用(Vector+deque)

    目录 一.Vector的基础函数 1. 构造函数 2. 增加元素 3. 删除元素 4. 遍历vector 5. 判断函数 6. 大小函数 7. 其他函数 二.deque的介绍及使用 三.deque 和 vector的差别 1.构造函数 2.常用成员函数 3.特点 一.Vector的基础函数 之前有学习过 vector.set.map等容器,都是需要什么搜什么,没有详细的了解其中的内容.最近在看 STL 的相关内容,就顺手整理一些基础性内容,避免以后遇到的时候再临时抱佛脚. 1. 构造函数 vec

  • C++STL教程之vector模板的使用

    目录 vector模板类 1. vector模板类 1.1 创建模板类 1.2 STL容器都提供的成员方法 1.3 vector特有的成员方法 1.4 STL容器的非成员方法 vector模板类 STL(标准模板库)提供了容器.迭代器.函数对象.算法的模板.容器是类似于数组的东西,它可以存储若干值,STL容器是同质的,即存储的值的类型相同;迭代器是用来遍历容器的,它和能遍历数组的指针类似,是广义指针;函数对象是类似于函数的对象,可以是类对象和函数指针;算法就是一些能完成特定任务的处方. 我们来看

  • C++  STL _ Vector使用及模拟实现

    目录 1.Vector的介绍 1.1 Vector的介绍 2.Vector的使用 2.1 vector的定义 2.2 vector 迭代器的使用 2.3 vector的空间增长问题 3. vector的增删查改 3.1 push_back (重点) 3.2 pop_back (重点) 3.3 insert 3.4 erase 3.5 operator [ ] 1.Vector的介绍 1.1 Vector的介绍 ​ ​vector官方文档介绍​​ 1.vector是表示可变大小数组的序列容器. 2

  • C++模拟实现STL容器vector的示例代码

    目录 一.vector迭代器失效问题 二.模拟实现构造函数调用不明确 1.问题描述 2.解决调用不明确的方法 三.reserve中的深浅拷贝问题 1.reserve中浅拷贝发生原因 2.浅拷贝发生的图解 3.解决方法 四.模拟实现vector整体代码 一.vector迭代器失效问题 1.Visual Studio和g++对迭代器失效问题的表现 int main(){ std::vector<int>v{1,2,3,4}; std::vector<int>::iterator it

  • C++ vector类的模拟实现方法

    vector和string虽然底层都是通过顺序表来实现的,但是他们利用顺序表的方式不同,string是指定好了类型,通过使用顺序表来存储并对数据进行操作,而vector是利用了C++中的泛型模板,可以存储任何类型的数据,并且在vector中,并没有什么有效字符和容量大小的说法,底层都是通过迭代器进行操作的,迭代器底层实现也就是指针,所以说,vector是利用指针对任何顺序表进行操作的. vector属性 _start用于指向第一个有效元素 _finish用于指向最后一个有效元素的下一个位置 _e

  • C++STL之vector模板类详解

    目录 前言 vector模板类 创建vector对象,遍历元素 迭代器 容器的基本方法 STL函数,sort 总结 前言 STL标准模板库是C++中非常有用的功能库.本篇从vector容器开始学习STL. vector模板类 创建vector对象,遍历元素 vector模板类在头文件vector中,用于存储数组,并采用动态内存分配. 创建一个vector对象并初始化长度,通过[]运算符访问元素: #include <vector> using namespace std; int main()

  • STL中vector的使用你了解吗

    目录 前言 1.vector是什么 2.vector创建对象 3.遍历vector (1)下标遍历 (2)迭代器遍历 (3)范围for遍历 3.vector容量函数 4.vector的扩容函数 5.vector的插入删除 (1)尾插与尾删 (2)insert与erase (3)clear vector的特殊应用 6.总结 前言 当我们使用C语言的语法来实现数组的时候,增删查改都需要自己来定义函数,STL中给出了数组模板vector,其中包含函数可以帮助我们更便捷地处理数组. 1.vector是什

  • 关于STL中vector容器的一些总结

    1.vector的简单介绍 vector作为STL提供的标准容器之一,是经常要使用的,有很重要的地位,并且使用起来也是灰常方便.vector又被称为向量,vector可以形象的描述为长度可以动态改变的数组,功能和数组较为相似.实际上更专业的描述为:vector是一个多功能的,能够操作多种数据结构和算法的模板类和函数库,vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说,vector是一个能够存放任意类型的动态数组,能够增加和压缩数据.(注:STL的容器从实现的

  • 关于C++STL string类的介绍及模拟实现

    目录 一.标准库中的string类 1.string类 2.string类中的常用接口说明+模拟实现 2.1 string类对象的常见构造+模拟实现 2.2 string类对象的容量操作+模拟实现 2.3 string类对象的访问及遍历操作+模拟实现 2.4 string类对象的修改操作+模拟实现 2.5 string类非成员函数+模拟实现 一.标准库中的string类 1.string类 字符串的表示字符序列的类 标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专

  • C++ vector的用法小结

    c++ vector用法 C++内置的数组支持容器的机制,但是它不支持容器抽象的语义.要解决此问题我们自己实现这样的类.在标准C++中,用容器向量(vector)实现.容器向量也是一个类模板. 标准库vector类型使用需要的头文件:#include <vector>.vector 是一个类模板.不是一种数据类型,vector<int>是一种数据类型.Vector的存储空间是连续的,list不是连续存储的. 一. 定义和初始化 vector< typeName > v1

随机推荐