C++ vector实现

2021/7/12 11:08:16

本文主要是介绍C++ vector实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 引入
  • 一、成员变量
  • 二、主要接口模拟
    • 2.1 size && capacity && operator[ ]
    • 2.2 begin && end
    • 2.3 默认成员函数
    • reserve && resize
    • 插入删除操作


引入

vector英文翻译是向量,这个名字可以说是很形象了。vector在C++中是一个可以动态增容的数组,它像string一样拥有一个随机的迭代器,支持随机访问vector的位置。vector可以说就是C语言中的顺序表,但是又有顺序表不具有的优点,比如使用了模板,支持不同类型的vector同时存在。

一、成员变量

每写一个类,我认为应该优先考虑的就是成员变量。但是成员变量往往需要在成员函数的实现过程中确认。还好STL中有实现好的一份,我们参考一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace my_stl //因为我的vector名字和stl里相同,所以namespace封装一下
{
template<class T>
class vector
{
public:
    typedef T* iterator;
    typedef const T* const_iterator;
private:
iterator _start; //指向vector的第一个位置
iterator _finish; //指向vector的最后一个位置的下一个位置
iterator _end_of_storage; //指向vector的容量的最后一个位置的下一个位置
};
}

成员变量

二、主要接口模拟

我们顺着stl的实现来一步一步走。较简单的只提供代码,不做讲解。

2.1 size && capacity && operator[ ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
size_t size() const{
    return _finish - _start;
}
size_t capacity() const{
    return _end_of_storage - _start;
}
T& operator[](size_t pos){
    assert(pos < size());
    return _start[pos];
}
const T& operator[](size_t pos) const{
    assert(pos < size());
    return _start[pos];
}

2.2 begin && end

1
2
3
4
5
6
7
8
9
10
11
12
13
iterator begin(){
    return _start;
}
iterator end(){
    return _finish;
}
// const迭代器
const_iterator begin() const{
    return _start;
}
const_iterator end() const{
    return _finish;
}

2.3 默认成员函数

构造函数有好几个版本,只实现几个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 无参构造,禁止隐式类型转换
explicit vector()
 :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}
 //一个参数n的构造函数
explicit vector(size_t n, const T& val = T())
:_start(new T[n]), _finish(_start), _end_of_storage(_start + n) {
    for(size_t i = 0; i < n; ++i){
        *(_finish++) = val;
    }
}
//迭代器构造函数
template <class InputIterator>
  vector (InputIterator first, InputIterator last)
  :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){
        reserve(last - first);
        while(first != last){
            push_back(*first);
            ++first;
        
  }
//initializer_list
vector(initializer_list<T> il){
    auto it = il.begin();
    while(it != il.end()){
        push_back(*it);
        ++it;
    }
}

几点注意:前两个构造函数不接受隐式类型转换。后两个代码有大量重复。可以重写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public:
template <class InputIterator>
  vector (InputIterator first, InputIterator last)
  :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){
    reserve(last - first);
    range_initialize(first, last);
  }
   
  vector(initializer_list<T> il){
    range_initialize(il.begin(), il.end());
 }
 // 复用的部分
private:
template<class InputIterator>
void range_initialize(InputIterator first, InputIterator last){
    while(first != last){
            push_back(*first);
            ++first;
        
}

拷贝构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// traditional 写法
vector(const vector<T>& v)
:_start(new T[v.capacity()])
,_finish(_start)
,_end_of_storage(_start + v.capacity())
{
    for (size_t i = 0; i < v.size(); ++i){
    *(_finish++) = v[i];
  }
}
// mordern写法
  vector(const vector<T>& v)   //拷贝构造现代写法
:_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)  
    {
             reserve(v.capacity()); //提前开好空间
            for (const auto& e : v)
                push_back(e);
    }
     
// 更mordern的写法
void swap(vector<T>& v){
    ::swap(_start, v._start);
    ::swap(_finish, v._finish);
    ::swap(_end_of_storage, v._end_of_storage);
}
vector(const vector<T>& v)
:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}
// C++ 11  移动构造
vector(vector<T>&& v)
:_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{
    swap(v);
}

代码中出现的未知函数的实现在下面给出。
operator=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// traditional 写法
vector<T>& operator=(const vector<T>& v){
    if(this != &v){
      vector<T> tmp(v);
      swap(tmp);
    }
    return *this;
}
// modern写法 pass-by-value
vector<T>& operator=(vector<T> v){
    if(this != &v)
    swap(v);
    return *this;
}
// C++ 11 移动赋值
vector<T>& operator=(vector<T>&& v){
    swap(v);
    return *this;
}

实际上移动赋值可以不用写,因为赋值的现代写法就包括了移动赋值。
析构

1
2
3
4
5
6
7
void clear() noexcept{
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
}
~vector(){
    clear();
}

reserve && resize

vector是可以动态增容的数组,所以自然提供增容函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void reserve(size_t n){
    assert(n > capacity());
    size_t sz = size();
    T* tmp = new T[n]; //开空间
    delete[] _start;   //释放旧空间
    for(size_t i = 0; i < size(); ++i){
        tmp[i] = _start[i];
    } //拷贝数据,利用赋值 + 循环
 
    _start = tmp;
    _finish = _start + sz; //这里不能加上 size(),不然有问题
    _end_of_storage = _start + n;
}
 
void resize(size_t n, const T& val = T()){
    if(n <= size()){
        _finish = _start + n;
        return ;
    }
    if(n > capacity()){
        reserve(n);
    }
    for(size_t i = size(); i < n; ++i){
        *(_finish++) = val;
    }
}

插入删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void push_back(const T& val){
    /*if(size() == capacity()){
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }
    *(_finish++) = val; */
    insert(end(), val);
}
 
void pop_back(){
    assert(size() > 0);
    --_finish;
}
 
iterator insert(iterator pos, const T& val = T()) //返回迭代器位置,防止迭代器失效
{
    size_t position = pos - _start;
    assert(pos >= _finish && pos <= _finish);
    if(size() == capacity()){
        size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newCapacity);
    }
     
    iterator end = _finish;
    while(end >= _start + position){
        *(end + 1) = *end;
        --end;
    }
    *(_start + position) = val;
    ++_finish;
    return _start + position;
}
 
iterator erase(iterator pos){
    assert(pos >= _finish && pos <= _finish);
    iterator begin = pos;
    while(begin < _finish){
        *begin = *(begin + 1);
        ++begin;
    }
    --finish;
    return pos;
}

迭代器失效问题:当我们调用某些使容量变动的函数时,例如reserve,push_back,可能会引起迭代器失效。因为增容可能导致重新开辟空间,导致pos指向释放过的空间。
实际上,vector的删除操作也会导致迭代器失效。但是删除操作不会重新开辟空间。究其原因是pos迭代器对应的值被删除了,导致pos的值锁定的值变了,删除效果变了。
我们可以在使用前对迭代器重新赋值即可。
(全文完)



这篇关于C++ vector实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


原文链接: https://blog.csdn.net/qq_53558968/article/details/118488251
扫一扫关注最新编程教程