C++ STL之vector的使用及模拟实现

文章目录

  • 1. 介绍
  • 2. vector类的使用
    • 2.1 vector类对象的构造函数
    • 2.2 vector类对象的容量操作
    • 2.3 vector类对象的访问及遍历操作
    • 2.4 vector类对象的修改操作
  • 3. vector类的模拟实现

1. 介绍

  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类的使用

2.1 vector类对象的构造函数

(constructor)构造函数代码 功能说明
explicit vector (const allocator_type& alloc = allocator_type()); （默认构造函数）构造一个空的容器，没有任何元素。
explicit vector (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()); （填充构造函数）构造一个包含 n 个元素的容器，每个元素都是 val 的副本。
vector (const vector& x); （拷贝构造函数）构造一个容器，其中的每个元素都是 x 中对应元素的副本，顺序相同。
template <class InputIterator>
vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());		 （范围构造函数）根据范围[first, last)中的元素构造一个容器，容器中的元素个数与该范围中的元素个数相同，并且顺序相同。

2.2 vector类对象的容量操作

函数名称 代码 功能说明
size size_type size() const; 返回向量中元素的个数，即向量的大小。
max_size size_type max_size() const; 返回向量可以容纳的最大元素数量。
resize void resize (size_type n, value_type val = value_type()); 改变容器的大小，使其包含 n 个元素。如果 n 小于当前容器的大小，内容将被缩减为其前 n 个元素，并移除超出范围的元素。如果 n 大于当前容器的大小，内容将扩展，通过在末尾插入足够数量的元素，使容器的大小达到 n。如果提供了 val 参数，则新元素将被初始化为 val 的副本，否则它们将进行值初始化。如果 n 也大于当前容器的容量，将进行自动重新分配已分配的存储空间。
capacity size_type capacity() const; 返回当前为向量分配的存储空间的大小，以元素为单位。这个容量不一定等于向量的大小。它可以相等或更大，额外的空间允许在不需要在每次插入时重新分配的情况下进行增长。这个容量并不限制向量的大小。当容量耗尽并需要更多空间时，容器会自动扩展（重新分配存储空间）。
empty bool empty() const; 返回向量是否为空（即其大小是否为 0）。
reserve void reserve (size_type n); 请求向量的容量至少为 n 个元素。如果 n 大于当前向量的容量，该函数会导致容器重新分配存储空间，将容量增加到 n（或更大）。在所有其他情况下，函数调用不会导致重新分配，并且向量的容量不受影响。

2.3 vector类对象的访问及遍历操作

函数名称 代码 功能说明
operator[] reference operator[] (size_type n);
const_reference operator[] (size_type n) const;		 返回向量容器中位置 n 处的元素的引用。
at reference at (size_type n);
const_reference at (size_type n) const;		 返回向量中位置 n 处的元素的引用。该函数会自动检查 n 是否在向量的有效元素范围内，如果不在范围内（即 n 大于或等于向量的大小），则抛出 out_of_range 异常。这与成员运算符 operator[] 不同，后者不进行边界检查。
front reference front();
const_reference front() const;		 返回向量中第一个元素的引用。
back reference back();
const_reference back() const;		 返回向量中最后一个元素的引用。

遍历操作

#include <iostream>
#include <vector>

int main()
{
	std::vector<int> v(10,100);
	// 1.普通下标遍历
	for (size_t i = 0; i < v.size(); ++i)
		std::cout << v[i] << " ";
	std::cout << '
';

	// 2.迭代器遍历
	for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
		std::cout << *it << " ";
	std::cout << '
';

	// 3.范围for遍历
	for (auto e : v)
		std::cout << e << " ";
	std::cout << '
';

	return 0;
}

输出结果

在这里插入图片描述

说明

  1. 普通下标遍历：
    在此代码段中，通过使用普通的下标操作符 []，从索引 0 开始，逐个访问向量 v 中的元素，并将其打印出来。循环变量 i 从 0 递增到 v.size()-1，并使用 v[i] 访问每个元素。最后，打印一个换行符。
  2. 迭代器遍历：
    在此代码段中，使用迭代器进行遍历。首先，通过 v.begin() 获取向量 v 的起始迭代器，通过 v.end() 获取向量 v 的结束迭代器。然后，通过迭代器 it 遍历从起始迭代器到结束迭代器之间的所有元素，并使用 *it 打印每个元素的值。最后，打印一个换行符。
  3. 范围for循环遍历：
    在此代码段中，使用范围for循环对向量 v 进行遍历。对于向量 v 中的每个元素，将其依次赋值给循环变量 e，然后打印出 e 的值。此方法不需要显式地使用迭代器或下标来访问向量的元素，因为范围for循环会自动处理迭代过程，并在每次迭代中将元素赋值给循环变量。最后，打印一个换行符。

2.4 vector类对象的修改操作

函数名称 代码 功能说明
assign template <class InputIterator>
void assign (InputIterator first, InputIterator last);
void assign (size_type n, const value_type& val);		 将新的内容赋值给向量，用新内容替换向量当前的内容，并相应地调整向量的大小。
push_back void push_back (const value_type& val); 在向量的末尾添加一个新元素 val。
pop_back void pop_back(); 删除最后一个元素。
insert iterator insert (iterator position, const value_type& val);
void insert (iterator position, size_type n, const value_type& val);		 在指定位置 position 之前插入新元素 val（n 个 val）。
erase iterator erase (iterator position);
iterator erase (iterator first, iterator last);		 从向量中删除单个元素（位置）或一段元素范围（[first, last)）。
clear void clear(); 清空向量中的所有元素，使向量变为空。

3. vector类的模拟实现

// vector.h文件
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace my_vector
{
    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;
        }

        //construct and destroy
        vector()
        {}

        vector(int n, const T& value = T())
        {
            resize(n, value);
        }

        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }

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

        vector<T>& operator=(vector<T> v)
        {
            swap(v);
            return *this;
        }

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

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

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

        void reserve(size_t n)
        {
            if (n > capacity())
            {
                iterator tmp = new T[n];
                size_t sz = size();
                if (_start)
                {
                    for (size_t i = 0; i < sz; i++)
                    {
                        tmp[i] = _start[i];
                    }
                }
                delete[] _start;
                _start = tmp;
                _finish = tmp + sz;
                _endOfStorage = tmp + n;
            }
        }

        void resize(size_t n, const T& value = T())
        {
            if (n <= size())
            {
                _finish = _start + n;
            }
            else
            {
                reserve(n);
                while (_finish < _start + n)
                {
                    *_finish = value;
                    _finish++;
                }
            }
        }

        ///access///
        T& operator[](size_t pos)
        {
            assert(pos < size());
            return _start[pos];
        }

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

        ///modify/
        void push_back(const T& x)
        {
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 4 : 2 * capacity());
            }
            *_finish = x;
            _finish++;
        }

        void pop_back()
        {
            assert(_start != _finish);
            _finish--;
        }

        void swap(vector<T>& v)
        {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_endOfStorage, v._endOfStorage);
        }

        iterator insert(iterator pos, const T& x)
        {
            assert(pos >= _start);
            assert(pos < _finish);
            if (_finish == _endOfStorage)
            {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : 2 * capacity());
                pos = _start + len;
            }

            iterator end = _finish;
            while (pos < end)
            {
                *end = *(end - 1);
                end--;
            }
            *pos = x;
            ++_finish;
            return pos;
        }

        iterator erase(iterator pos)
        {
            assert(pos >= _start);
            assert(pos < _finish);
            iterator it = pos;
            while (it < _finish - 1)
            {
                *it = *(it + 1);
                it++;
            }
            _finish--;
            return pos;
        }
    private:
        iterator _start = nullptr; // 指向数据块的开始
        iterator _finish = nullptr; // 指向有效数据的尾
        iterator _endOfStorage = nullptr; // 指向存储容量的尾
    };
}