【C++进阶】深入STL之vector:构建高效C++程序的基石

简介: 【C++进阶】深入STL之vector:构建高效C++程序的基石

学习STL中的vector:开启C++容器之旅的前言

  • 在C++的编程世界中,标准模板库(STL)无疑是每位开发者都需要熟练掌握的工具集。其中,vector作为STL中最常用的动态数组容器之一,以其灵活、高效和易用的特性,成为了众多C++程序员的首选。

vector容器允许我们存储任意数量的同类型元素,并且能够根据需要进行动态扩展。这种灵活性使得vector在处理大量数据时变得尤为高效,无论是在科学计算、图形处理、网络编程还是游戏开发等领域,我们都能看到vector的身影。
现在让我们一起踏上学习STL中vector的旅程吧!


📒1.vector类的基本概念

vector是C++标准模板库(STL)中的一个动态数组容器,它提供了对一段连续空间的动态管理功能。与普通的C++数组相比,vector具有许多优点,如可以动态调整大小、支持随机访问等


vector类成员函数:

class string
{
private:
  iterator _start;
  iterator _finish;
  iterator _end_of_storage;
};


📕2. vector类的常用操作

🌈vector类对象的常见构造

构造函数声明 接口说明
vector() 无参构造
vector(size_type n, const value_type& val = value_type()) 构造并初始化n个val
vector (const vector& x); 拷贝构造
vector (InputIterator first, InputIterator last); 使用迭代器进行初始化构造
int main()
{
  vector<int> v1; // 无参构造
  vector<int> v2(10, 0); // 构造并初始化n个val
  vector<int> v3(v2); // 拷贝构造
  vector<int> v4(v2.begin(),v2.end()); // 使用迭代器进行初始化构造
  return 0;
}

关于 vector iterator 的使用

iterator的使用 接口说明
begin +end 获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend 获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

其实vector的很多用法和string类似


🌞vector类对象的容量操作

容量空间 接口说明
size 获取数据个数
capacity 获取容量大小
empty 判断是否为空
resize 改变vector的size
reserve 改变vector的capacity
int main()
{
  vector<int> v(10, 0);
  cout << v.size() << endl; // 获取数据个数
  cout << v.capacity() << endl; // 获取容量大小

  v.reserve(20); // 改变vector的capacity
  cout << endl;
  cout << "after reserve size: " << v.size() << endl;
  cout << "after reserve capacity: " << v.capacity() << endl;
  
  cout << endl;
  
  v.resize(20); // 改变vector的size
  cout << "after resize size: " << v.size() << endl;
  cout << "after resize capacity: " << v.capacity() << endl;

  cout << v.empty() << endl; // 判断是否为空
  return 0;
}

注意:

  • capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL
  • reserve只负责开辟空间,不会影响size的大小,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
  • resize在开空间的同时还会进行初始化,会影响size的大小

🌙vector类对象的增删查改

vector增删查改 接口说明
push_back 尾插
pop_back 尾删
insert 在pos之前插入val
erase 删除pos位置的数据
swap 交换两个vector的数据空间
operator[ ] 像数组一样访问

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

代码示例:

int main()
{
  vector<int> v1(1, 0);
  v1.push_back(1); // 尾插
  v1.push_back(2);
  v1.push_back(3);
  v1.push_back(5); // 尾插后v1 : 0,1,2,3,5

  v1.pop_back(); // 尾删后v1 : 0,1,2,3

  cout << "v1: ";
  for (size_t i = 0; i < v1.size(); i++) // 遍历vector数组
  {
    cout << v1[i] << " "; // operator[]随机访问
  }
  cout << endl;

  vector<int> v2(10, 0);
  cout << "v2: ";
  for (size_t i = 0; i < v2.size(); i++)
  {
    cout << v2[i] << " ";
  }
  cout << endl;
  
  v1.swap(v2); // 交换v1,v2内容
  cout << "after swap v1: ";
  for (size_t i = 0; i < v1.size(); i++)
  {
    cout << v1[i] << " ";
  }
  cout << endl;

  vector<int>::iterator it = find(v1.begin(), v1.end(), 0); // 查找
  cout << *it;
  return 0;
}


注意:insert和erase在vector里面有点特殊,在vector上它使用的都是迭代器

erase往往和find搭配使用

vector<int> v{1,2,3,4,5,6,7,8,9};
auto pos = find(v.begin(),v.end(),6);
v.erase(pos);

//删除一个区间
v.erase(v.begin() + 1,v.end() - 1);

insert头插一个0

vector<int> v{1,2,3,4,5,6,7,8,9};
auto pos = v.begin();
v.insert(pos,0);

📜3. vector类的模拟实现

🍁vector的成员变量

首先我们要先搞清楚 vector的成员变量,我们清楚 vector类在底层实际上也是指针,在模拟实现 vector之前,我们创建一个属于自己的命名空间来与库里面的区分

namespace pxt
{
  template<class T>
  class vector
  {
  public:
    // vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;
    // 迭代器相关(迭代器主要就是找到头尾)
    iterator begin()
    {
      return _start;
    }
    iterator end()
    {
      return _finish;
    }
    const_iterator begin() const
    {
      return _start;
    }
    const_iterator end() const
    {
      return _finish;
    }
  private:
    // 成员变量
    iterator _start; // 指向有效数据的头
    iterator _finish; // 指向有效数据的尾
    iterator _end_of_storage; // 指向最大空间的地方
  };
}


🌸vector的构造函数

无参构造:

vector()
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{}

带参的构造函数

vector(size_t n, const T& val = T())
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  reserve(n); // 开辟空间
  for (size_t i = 0; i < n; i++)
  {
    push_back(val); // 给初始值赋值
    // reserve,push_back的模拟实现下面会讲
  }
}

迭代器区间构造

为了实现不同类型迭代器的构造,这里需要再创建一个模板

template <class InputIterator> // 类似与STL
vector(InputIterator first, InputIterator last)
  :_start(nullptr)
  , _finish(nullptr)
  , _end_of_storage(nullptr)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

🌷vector的析构函数

析构函数比较简单,将空间释放,各个指针置为空

~vector()
{
  delete[] _start;
  _start = _finish = _end_of_storage = nullptr;
}

🌻vector的拷贝构造函数

vector(const vector<T>& v)
  :_start(nullptr)
  , _finish(nullptr)
  , _endof_storage(nullptr)
  {
    reserve(v.capacity());
    for (const auto& e : v)
    {
      push_back(e);
    }
  }

🌼vector的运算符重载

void swap(vector<T> v)
{
  std::swap(_start, v._start);
  std::swap(_finish, v._finish);
  std::swap(_end_of_storage, v._end_of_storage);
}
// 现代写法
vector<T>& operator=(vector<T> tmp)
  {
    swap(tmp); 
    return *this;
  }

🍂vector容量相关函数

跟容量有关的函数size,capacity,empty,resize,reverse,push_back

size_t size() const
{
  return _finish - _start;
}

size_t capacity() const
{
  return _endof_storage - _start;
}

bool empty() const
{
  return _start == _finish;
}

reverse

reverse只会改变capacity的大小,并不会改变size的大小

void reserve(size_t n)
{
  if (n > capacity()) // n < capacity()时,则不需要作出反应
  {
    size_t sz = size(); // 先保存以下size的值
    T* tmp = new T[n]; // 开辟空间
    if (_start)
    {
      //memcpy(tmp, _start, sizeof(T)*sz);
      for (size_t i = 0; i < sz; ++i)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
    }

    _start = tmp;
    _finish = _start + sz;
    _end_of_storage = _start + n;
  }
}

resize

resize不仅会改变size大小,也会改变capacity大小

void resize(size_t n, const T& val = T()) // val=T()用了匿名对象
{
  if (n > capacity())
  {
    reserve(n); // 开辟额外空间
  } 

  if (n > size())
  {
    // 初始化填值
    while (_finish < _start + n)
    {
      *_finish = val;
      ++_finish;
    }
  }
  else
  {
    _finish = _start + n;
  }
}

注意:C++将内置类型特殊处理过,int/char等等都被升级为了类,所以可以使用int()表示匿名对象

int main()
{
  cout << int() << endl; // int的缺省值为0,所以输出 0
  return 0;
}

push_back

void push_back(const T& x)
{
  if(_finish == _end_of_storage)
  {
    size_t sz = size();
    size_t cp = capacity() == 0 ? 4 : capacity() * 2;
    T* tmp = new <T>(cp);
    if(_start)
    {
      // memcpy(tmp, _start, sizeof(T) * sz);
      for (size_t i = 0; i < sz; ++i)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
    }
    _start = tmp;
    _finish = _start + sz;
    _end_of_storage = _start + cp;
  }
  *_finish = x;
  _finish++;
}

当探索并深入了解了STL中的vector容器后,我们不禁感叹其强大的功能和灵活性。随着对vector的学习和使用,我们逐渐理解到,一个高效的C++程序不仅仅是代码的堆砌,更是对数据结构、算法和STL等标准库深刻理解的体现。vector的迭代器、容量管理、元素访问以及算法支持等功能,都是我们在日常编程中不可或缺的工具


📖4. 总结

学习vector仅仅是开始。STL(Standard Template Library)还提供了诸如list、set、map等其他强大的容器,每个都有其独特的特点和适用场景。因此,鼓励大家继续深入学习STL,探索其背后的设计理念和实现原理。通过不断实践,我们不仅能够提高编程效率,还能够培养出更加优雅、健壮的代码风格。最后,我想说的是学习是一个永无止境的过程。无论是STL还是其他任何技术,都值得我们不断学习和探索。让我们保持对知识的渴望和好奇心,不断前行,在编程的道路上越走越远

目录
相关文章
|
11天前
|
C++ 容器
C++中向量的操作vector
C++中向量的操作vector
|
9天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
18天前
|
存储 C语言 C++
【C++】vector的使用上
**C++ STL的vector简介与用法:** Vector是动态顺序数组,提供高效下标访问,支持动态增长。与数组类似但可自动调整大小。常用构造函数包括默认、填充、迭代器范围和拷贝构造。析构函数自动释放内存。赋值运算符执行深拷贝。迭代器接口包括`begin()`和`end()`(反向对应`rbegin()`和`rend()`),C++11增加了const版本以支持只读访问。示例代码展示了不同构造函数和迭代器的使用。
|
16天前
|
算法 测试技术 C++
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
14 2
|
10天前
|
存储 Java C++
【c++】vector模拟
【c++】vector模拟
9 0
|
16天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
25 0
|
18天前
|
编译器 C++
【C++】vector的使用下
**C++ 中的 `std::vector` 概要:** - **元素获取:** 支持 `operator[]`(越界时不检
|
18天前
|
存储 算法 数据处理
【C++】STL简介
**STL是C++标准库的关键部分,源于Alexander Stepanov的泛型编程研究。它提供了数据结构(如vector、list)和算法,是高效、通用的软件框架。STL始于惠普,后由SGI发展,现已成为C++1998标准的一部分并不断进化。它包括容器、迭代器、算法、仿函数、配接器和分配器六大组件,带来高效性、通用性和可扩展性,但也存在性能开销和学习难度。学习STL涉及理解底层数据结构、用法、实现和实践。推荐[cplusplus.com](https://cplusplus.com)作为学习资源。**
|
18天前
|
存储 算法 程序员
C++基础知识(八:STL标准库(Vectors和list))
C++ STL (Standard Template Library标准模板库) 是通用类模板和算法的集合,它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等. STL容器的提供是为了让开发者可以更高效率的去开发,同时我们应该也需要知道他们的底层实现,这样在出现错误的时候我们才知道一些原因,才可以更好的去解决问题。
|
18天前
|
算法 前端开发 C++
C++基础知识(八:STL标准库 deque )
deque在C++的STL(Standard Template Library)中是一个非常强大的容器,它的全称是“Double-Ended Queue”,即双端队列。deque结合了数组和链表的优点,提供了在两端进行高效插入和删除操作的能力,同时保持了随机访问的特性。