一、前言
在另一篇博客中我已經寫了：vector容器介紹和使用以及迭代器失效問題，那么在這篇博客中我將要模擬實作一個簡單的vector，對vector實作基本的增、刪、改，
下圖是vector的基本結構：
二、vector的成員、構造、析構、迭代器的基本實作
#pragma once
#include<iostream>
#include<assert.h>
namespace Myvector{
template<class T>
class vector {
public:
//因為vector的底層是連續的，所以可以使用原生指標來當作迭代器使用
typedef T* iterator;
typedef const T* const_iterator; //const參考const迭代器
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const{
return _start;
}
const_iterator end() const{
return _finish;
}
//當前vector元素的有效個數
size_t size(){
return _finish - _start;
}
//當前vector容器的個數
size_t capacity() {
return end_of_storage - _start;
}
//建構式，構造一個空的vector
vector():
_start(nullptr),_finish(nullptr),end_of_storage(nullptr)
{}
//vector的解構式
~vector() {
delete[]_start;
_start = _finish = end_of_storage = nullptr;
}
private:
iterator _start;
iterator _finish;
iterator end_of_storage;
}
}
三、check_capacity、reserve方法
3.1 check_capacity判斷是否達到擴容條件
void check_capacity() {
if (_finish == end_of_storage) {
size_t newcapacity = capacity() == 0 ? 1 : 2 * capacity();//當最初的時候，容量為0，要給個初始值
reserve(newcapacity);
}
}
3.2 reserve實作重新配置、元素移動、釋放原空間
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size(); //保存原有vector的大小
T* tmp = new T[n]; //重新配置新空間
// memcpy(tmp,_start,sizeof(T)*size()); 出現深淺拷貝問題
for(size_t i=0;i<sz;i++){
tmp[i] = _start[i];
}
delete[] _start; //釋放原空間
//將vector的指標指向新配置的空間
_start = tmp;
_finish = _start + sz;
end_of_storage = _start + n;
}
}
4.1 分析使用memcpy進行拷貝會出現什么問題
int main()
{
Myvector::vector<string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
問題分析：
■ 1、memcpy是記憶體的二進制格式拷貝，將一段記憶體空間中內容原封不動的拷貝到另外一段記憶體空間中，
■ 2、如果拷貝的是自定義型別的元素，memcpy高效又不會出錯，但如果拷貝的是自定義型別元素，并且自定義型別中涉及到資源管理，就會出錯，因為memcpy的拷貝實際是淺拷貝，當釋放掉原來的空間時，那么我們重新分配的空間將指向野指標，
結論：如果物件中涉及到資源管理時，千萬不能使用memcpy進行物件之間的拷貝，因為memcpy是淺拷貝，否則可能會引起記憶體泄漏甚至程式崩潰，
四、resize方法
void resize(size_t n,const T& val=T()) {
if(n>capacity()){
reserve(n); //第二種情況，要先進行擴容
}
if(n<size()){ //第一種情況，n<size,直接將_finish=n+_start
_finish=n+_start;
}else{
while(_finish!=_start+n){
*_finish=val;
++_finish;
}
}
}
五、insert、push_back 增方法
void push_back(const T& val){
check_capacity();
*_finish=val;
++_finish;
}
iterator insert(iterator pos,const T& val){
assert(pos>=_start&&pos<=_finish); pos==_finish時在vector的末尾插入
size_t gap=pos-_start;//為了重新計算pos的位置，所以需要保存距離
check_capacity();
pos=_start+gap; //如果發生了擴容需要重新計算pos迭代器的位置
iterator end=_finish-1; //計算最后一個元素
while(end>=pos){ //將pos迭代器以及以后的元素依次往后移動
*(end+1)=*end;
--end;
}
*pos=val;
++_finish;
return pos;
}
六、erase、pop_back刪方法
iterator erase(iterator pos){
assert(pos>=_start&&pos<_finish); //pos不能等于_finish
iterator it=pos+1;
while(it!=_finish){
*(it-1)=*it;
--it;
}
--_finish;
return pos;
}
void pop_back(){
assert(_finish>_start);
--_finish;
}
七、operator[] 改方法
T& operator[](size_t pos){
assert(pos<size());
return _start[pos];
}
八、拷貝構造、賦值運算子多載
void swap(vector<T> &v){
std::swap(_start,v._start);
std::swap(_finish,v._finish);
std::swap(end_of_storage,v.end_of_storage);
}
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;
}
}
vector<T>& operator=(vector<T> v){ //現代寫法
swap(v);
return *this;
}
vector(const vector<T> &val)
:_start(nullptr),_finish(nullptr),end_of_storage(nullptr)
{
vector<T> tmp(val.begin(),val.end());
swap(tmp);
}
九、整合代碼
#pragma once
#include<assert.h>
namespace Myvector {
template<class T>
class vector {
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator begin() const{
return _start;
}
const_iterator end() const{
return _finish;
}
size_t size(){
return _finish - _start;
}
size_t capacity() {
return end_of_storage - _start;
}
vector():
_start(nullptr),
_finish(nullptr),
end_of_storage(nullptr)
{}
void swap(vector<T> &v) {
std::swap(_start,v._start);
std::swap(_finish, v._finish);
std::swap(end_of_storage, v.end_of_storage);
}
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;
}
}
vector(const vector<T>& val) :
_start(nullptr), _finish(nullptr), end_of_storage(nullptr)
{
vector<T> tmp(val.begin(), val.end());
swap(tmp);
}
vector<T>& operator=(vector<T> v) {
swap(v);
return *this;
}
~vector() {
delete[]_start;
_start = _finish = end_of_storage = nullptr;
}
void resize(size_t n,const T& val=T()) {
if (n > capacity()) {
reserve(n);
}
if (n<size()) {
_finish = _start+n;
}
else {
while (_finish != _start + n) {
*_finish = val;
++_finish;
}
}
}
void reserve(size_t n) {
if (n > capacity()) {
size_t sz = size();
T* tmp = new T[n];
//memcpy(tmp,_start,sizeof(T)*size()); //出現深淺拷貝問題
for (size_t i = 0; i < sz; i++) {
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = _start + sz;
end_of_storage = _start + n;
}
}
void check_capacity() {
if (_finish == end_of_storage) {
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
}
}
void push_back(const T&val) {
check_capacity();
*_finish = val;
++_finish;
}
iterator insert(iterator pos,const T& val) {
assert(pos>=_start&&_finish>=pos);
size_t posi = pos - _start;
check_capacity();
pos = _start + posi;
iterator end = _finish;
while (end >= pos) {
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
void pop_back() {
assert(_finish > _start);
--_finish;
}
iterator erase(iterator pos) {
assert(pos>=_start&&pos<_finish);
iterator it = pos + 1;
while (it != _finish) {
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
private:
iterator _start;
iterator _finish;
iterator end_of_storage;
};
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/281313.html
標籤：其他