面试十五 容器

一、vector容器 

template<typename T>
class Allocator{
public:
    T* allocator(size_t size){
    // 负责内存开辟
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(void * p){
        free(p);
    }
    void construct(T*p,const T&val){
        // 定位new
        new (p) T(val);
    }
    void destroy(T*p){
       p->~T();
    }

};


template<typename T, typename Alloc = Allocator<T>>
class vector{
public:
    vector(int size=10){
        //  需要把内存开辟和对象构造分开处理
        //  _first = new T[size];
        _first= _allocator.allocator(size);
        _end = _first + size;
        _last =_first;
    }
    ~vector(){
        //  delete[] _first;
        //  析构容器有效的元素，然后释放_first指针指向的堆内存

        for (T* p = _first; p != _last; ++p){
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
            }
        _allocator.deallocate(_first); // 释放堆上的数组内存
        _first=_last=_end= nullptr;
    }


    vector(const Vector<T>& src){
        int size = src._last-src._first;
//        _first =new T[size];
        _first = _allocator.allocator(size);
        int len=src._last-src._first;
        for(int i=0;i<len;i++){
//            _first[i]=src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    vector<T>& operator=(const vector<T>&src){
        if(this==&src){
            return *this;
        }
//        delete[] _first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first);
        int size = src._end - src._first;
        int len = src._last - src._first;
//        _first = new T[size];
        _first=_allocator.allocate(size);
        for (int i=0; i<len; ++i) {
//            _first[i] = src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }


    void push_back(const T &x) {
        if (full()) {
            resize();
        }
//        *_last ++ = x;
        _allocator.construct(_last, x);
        _last++;
    }
    void pop_back() {
        if (empty()) {
            return;
        }
        _allocator.destroy(_last);
        --_last;
    }

    T back() const {
        if (empty()) {

        }
        return *(_last-1);
    }

    bool full() {
        return _end == _last;
    }

    bool empty() {
        return _last == _first;
    }
    void resize() {
        int size=_end-_first;
//        T *tmp = new T[2*size];
        T* tmp = _allocator.allocator(2 * size);
        int len = _last-_first;
//        for(int i=0; i<len; ++i) {
//            tmp[i] = _first[i];
//        }
//        delete[] _first;
        for (int i = 0; i < size; ++i)
        {
            //ptmp[i] = _first[i];
            _allocator.construct(tmp + i, _first[i]);
        }
        //delete[]_first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first);
        _first = tmp;
        _end = _first + 2*size;
        _last = _first + len;
    }
    int size() const{
        return _last-_first;
    }
    T& operator[](int index){
        if(index<0 || index>=size()){
            throw "OutOfException";
        }
        return _first[index];
    }

    // 迭代器一般实现成容器的嵌套类型
    class iterator{
    public:
        iterator(T* ptr = nullptr):_ptr(ptr){}
        bool operator !=(const iterator &it) const{
            return _ptr !=it._ptr;
        }
        void operator++(){
            _ptr++;
        }
        T* operator*() {return *_ptr;}
        const T& operator*()const {return  *_ptr;}
    private:
        T* _ptr;
    };

    // 给容器提供begin() 和end()方法
    iterator begin(){return iterator(_first);}
    iterator end(){return iterator(_last);}

    // for each的底层也是iterator

     
private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _allocator; // // 定义容器的空间配置器对象


};


int main() {
    Test t1;
    Test t2;
    vector<Test> vec;
    vec.push_back(t1);
    vec.push_back(t2);
    cout << "===========================" << endl;
    vec.pop_back();
    cout << "===========================" << endl;
    return 0;
}

二、迭代器失效

        迭代器失效是指：迭代器的底层其实就是容器的原生指针，插入元素可能导致容器内部的数据结构重新分配，从而使得原先的迭代器指向的位置不再有效；删除元素可能导致迭代器指向的位置被移动或删除，从而使得原先的迭代器不再指向期望的位置。也就是说原来的指针指向的内容被改变了，而不是现在内存中存的。

怎么判断迭代器失效没有：

        容器迭代器失效增加代码，它是一个结构体维护了一个链表。cur是指向某一个结构体的指针，又定义了一个指向下一个Iterator_Base节点的地址，还定义了一个头节点。记录了用户从中获取的哪一个元素的迭代器，记录在Iterator_Base链表中，哪一个迭代器增加或删除要让其失效并重新更新。 

        然后判断链表中的迭代器，看它是否在插入、删除点和_last之间，将会失效，失效的话将迭代器的容器对象赋值为nullptr，再进行 operator !=  、 operator++ 、 insert、erase进行操作时候，先判断迭代器是否失效。

    void verify(T* first,T* last){
        Iterator_Base *pre = &this->_head;
        Iterator_Base *it =this->_head._next;
        while(it!= nullptr){
            if(it->_cur->_ptr >first && it->_cur->_ptr <=last){
                it->_cur->_pVec = nullptr;
                pre->_next =it->_next;
                delete it;
                it=pre->_next;
            }else{
                pre=it;
                it=it->_next;
            }
        }
    }

 所有代码：

//
// Created by zhangchuang on 2024/4/22.
//

#include <iostream>
using namespace std;
//#include <vector>


template<typename T>
class Allocator{
public:
    T* allocator(size_t size){
        // 负责内存开辟
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(void * p){
        free(p);
    }
    void construct(T*p,const T&val){
        // 定位new
        new (p) T(val);
    }
    void destroy(T*p){
        p->~T();
    }

};


template<typename T, typename Alloc = Allocator<T>>
class vector{
public:
    vector(int size=10){
        //  需要把内存开辟和对象构造分开处理
        //  _first = new T[size];
        _first= _allocator.allocator(size);
        _end = _first + size;
        _last =_first;
    }
    ~vector(){
        //  delete[] _first;
        //  析构容器有效的元素，然后释放_first指针指向的堆内存

        for (T* p = _first; p != _last; ++p){
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first); // 释放堆上的数组内存
        _first=_last=_end= nullptr;
    }


    vector(const vector<T>& src){
        int size = src._last-src._first;
//        _first =new T[size];
        _first = _allocator.allocator(size);
        int len=src._last-src._first;
        for(int i=0;i<len;i++){
//            _first[i]=src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    vector<T>& operator=(const vector<T>&src){
        if(this==&src){
            return *this;
        }
//        delete[] _first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p); // 把_first指针指向的数组的有效元素进行析构操作
        }
        _allocator.deallocate(_first);
        int size = src._end - src._first;
        int len = src._last - src._first;
//        _first = new T[size];
        _first=_allocator.allocate(size);
        for (int i=0; i<len; ++i) {
//            _first[i] = src._first[i];
            _allocator.construct(_first + i, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }


    void push_back(const T &x) {
        if (full()) {
            resize();
        }
//        *_last ++ = x;
        _allocator.construct(_last, x);
        _last++;
    }
    void pop_back() {
        if (empty()) {
            return;
        }
        // 验证迭代器是否失效

        verify(_last-1, _last);
        // 如果是erase   验证verify(it._ptr, _last);
        // insert  验证verify(it._ptr, _last);
        _allocator.destroy(_last);
        --_last;
    }

    T back() const {
        if (empty()) {

        }
        return *(_last-1);
    }

    bool full() {
        return _end == _last;
    }

    bool empty() {
        return _last == _first;
    }
    void resize() {
        int size=_end-_first;
//        T *tmp = new T[2*size];
        T* tmp = _allocator.allocator(2 * size);
        int len = _last-_first;
//        for(int i=0; i<len; ++i) {
//            tmp[i] = _first[i];
//        }
//        delete[] _first;
        for (int i = 0; i < size; ++i)
        {
            //ptmp[i] = _first[i];
            _allocator.construct(tmp + i, _first[i]);
        }
        //delete[]_first;
        for (T* p = _first; p != _last; ++p)
        {
            _allocator.destroy(p);
        }
        _allocator.deallocate(_first);
        _first = tmp;
        _end = _first + 2*size;
        _last = _first + len;
    }
    int size() const{
        return _last-_first;
    }
    T& operator[](int index){
        if(index<0 || index>=size()){
            throw "OutOfException";
        }
        return _first[index];
    }

    // 迭代器一般实现成容器的嵌套类型
    class iterator{
    public:

        iterator(vector<T,Alloc>*pvec= nullptr,T* ptr = nullptr):_ptr(ptr),_pVec(pvec){
            Iterator_Base* itb = new Iterator_Base(this,_pVec->_head._next);
            _pVec->_head._next=itb;
        }

        bool operator !=(const iterator &it) const{
            // 检查迭代器的有效性
            if(_pVec == nullptr || _pVec!=it._pVec){
                throw "iterator incompatable!";
                return false;
            }
            return _ptr !=it._ptr;
        }
        void operator++(){
            // 检查迭代器的有效性,迭代器失效为空
            if(_pVec== nullptr){
                throw "iterator invalid";
            }
            _ptr++;
        }
        T* operator*() {return *_ptr;}
        const T& operator*()const {return  *_ptr;}
    private:
        T* _ptr;
        vector<T,Alloc> *_pVec;
    };

    // 给容器提供begin() 和end()方法
    iterator begin(){return iterator(_first);}
    iterator end(){return iterator(_last);}




    // 容器迭代器失效增加代码
    struct Iterator_Base{
        Iterator_Base(iterator *c = nullptr , Iterator_Base *n = nullptr):_cur(c),_next(n){}
        iterator *_cur;
        Iterator_Base *_next;
    };
    Iterator_Base _head;


    void verify(T* first,T* last){
        Iterator_Base *pre = &this->_head;
        Iterator_Base *it =this->_head._next;
        while(it!= nullptr){
            if(it->_cur->_ptr >first && it->_cur->_ptr <=last){
                it->_cur->_pVec = nullptr;
                pre->_next =it->_next;
                delete it;
                it=pre->_next;
            }else{
                pre=it;
                it=it->_next;
            }
        }
    }

    iterator insert(iterator it ,const T &val){
        // 1. 不考虑扩容
        // 2. 不考虑it._ptr的指针合法性
        verify(it._ptr -1 ,_last);
        T* p = _last;
        while(p>it._ptr){
            _allocator.construct(p,*(p-1));
            _allocator.destroy(p-1);
            p--;
        }
        _allocator.construct(p,val);
        _last++;
        return iterator(this,p);
    }

    iterator erase(iterator it ){
        // 1. 不考虑扩容
        // 2. 不考虑it._ptr的指针合法性
        verify(it._ptr -1 ,_last);
        T* p = _last;
        while(p<_last-1){
            _allocator.destroy(p);
            _allocator.construct(p,*(p+1));
            p++;
        }
        _allocator.destroy(p);
        _last--;
        return iterator(this,it._ptr);
    }



    // for each的底层也是iterator



private:
    T* _first;
    T* _last;
    T* _end;
    Alloc _allocator; // // 定义容器的空间配置器对象


};
/*
 vector怎么
 */

#if 0
int main(){
//    std::vector<int>vec{1,2,3,4,5,6,8};

    /*
     迭代器失效问题
     1. 删除元素
    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.erase(it);
        }
    }
    // 2.增加元素

    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.insert(it,*it-1);
        }
    }
     */


    // 2。 解决办法 -- 更新迭代器
    // 删除
    auto it =vec.begin();
    while(it!=vec.end()){
        if(*it%2==0){
            it=vec.erase(it);
        }else{
            ++it;
        }
    }

    // 增加
    for(auto it =vec.begin();it!=vec.end();it++){
        if(*it%2==0){
            vec.insert(it,*it-1);
            ++it;
        }
    }



}
#endif

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/573948.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Golang对接Ldap（保姆级教程：概念搭建实战）

Golang对接Ldap（保姆级教程：概念搭建实战）

Golang对接Ldap&#xff08;保姆级教程&#xff1a;概念&搭建&实战&#xff09; 最近项目需要对接客户的LDAP服务&#xff0c;于是趁机好好了解了一下。LDAP实际是一个协议&#xff0c;对应的实现&#xff0c;大家可以理解为一个轻量级数据库。用户查询。比如&#xff…
阅读更多...
DiT论文精读Scalable Diffusion Models with Transformers CVPR2023

DiT论文精读Scalable Diffusion Models with Transformers CVPR2023

Scalable Diffusion Models with Transformers CVPR2023 Abstract idea 将UNet架构用Transformer代替。并且分析其可扩展性。 并且实验证明通过增加transformer的宽度和深度&#xff0c;有效降低FID 我们最大的DiT-XL/2模型在classconditional ImageNet 512、512和256、256基…
阅读更多...
switch语句深讲

switch语句深讲

一。功能 1.选择&#xff0c;由case N:完成 2.switch语句本身没有分支功能&#xff0c;分支功能由break完成 二。注意 1.switch语句如果不加break&#xff0c;在一次判断成功后会执行下面全部语句并跳过判断 2.switch的参数必须是整形或者是计算结果为整形的表达式,浮点数会…
阅读更多...
centos 7 yum install -y nagios

centos 7 yum install -y nagios

centos 7 systemctl disable firewalld --now vi /etc/selinux/config SELINUXdisabled yum install -y epel-release httpd nagios yum install -y httpd nagios systemctl enable httpd --now systemctl enable nagios --now 浏览器 IP/nagios 用户名&#xff1a;…
阅读更多...
stack,queue的模拟实现以及优先级队列

stack,queue的模拟实现以及优先级队列

这篇博客用来记录stack&#xff0c;queue的学习。 stack的模拟实现 stack的模拟实现比较简单&#xff0c;先上代码 #pragma once #include<vector> #include<list> #include<deque> #include<iostream> using std::deque; using namespace std;name…
阅读更多...
【STM32HAL库】外部中断

【STM32HAL库】外部中断

目录 一、中断简介 二、NVIC 1.寄存器 2.工作原理 3.优先级 4.使用NVIC 三、EXTI 1.简介 2.AFIO&#xff1a;复用功能IO&#xff0c;主要用于重映射和外部中断映射配置​编辑 3. 中断使用 4.HAL库配置使用 一、中断简介 中断的意义&#xff1a;高效处理紧急程序&#xff0c;不会…
阅读更多...
树莓派学习笔记--串口通信（配置硬件串口进行通信）

树莓派学习笔记--串口通信（配置硬件串口进行通信）

树莓派串口知识点 树莓派4b的外设一共包含两个串口&#xff1a;硬件串口&#xff08;/dev/ttyAMA0&#xff09;,mini串口&#xff08;/dev/ttyS0&#xff09; 硬件串口由硬件实现&#xff0c;有单独的波特率时钟源&#xff0c;性能高&#xff0c;可靠&#xff1b;而mini串口性能…
阅读更多...
Java-AQS的原理

Java-AQS的原理

文章目录 基本概述1. 设计思想2. 基本实现 一些关键词语以及常用术语&#xff0c;主要如下&#xff1a; 信号量(Semaphore): 是在多线程环境下使用的一种设施&#xff0c;是可以用来保证两个或多个关键代码段不被并发调用&#xff0c;也是作系统用来解决并发中的互斥和同步问题…
阅读更多...
数据挖掘 | Count数据去除批次效应后不是整数甚至还出现负值导致无法进行差异分析怎么办？

数据挖掘 | Count数据去除批次效应后不是整数甚至还出现负值导致无法进行差异分析怎么办？

之前咱们介绍过数据挖掘 | 批次效应的鉴定与处理 | 附完整代码 注释 | 看完不会来揍我&#xff0c;但是很多小伙伴遇到了Count数据批次处理后不是整数甚至还出现负值的问题&#xff0c;这就导致无法使用某些包包进行差异分析&#xff08;对差异分析感兴趣的小伙伴可以查看&…
阅读更多...
MySQL中如何随机获取一条记录

MySQL中如何随机获取一条记录

点击上方蓝字关注我 随机获取一条记录是在数据库查询中常见的需求&#xff0c;特别在需要展示随机内容或者随机推荐的场景下。在 MySQL 中&#xff0c;有多种方法可以实现随机获取一条记录&#xff0c;每种方法都有其适用的情况和性能特点。在本文中&#xff0c;我们将探讨几种…
阅读更多...
word添加行号

word添加行号

打开页面设置&#xff0c;找到行号
阅读更多...
2018-2023年上市公司富时罗素ESG评分数据

2018-2023年上市公司富时罗素ESG评分数据

2018-2023年上市公司富时罗素ESG评分数据 1、时间&#xff1a;2018-2023年 2、来源&#xff1a;整理自WIND 3、指标&#xff1a;证券代码、简称、ESG评分 4、范围&#xff1a;上市公司 5、指标解释&#xff1a; 富时罗素将公司绿色收入的界定和计算作为公司ESG 评级打分结…
阅读更多...
「白嫖」开源的后果就是供应链攻击么？| 编码人声

「白嫖」开源的后果就是供应链攻击么？| 编码人声

「编码人声」是由「RTE开发者社区」策划的一档播客节目&#xff0c;关注行业发展变革、开发者职涯发展、技术突破以及创业创新&#xff0c;由开发者来分享开发者眼中的工作与生活。 面对网络安全威胁日益严重的今天&#xff0c;软件供应链安全已经成为开发者领域无法避免的焦点…
阅读更多...
OpenWRT设置自动获取IP，作为二级路由器

OpenWRT设置自动获取IP，作为二级路由器

前言 上一期咱们讲了在OpenWRT设置PPPoE拨号的教程&#xff0c;在光猫桥接的模式下&#xff0c;OpenWRT如果不设置PPPoE拨号&#xff0c;就无法正常上网。 OpenWRT设置PPPoE拨号教程 但现在很多新装的宽带&#xff0c;宽带师傅为了方便都会把光猫设置为路由模式。如果你再外…
阅读更多...
【A-024】基于SSH的房屋租赁管理系统（含论文）

【A-024】基于SSH的房屋租赁管理系统（含论文）

【A-024】基于SSH的房屋租赁管理系统&#xff08;含论文&#xff09; 开发环境&#xff1a; Jdk7(8)Tomcat7(8)MySQLIntelliJ IDEA(Eclipse) 数据库&#xff1a; MySQL 技术&#xff1a; SpringStruts2HiberanteBootstrapJquery 适用于&#xff1a; 课程设计&#xff0c;毕…
阅读更多...
半波整流220V转正5V负-5V100mA恒压WT5101A

半波整流220V转正5V负-5V100mA恒压WT5101A

半波整流220V转正5V负-5V100mA恒压WT5101A WT5101A 是一款专为 Buck 和 Buck-Boost 拓扑而设计的高效、具有成本优势的离线恒压稳压器&#xff0c;内嵌有500V MOSFET。在降低系统成本的同时&#xff0c;这款稳压器只需少量的外部元件就能输出默认的5V电压。在轻负载条件下&…
阅读更多...
Sping源码（七）—context: component-scan标签如何扫描、加载Bean

Sping源码（七）—context: component-scan标签如何扫描、加载Bean

序言 简单回顾一下。上一篇文章介绍了从xml文件context component-scan标签的加载流程到ConfigurationClassPostProcessor的创建流程。 本篇会深入了解context component-scan标签底层做了些什么。 component-scan 早期使用Spring进行开发时&#xff0c;很多时候都是注解 标…
阅读更多...
智能算法 | Matlab基于CBES融合自适应惯性权重和柯西变异的秃鹰搜索算法

智能算法 | Matlab基于CBES融合自适应惯性权重和柯西变异的秃鹰搜索算法

智能算法 | Matlab基于CBES融合自适应惯性权重和柯西变异的秃鹰搜索算法 目录 智能算法 | Matlab基于CBES融合自适应惯性权重和柯西变异的秃鹰搜索算法效果一览基本介绍程序设计参考资料效果一览 基本介绍 Matlab基于CBES融合自适应惯性权重和柯西变异的秃鹰搜索算法 融合自适应…
阅读更多...
ds18b20温度传感器驱动程序

ds18b20温度传感器驱动程序

ds18b20驱动程序 有了之前延时的方法&#xff0c;那么实现一个单总线数据传输的传感器驱动程序就非常简单了。下面我们套用杂项驱动框架来编写ds18b20驱动程序。 实现需要明确的是&#xff1a;**ds18b20驱动的本质是通过2440的gpio&#xff0c;通过给定的时序对ds18b20的读写数…
阅读更多...
【介绍下WebStorm开发插件】

【介绍下WebStorm开发插件】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站