当前位置:首页 » 《随便一记》 » 正文

C++笔记---vector

14 人参与  2024年09月22日 18:01  分类 : 《随便一记》  评论

点击全文阅读


1. vector的介绍

vector其实就是我们所熟知的顺序表,但其是作为STL中的一个类模板而存在。

也就是说,vector是可以用来存储任意类型数据的顺序表,既可以是内置类型,也可以是自定义类型,或是STL中的其他容器。

vector的使用方式与string基本相似,但其接口相对于string来说要简洁地多,也与之后会介绍地各种STL的类模板跟为接近。

具体以vector - C++ Reference为准,本文为该文档的一个简单总结与标注。

2. vector的重要接口

以下表格中的函数都不是官方库中的函数原型,而是为了方便学习和理解而进行了简化的。

2.1 默认成员函数

2.1.1 构造函数

四种构造方式
(1) vector();默认构造函数
(2) vector(size_t n, cosnt T& val = T());构造并用val初始化前n个数据

(3) template <class InputIterator>

      vector(InputIterator first, InputIterator last);

用迭代器区间进行初始化
(4) vector(const vector& x);拷贝构造
 2.1.2 析构函数

释放掉容器内的资源。

2.1.3 赋值重载

 分配新的数据到容器中,替代他本来的数据,并根据新数据修改其size和capacity(深拷贝)。

2.2 迭代器相关

begin返回开始位置的迭代器
end返回最后一个数据的下一个位置的迭代器
rbegin用于逆向迭代
rend用于逆向迭代
cbegin用于const修饰的容器的迭代
cend用于const修饰的容器的迭代
crbegin用于const修饰的容器的逆向迭代
crend用于const修饰的容器的逆向迭代

2.3 大小容量相关

size_t size() const;返回数据个数
size_t max_size() const;返回容量大小
void resize(size_t n, T val = T());修改数据个数,若n<size则删除数据,若n>size则用val初始化多出来的数据
size_t capacity() const;返回容量大小
bool empty() const;判断容器是否为空
void reserve(size_t n);

确保capacity>=n,若capacity<n则扩容,若capacity>=n则无任何影响

void shrink_to_fit();是capacity减小到size,以减少空间浪费

2.4 访问相关

(1) vector<T>& operator[](size_t n);

(2) const vector<T>& operator[](size_t n) const;

使vector中的元素可像数组一样被访问

(1) vector<T>& at(size_t n);

(2) const vector<T>& at(size_t n) const;

返回vector中下标为n的元素的引用

(1) vector<T>& front();

(2) const vector<T>& front() const;

返回vector中第一个元素的引用

(1) vector<T>& back();

(2) const vector<T>& back() const;

返回vector中最后一个元素的引用

(1) T* data();

(2) const T*data() const; 

返回存储vector中元素的数组的地址

2.5 元素修改相关

(1) template<class InputIterator>

     void assign(InputIterator first, InputIterator last);

(2) void assign(size_t n, const T& val);

给vector赋新的值,效果类似于重新构造这个vector
void push_back(const T& val); 在vector尾部插入一个元素
void pop_back();删除vector尾部的一个元素
(1) iterator insert(iterator pos, const T& val);
(2) void insert(iterator pos, size_t n, const T& val);
(3) template <class InputIterator>
     void insert(iterator position, InputIterator first,InputIterator last);
在指定位置插入元素,效率低,会导致该位置及之后数据的迭代器失效,非特殊情况不推荐使用
(1) iterator erase(iterator pos);
(2) iterator erase(iterator first, iterator last);
删除指定位置的数据,效率低,会导致该位置及之后数据的迭代器失效,非特殊情况不推荐使用
void swap(vector<T>& x);交换两个vector的数据
void clear();清空vector,使size变为0

3. vector不完全模拟实现示例

STL标准库中,vector包括三个成员变量:

_start起始位置的迭代器
_finish最后一个元素的下一个位置的迭代器
_end_of_storage最大容量的下一个位置的迭代器
#pragma once#include<iostream>#include<assert.h>namespace lbz{    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 cbegin() const        {            return _start;        }        const_iterator cend() const        {            return _finish;        }        // construct and destroy        // 可以不写初始化列表        vector()            :_start(nullptr)            ,_finish(nullptr)            ,_end_of_storage(nullptr)        {}        // C++11强制生成默认构造        // vector() = default;        vector(int n, const T& value = T())        {            reserve(n);            while (n--)            {                push_back(value);            }        }        vector(size_t n, const T& value = T())        {            reserve(n);            while (n--)            {                push_back(value);            }        }        template<class InputIterator>        vector(InputIterator first, InputIterator last)        {            while (first != last)            {                push_back(*first);                first++;            }        }        /*vector(const vector<T>& v)        {            vector<T> tmp(v.cbegin(), v.cend());            swap(tmp);        }*/        vector(const vector<T>& v)        {            reserve(v.size());            auto it = v.cbegin();            while (it != v.cend())            {                push_back(*it);                it++;            }        }        vector<T>& operator= (vector<T> v)        {            swap(v);            return *this;        }        ~vector()        {            if(_start)                delete[] _start;            _start = nullptr;            _finish = nullptr;            _end_of_storage = nullptr;        }         // capacity        size_t size() const        {            return (_finish - _start);        }        size_t capacity() const        {            return (_end_of_storage - _start);        }        /*void reserve(size_t n)        {            size_t old_size = size();            size_t old_capacity = capacity();            if (n > old_capacity)            {                while (n > old_capacity)                {                    old_capacity = old_capacity == 0 ? 4 : old_capacity * 2;                }                T* tmp = new T[old_capacity];                //元素有动态资源时,memcpy存在问题                memcpy(tmp, _start, sizeof(T) * old_size);                delete[] _start;                _start = tmp;                _finish = _start + old_size;                _end_of_storage = _start + old_capacity;            }        }*/        void reserve(size_t n)        {            size_t old_size = size();            size_t old_capacity = capacity();            if (n > old_capacity)            {                while (n > old_capacity)                {                    old_capacity = old_capacity == 0 ? 4 : old_capacity * 2;                }                T* tmp = new T[old_capacity];                for (size_t i = 0; i < old_size; i++)                {                    tmp[i] = _start[i];                }                delete[] _start;                _start = tmp;                _finish = _start + old_size;                _end_of_storage = _start + old_capacity;            }        }        void resize(size_t n, const T& value = T())        {            if (n < size())            {                _finish = _start + n;            }            else            {                reserve(n);                while (size() < n)                {                    push_back(value);                }            }        }        ///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)        {            reserve(size() + 1);            *_finish = x;            _finish++;        }        void pop_back()        {            _finish--;        }        void swap(vector<T>& v)        {            std::swap(_start, v._start);            std::swap(_finish, v._finish);            std::swap(_end_of_storage, v._end_of_storage);        }        iterator insert(iterator pos, const T& x)        {            assert(pos >= begin() && pos < end());            size_t old_pos = pos - _start;            reserve(size() + 1);            pos = _start + old_pos;            //typename vector<int>::iterator end = end();            auto end = this->end();            while (end != pos)            {                *end = *(end - 1);                end--;            }            *end = x;            _finish++;            return pos;        }        iterator erase(iterator pos)        {            assert(pos >= begin() && pos < end());            iterator it = pos;            while (it != end() - 1)            {                *it = *(it + 1);                it++;            }            _finish--;            return pos;        }    private:        iterator _start = nullptr; // 指向数据块的开始        iterator _finish = nullptr; // 指向有效数据的尾        iterator _end_of_storage = nullptr; // 指向存储容量的尾    };}

4. 迭代器失效问题

顾名思义,就是迭代器失去访问容器中元素的能力。

导致迭代器失效发生的有两种情况:(1)底层空间改变,(2)指定位置元素删除(erase)

4.1 底层空间改变导致迭代器失效

会引起其底层空间改变的操作(扩容或者赋值),都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。

#include <iostream>using namespace std;#include <vector>int main(){    vector<int> v{1,2,3,4,5,6};    auto it = v.begin();    // 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容    // v.resize(100, 8);    // reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变    // v.reserve(100);    // 插入元素期间,可能会引起扩容,而导致原空间被释放    // v.insert(v.begin(), 0);    // v.push_back(8);    // 给vector重新赋值,可能会引起底层容量改变    v.assign(100, 8);    while(it != v.end())    {        cout<< *it << " " ;        ++it;    }     cout<<endl;    return 0;}

出错原因:

以上操作,都有可能会导致vector发生扩容,而vector只要发生扩容都是异地扩,并且vector的迭代器实质上是指针。

这意味着,一旦发生扩容,原本的空间就会被释放掉,_start,_finish,_end_of_storage会分别指向新空间。但此时,it仍旧指向旧空间,变成了一个野指针。

在对it迭代器操作时,实际操作的是一块已经被释放的空间,而引起代码运行时崩溃。

解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,就需要给it重新赋值。

其中,insert函数会返回指向插入元素的迭代器(插入单个元素时)。

4.2 指定位置元素删除(erase)导致迭代器失效

#include <iostream>using namespace std;#include <vector>int main(){    int a[] = { 1, 2, 3, 4 };    vector<int> v(a, a + sizeof(a) / sizeof(int));    // 使用find查找3所在位置的iterator    vector<int>::iterator pos = find(v.begin(), v.end(), 3);    // 删除pos位置的数据,导致pos迭代器失效。    v.erase(pos);    cout << *pos << endl; // 此处会导致非法访问    return 0;}

这里有人会说:删掉3之后pos不是指向4吗?

你说的对,但是假如被删除的是最后一个元素呢?假如此处不是vector(顺序表)而是list(链表)呢?假如迭代器的底层根本就不是指针呢?

如果是以上三种情况,被删除元素的迭代器还会被下一个元素继承吗?显然不会,那么此时对pos解引用就会导致非法访问。

由于STL的实现是希望用户能够忽略掉底层实现,那么关于这个问题最好是要做到所有容器统一,认为对pos的访问是非法访问。

解决方法:和insert类似,erase函数在删除数据之后,会返回被删除数据的下一个位置的迭代器,让pos重新接收一下即可。

4.3 其他

windows下,vs编译器对迭代器的检测十分严格,一旦发生对失效的迭代器解引用的操作就一定会报错。

Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端。

前面讲到的string和vector存在相同的迭代器失效的问题,注意警惕。

5. 使用memcpy拷贝的问题

前面在string的实现中,我们在进行异地扩容时使用了memcpy将原本的数据拷贝到新空间中。

但是在这里,我们则采用了手动赋值的方式,这是为什么呢?

void reserve(size_t n){    size_t old_size = size();    size_t old_capacity = capacity();    if (n > old_capacity)    {        while (n > old_capacity)        {            old_capacity = old_capacity == 0 ? 4 : old_capacity * 2;        }        T* tmp = new T[old_capacity];        //元素有动态资源时,memcpy存在问题        memcpy(tmp, _start, sizeof(T) * old_size);        delete[] _start;        _start = tmp;        _finish = _start + old_size;        _end_of_storage = _start + old_capacity;    }}void reserve(size_t n){    size_t old_size = size();    size_t old_capacity = capacity();    if (n > old_capacity)    {        while (n > old_capacity)        {            old_capacity = old_capacity == 0 ? 4 : old_capacity * 2;        }        T* tmp = new T[old_capacity];        for (size_t i = 0; i < old_size; i++)        {            tmp[i] = _start[i];        }        delete[] _start;        _start = tmp;        _finish = _start + old_size;        _end_of_storage = _start + old_capacity;    }}

我们设想下面这样的情况:

int main(){    lbz::vector<lbz::string> v;    v.push_back("1111");    v.push_back("2222");    v.push_back("3333");        reserve(5);    return 0;}

在三次push_back完成之后,v中存储了三个string类型的对象,他们的_str分别指向str1 = "1111",str2 = "2222",str3 = "3333"。

接着,我们对vector进行了扩容,如果我们采用memcpy进行拷贝,那么只能完成对三个string对象的浅拷贝,也就是tmp中的三个string对象的_str依然指向str1,str2和str3。

当我们delete[] _start时,三个string类型的对象调用对应的析构函数分别释放掉str1,str2和str3。

此时,tmp中三个string对象的_str就都成了野指针,如果对其访问,就会造成程序的崩溃。

结论:

如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。

 6. 动态二维数组

对于vector<vector<int>>的理解有困难的小伙伴,可以参考这篇文章:如何开辟动态二维数组(C语言)_动态开辟二维数组-CSDN博客


点击全文阅读


本文链接:http://zhangshiyu.com/post/163176.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1