首页 > 其他分享 >vector的扩容机制实现

vector的扩容机制实现

时间:2023-03-23 16:12:14浏览次数:47  
标签:扩容 std last String vector const 机制 include first

在做C++ primer的课后题时,有一道为自己写的类定义拷贝控制操作,之后定义一个vector 进行push_back并观察vector的capacity。通过查资料了解到vector当达到扩容要求时,会将所有的旧元素移动到新的位置,所以我以为总共会移动n个元素,但通过打印发现每次只移动了n-1次。源代码如下

h.h

#ifndef STRVEC_H_
#define STRVEC_H_

#include <iostream>
#include <stdio.h>
#include <string>
#include <memory>
#include <algorithm>
#include <initializer_list>
#include <memory>
#include <vector>
#include <stdexcept>
#include <fstream>
#include <sstream>
#include <set>
#include <map>

using std::cout;
using std::endl;

class String
{
public:
    String() :first_c(nullptr), last_c(nullptr) {};
    String(const char* chr);
    String(const String& s);
    String(String&& s) noexcept;//移动构造函数
    String& operator=(const String& s);
    String& operator=(String&& s) noexcept;
    char* begin() const { return first_c; }
    char* end() const { return last_c; }
    char* c_str() { return first_c; }
    ~String();
private:
    std::allocator<char> alloc;
    std::pair<char*, char*>alloc_n_copy(const String& s);
    void free();
    char* first_c;
    char* last_c;
};

String::String(const char* chr)
{
    auto len = strlen(chr) + 1;
    auto beg = alloc.allocate(len);
    first_c = beg;
    last_c = beg + len;
    memcpy(first_c, chr, len);
    printf("默认构造函数\n");
}

String::String(const String& s)
{
    auto p = alloc_n_copy(s);
    first_c = p.first;
    last_c = p.second;
    std::cout << "拷贝构造函数" << std::endl;
}

String::String(String&& s) noexcept :
    alloc(std::move(s.alloc)), first_c(std::move(s.first_c)), last_c(std::move(s.last_c))
{
    printf("%s 移动构造函数\n", first_c);
    s.first_c = nullptr;   s.last_c = nullptr;
}


String::~String()
{
    free();
}

std::pair<char*, char*> String::alloc_n_copy(const String& s)
{
    auto data = alloc.allocate(s.last_c - s.first_c);
    return { data, std::uninitialized_copy(s.first_c, s.last_c, data) };
}

String& String::operator=(const String& s)
{
    auto tmp = alloc_n_copy(s);
    free();
    first_c = tmp.first;
    last_c = tmp.second;
    printf("拷贝赋值运算符\n");
    return *this;
}

String& String::operator=(String&& s) noexcept
{
    if (this != &s)
    {
        free();
        alloc = std::move(s.alloc);
        first_c = std::move(s.first_c);
        last_c = std::move(s.last_c);
        s.first_c = nullptr; s.last_c = nullptr;
        printf("移动赋值运算符");
    }
    return *this;
}

void String::free()
{
    if (first_c)
    {
        std::for_each(first_c, last_c, [this](char& cp) { alloc.destroy(&cp); });
        alloc.deallocate(first_c, last_c - first_c);
    }
}

#endif

c.cpp

#include"h.h"

int main()
{
	std::vector<String> vec;
	String a = "aaaa";
	printf("%d\n", vec.capacity());
	vec.push_back(a);
	printf("%d\n", vec.capacity());
	vec.push_back("bbbb");
	printf("%d\n", vec.capacity());
	vec.push_back("bbbb");
	printf("%d\n", vec.capacity());
	return 0;
}

打印结果

发现vs 2019,当判断需要扩容的时候,会先将新写入的元素直接放在新的内存位置,然后在把旧元素移动构造 从头到尾移动到新的位置

但是并不知道为什么需要这样的实现,为什么不能直接从头开始移动构造转移

标签:扩容,std,last,String,vector,const,机制,include,first
From: https://www.cnblogs.com/lihaoxiang/p/17247846.html

相关文章

  • Python中的重试机制
    ====引用自https://www.jb51.net/article/254886.htm(一文详解Python中的重试机制)这里要给大家介绍的是一个第三方库-Tenacity(标题中的重试机制并并不准确,它不是Python......
  • 为什么OS已经有了页面置换机制,MySQL中的Buffer Pool还需要再实现一遍?
    问题引入舍友最近在找实习,简历上有CMU15-445经典数据库项目。在面试时被问到:操作系统已经有页面置换算法,为什么BufferPool中还需要自己实现呢?操作系统中的页面置换......
  • SAP生产订单组件库位能否下单时自动带出的处理机制
    参考自:https://blog.csdn.net/lj663/article/details/106056754SAP企业做生产入库时,通常需要在成品入库的同时去反冲成品下级原材料消耗。但原材料消耗需要确定归属,从哪个......
  • vector
    1、emplace1)emplace(pos,args):在某个迭代器位置插入(构建)一个新对象std::vector<int>myvector={10,20,30};//->10,100,20,30autoit=myvector.emplace(myvec......
  • vector与mat互转
    一、Mat转vector1、生成1xN的vector对象1)Mat对象直接转换成vector对象(1)主要是将Mat对象转换为单通道、单行的Mat对象!然后就可以直接转换成vector对象Matsrc=imread(......
  • 无线自组网AODV路由机制matlab仿真
    1.算法描述无线自组网按需平面距离向量路由协议(AdhocOn-DemandDistanceVectorRouting,AODV)是应用于无线随意网络(也称作无线Adhoc网络)中进行路由选择的路由协议,它能够......
  • 无线自组网AODV路由机制matlab仿真
    1.算法描述       无线自组网按需平面距离向量路由协议(AdhocOn-DemandDistanceVectorRouting,AODV)是应用于无线随意网络(也称作无线Adhoc网络)中进行路由选择的......
  • UI自动化alter框 、等待机制
    一、下拉框处理:网页上的js弹出框一般有三种情况,且识别不了元素,需要使用switch_to.alert()进行跳转    情况一: 这时候需要先跳转到此弹窗,才能做到自动化点击确......
  • Java SPI机制详解
    一、什么是SPI机制1、SPI(ServiceProviderInterface),是JDK内置的一种服务提供发现机制,可以用来启用框架扩展和替换组件,主要被框架的开发人员使用,比如Java.sql.Driver接口......
  • JVM类加载机制
    JVM的类加载分为5个阶段:加载、验证、准备、解析和初始化。在类初始化完成后可以使用该类的信息,在一个类不再被需要时可以从JVM中卸载1.加载指JVM读取Class文件,并根据Cla......