@[TOC]

前言：

博主收集的资料New Young，连载中。

博主收录的问题:New Young

转载请标明出处：New Young

vector与数组

vector在底层是一种类似数组的C++类模板，因此vector容器一但实例化其大小是不变的，但是容器中指向堆上的元素对象是动态变化的，支持“增删查改"，同数组一样对于插入，insert的效率是很低的

在这里插入图片描述

迭代器---“通用指针"

迭代器的本质

循环的控制方式有2种：标志控制(while),计数控制(for),而迭代器将这2种循环方式的统一为一种控制方式---迭代器控制---“通用指针"
为什么称迭代器为指针，因为其的行为和指针非常相似，另外不同容器的迭代器类型是不同的，因此这里的“通用"是一种概念上的通用
几乎所有的的泛型容器和泛型算法都使用迭代器来访问对象

迭代器的分类

迭代器	功能
Input_iterator--输入迭代器	只提高读操作
Output_iterator--输出迭代器	只提高写操作
Forward_iterator--单向迭代器	只能向前访问下一元素，不能向后访问，支持++
Bidirectional_iterator--双向迭代器	双向访问迭代器，支持++与--
Random_iterator--随机迭代器	可以随机访问对象中的每一个元素，支持++，-,+,--等运算

从表中可以得出，功能更全的迭代器是支持向功能少的迭代器支持的接口进行传参的

在这里插入图片描述

迭代器失效

迭代器失效指的是：当容器底层发生变化，原来的迭代器可能由于元素存储位置的变动，成为野指针或者后续的迭代器不在指向准确的数据。
常见的引发操作：insert()时的扩容，erase（）的缩容，clear（），remove()等
解决方法：及时的更新迭代器并通过返回值得到正确的指向下一个元素的

vector功能复写

成员变量

typedef T* iterator;
iterator _start;
iterator _finish;
iterator _end_of_storage;

构造函数

默认构造函数

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

自定义的构造函数

vector支持通过迭代器区间来初始化对象

    template<class inputIterator>
    vector(inputIterator first, inputIterator last)
        :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)

    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

拷贝构造函数

vector(const vector<T>& v)//提前初始化成员，防止delete随机值
        : _start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
    {
    
        vector<T> tmp(v.begin(), v.end());
        std::swap(_start, tmp._start);
        std::swap(_finish, tmp._finish);
        std::swap(_end_of_storage, tmp._end_of_storage);
    }

赋值运算符

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

size()

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

capacity()

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

operator[]

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

begin()

typedef T* iterator;
    iterator begin()
    {

        return _start;
    }
typedef T* const_iterator;
    const_iterator begin()const
    {
        return _start;

    }

end()

typedef T* iterator;
iterator end()
    {
        return _finish;

    }
typedef T* const_iterator;
const_iterator end()const
    {
        return _finish;

    }

reserve()

void reserve(size_t n)
    {
        if (n > capacity())
        {
            T* tmp = new T[n];
            int sz = size();
            if (_start != nullptr)
            {
                //使用memcpy会导致浅拷贝野指针问题
                //memcpy(tmp, _start, sizeof(T)*sz);
                
                //使用深拷贝赋值
                // 或者定位new
                for (size_t i = 0; i < sz; ++i)
                {
                    //调用深拷贝的赋值函数
                    tmp[i] = _start[i];
                
                }
                delete[]_start;
            }
                

            _start = tmp;
            //注意这里要用旧的size，因为_start改变时，
            //finish未变，直接使用size()，可能会出现负的情况
            _finish = _start + sz;
            _end_of_storage = _start + n;
        }
    }

resize()

编译器对很多类型包括内置类型都将它们进行了提升，类似一种类，因此int()=0；

    void resize(size_t n, const T& value = T())
    {
        if (n < size())
        {
            _finish = _start + n;
        }
        else
        {
            if (n > capacity())
            {
                reserve(n);
            }
            //初始化大于size()的空间
            for (size_t i =  size(); i < n; ++i)
            {
                _start[i]  = value;
            }
            _finish = _start + n;
            _end_of_storage = _start + n;
        }
    }

push_back()

void push_back(const T& value)
    {
        if (_finish == _end_of_storage)
        {
            reserve(capacity() == 0 ? 4 : 2 * capacity());
        }
        *_finish = value;
        ++_finish;

    }

pos_back()

void pop_back()
    {
        assert(_finish > _start);
         --_finish;
            
    }

insert()

如果inisrt中发生了扩容导致pos指向的空间被释放
又pos本身是一个指针，这就成了对野指针的操作是非法的----迭代器失效

iterator  insert(iterator  pos,const T& value)
    {
        assert(pos >= _start);
        assert(pos <= _finish);

        //扩容会导致pos失效，需要更新pos
        if (_finish == _end_of_storage)
        {
            size_t len = pos - _start;
            reserve(capacity() == 0 ?  4 : 2 * capacity());
            pos = _start + len;
        }

        iterator end = _finish;
        while (end > pos)
        {
        
            *(end) = *(end - 1);
            --end;
        }

        *pos = value;
        ++_finish;
        return pos;
    }

erase()

    //不同版本的erase可能会 异地 缩容，因此要返回一个
    iterator erase(iterator  pos)
    {
    
        assert(pos >= _start);
        assert(pos < _finish);
            
        iterator begin = pos + 1;
        while (begin < _finish)
        {
            *(begin - 1) = *(begin);
            ++begin;
        }
        --_finish;
        return pos;
    }

find(）

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

全部代码

Vector.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdlib.h> 
#include <string>
#include <assert.h>
#include<time.h>
#include<windows.h>
#include<algorithm>
#include<vector>

namespace My_Vet
{
template <class T>
class vector
{
public:
    typedef T* iterator;
    iterator begin()
    {

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

    }
    typedef T* const_iterator;
    const_iterator begin()const
    {
        return _start;

    }
    const_iterator end()const
    {
        return _finish;

    }


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

    //传统写法
    /*vector(const vector<T>& v)
    {

        T* tmp = new <T>[v.size()*sizeof(T)];
        delete[]_start;
        _start = tmp;
        _finish = tmp + v.size();
        _end_of_storage = tmp + v.capacity();
        //传统写法要考虑浅拷贝问题
        //memcpy(_start, v._start, sizeof(T)*v.size());
        for(size_t i =0;i<sz;++i)
        {
                _start[i]=v._start[i];
        }
        
    }*/

    //现在写法
    //因为vector只有默认的构造函数，无自定义构造函数，因此需要自定义构造函数
    // 
    template<class inputIterator>
    vector(inputIterator first, inputIterator last)
        :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)

    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

    vector(const vector<T>& v)//提前初始化成员，防止delete随机值
        : _start(nullptr),
        _finish(nullptr),
        _end_of_storage(nullptr)
    {
    
        vector<T> tmp(v.begin(), v.end());
        std::swap(_start, tmp._start);
        std::swap(_finish, tmp._finish);
        std::swap(_end_of_storage, tmp._end_of_storage);
    }

    //现代写法
    vector<T>& operator=(vector<T>v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_end_of_storage, v._end_of_storage);
    }
    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];
    }


    void reserve(size_t n)
    {
        if (n > capacity())
        {
            T* tmp = new T[n];
            int sz = size();
            if (_start != nullptr)
            {
                //使用memcpy会导致浅拷贝野指针问题
                //memcpy(tmp, _start, sizeof(T)*sz);
                
                //使用深拷贝赋值
                // 或者定位new
                for (size_t i = 0; i < sz; ++i)
                {
                    //调用深拷贝的赋值函数
                    tmp[i] = _start[i];
                
                }
                delete[]_start;
            }
                

            _start = tmp;
            //注意这里要用旧的size，因为_start改变时，
            //finish未变，直接使用size()，可能会出现负的情况
            _finish = _start + sz;
            _end_of_storage = _start + n;
        }
    }
    
    //编译器对很多类型包括内置类型都将它们进行了提升，类似一种类，因此int()=0；
    void resize(size_t n, const T& value = T())
    {
        if (n < size())
        {
            _finish = _start + n;
        }
        else
        {
            if (n > capacity())
            {
                reserve(n);
            }
            //初始化大于size()的空间
            for (size_t i =  size(); i < n; ++i)
            {
                _start[i]  = value;
            }
            _finish = _start + n;
            _end_of_storage = _start + n;
        }
    }
    void push_back(const T& value)
    {
        if (_finish == _end_of_storage)
        {
            reserve(capacity() == 0 ? 4 : 2 * capacity());
        }
        *_finish = value;
        ++_finish;

    }

    void pop_back()
    {
        assert(_finish > _start);
         --_finish;
            
    }
    //如果inisrt中发生了扩容导致pos指向的空间被释放
    //又pos本身是一个指针，这就成了对野指针的操作是非法的----迭代器失效

    iterator  insert(iterator  pos,const T& value)
    {
        assert(pos >= _start);
        assert(pos <= _finish);

        //扩容会导致pos失效，需要更新pos
        if (_finish == _end_of_storage)
        {
            size_t len = pos - _start;
            reserve(capacity() == 0 ?  4 : 2 * capacity());
            pos = _start + len;
        }

        iterator end = _finish;
        while (end > pos)
        {
        
            *(end) = *(end - 1);
            --end;
        }

        *pos = value;
        ++_finish;
        return pos;
    }

    //不同版本的erase可能会 异地 缩容，因此要返回一个
    iterator erase(iterator  pos)
    {
    
        assert(pos >= _start);
        assert(pos < _finish);
            
        iterator begin = pos + 1;
        while (begin < _finish)
        {
            *(begin - 1) = *(begin);
            ++begin;
        }
        --_finish;
        return pos;
    }

    ~vector()
    {
        delete[]_start;
        _start = _finish = _end_of_storage = nullptr;
        //std::cout << "~vector()" << std::endl;
    }

    //iterator find()
    //{
    //


    //}
    private:
        iterator _start;
        iterator _finish;
        iterator _end_of_storage;

};
}

STL——vector与迭代器

前言：

vector与数组

迭代器---“通用指针"

迭代器的本质

迭代器的分类

迭代器失效

vector功能复写

成员变量

构造函数

默认构造函数

自定义的构造函数

拷贝构造函数

赋值运算符

size()

capacity()

operator[]

begin()

end()

reserve()

resize()

push_back()

pos_back()

insert()

erase()

find(）

全部代码

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

STL——vector与迭代器

前言：

vector与数组

迭代器---“通用指针"

迭代器的本质

迭代器的分类

迭代器失效

vector功能复写

成员变量

构造函数

默认构造函数

自定义的构造函数

拷贝构造函数

赋值运算符

size()

capacity()

operator[]

begin()

end()

reserve()

resize()

push_back()

pos_back()

insert()

erase()

find(）

全部代码

热门文章

最新文章

相关电子书