2.4 Vector＜T＞ 动态数组（随机访问迭代器）

C++自学精简教程 目录(必读)

该 Vector 版本特点

这里的版本主要是使用模板实现、支持随机访问迭代器，支持std::sort等所有STL算法。(本文对随机迭代器的支持参考了 复旦大学 大一公共基础课C++语言的一次作业)

随机访问迭代器的实现主要是继承std::iterator<std::random_access_iterator_tag, T>来实现的。

随机访问迭代器最牛逼的两个接口是：

friend iterator operator+(const iterator& lhs, size_t n);

friend iterator operator-(const iterator& lhs, size_t n);

问题解答

1 为何下面代码中的iterator是struct而不是class？

答：参考struct与class

题目代码

头文件 Vector.h ：

#ifndef VEC_H
#define VEC_H
#include <iostream>
#include <cassert>
#include <initializer_list>
//------下面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------
#include <algorithm>
#include <cstdlib>
#include <iostream> 
#include <vector>
#include <utility>
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i = 0; while ((location[i] = location1[i]) && i < 100) { ++i; } }void* ptr; size_t count; char location[100] = { 0 }; int line; bool is_array = false; bool not_use_right_delete = false; }; bool operator==(const Record& lhs, const Record& rhs) { return lhs.ptr == rhs.ptr; }std::vector<Record> myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr = std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{return newFunctionImpl(sz, file, line, true);
}void operator delete(void* ptr) noexcept { Record item{ ptr, 0, "", 0, false }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept { Record item{ ptr, 0, "", 0, true }; auto itr = std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr != myAllocStatistic.end()) { auto ind = std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr = nullptr; if (!itr->is_array) { myAllocStatistic[ind].not_use_right_delete = true; } else { myAllocStatistic[ind].count = 0; }std::free(ptr); } }
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout << "Memory leak report: " << std::endl; bool leak = false; for (auto& i : myAllocStatistic) { if (i.count != 0) { leak = true; std::cout << "leak count " << i.count << " Byte" << ", file " << i.location << ", line " << i.line; if (i.not_use_right_delete) { cout << ", not use right delete. "; }	cout << std::endl; } }if (!leak) { cout << "No memory leak." << endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line = __LINE__) { if (b) { cout << "line:" << line << " Pass" << endl; } else { cout << "line:" << line << " Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!!" << " " << endl; exit(0); } }
#define check(msg)  check_do(msg, __LINE__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码，你无需关注------template<typename T>
class Vector
{
public:/* 提供默认构造函数， 否则只能使用有参版本，这会带来不变例如，Vector<int> arr; 这样会报错，因为需要默认构造函数*/Vector(void);//如果类提供了非默认构造函数，编译器不会自动提供默认构造函数Vector(const Vector& from);// 复制构造函数Vector(T* start, T* end);//  非默认构造函数Vector(int count, int value);//2 非默认构造函数Vector(std::initializer_list<T> value_array){for (auto& item : value_array){push_back(item);}}Vector& operator = (const Vector& from);bool operator==(const Vector& other) const{//(1) your codereturn false;}//赋值操作符~Vector();//析构函数
public:size_t size(void) const;bool empty(void) const;T& operator[] (size_t n) const;T& operator[] (size_t n);void push_back(const T& val);void clear(void);
private:void deep_copy_from(const Vector<T>& from);public:struct iterator : std::iterator<std::random_access_iterator_tag, T>{friend class  Vector;friend bool operator == (const iterator& lhs, const iterator& rhs) { return lhs.m_hold == rhs.m_hold; }friend bool operator != (const iterator& lhs, const iterator& rhs) { return !(lhs == rhs); }friend size_t operator - (const iterator& lhs, const iterator& rhs) { return lhs.m_hold - rhs.m_hold; }friend bool operator < (const iterator& lhs, const iterator& rhs) { return lhs.m_hold < rhs.m_hold; }friend bool operator > (const iterator& lhs, const iterator& rhs) { return lhs.m_hold > rhs.m_hold; }friend bool operator <= (const iterator& lhs, const iterator& rhs) { return !(lhs > rhs); }friend bool operator >= (const iterator& lhs, const iterator& rhs) { return !(lhs < rhs); }friend iterator operator + (const iterator& lhs, size_t n) { iterator itr; itr.m_hold = lhs.m_hold + n; return itr; }//随机访问迭代器牛逼的地方friend iterator operator - (const iterator& lhs, size_t n) { iterator itr; itr.m_hold = lhs.m_hold - n; return itr; }//随机访问迭代器牛逼的地方public://用于前置形式iterator& operator++() { m_hold = m_hold + 1; return *this; };iterator& operator--() { m_hold = m_hold - 1; return *this; };//用于后置形式iterator operator++(int) { iterator itr = *this; m_hold += 1; return itr; }iterator operator--(int) { iterator itr = *this; m_hold -= 1; return itr; }T& operator*() const//这里必须是const in C++14{return *m_hold;}private:T* m_hold;};struct const_iterator : std::iterator<std::random_access_iterator_tag, T>{friend class  Vector;friend bool operator == (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold == rhs.m_hold; }friend bool operator != (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs == rhs); }friend size_t operator - (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold - rhs.m_hold; }friend bool operator < (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold < rhs.m_hold; }friend bool operator > (const const_iterator& lhs, const const_iterator& rhs) { return lhs.m_hold > rhs.m_hold; }friend bool operator <= (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs > rhs); }friend bool operator >= (const const_iterator& lhs, const const_iterator& rhs) { return !(lhs < rhs); }friend const_iterator operator + (const const_iterator& lhs, size_t n) { const_iterator itr; itr.m_hold = lhs.m_hold + n; return itr; }//随机访问迭代器牛逼的地方friend const_iterator operator - (const const_iterator& lhs, size_t n) { const_iterator itr; itr.m_hold = lhs.m_hold - n; return itr; }//随机访问迭代器牛逼的地方public://用于前置形式const_iterator& operator++() { m_hold = m_hold + 1; return *this; };const_iterator& operator--() { m_hold = m_hold - 1; return *this; };//用于后置形式const_iterator operator++(int) { const_iterator itr = *this; m_hold += 1; return itr; }const_iterator operator--(int) { const_iterator itr = *this; m_hold -= 1; return itr; }const T& operator*() const{return *m_hold;}private:T* m_hold;};iterator begin() noexcept{iterator itr;itr.m_hold = empty() ? nullptr : &m_data[0];return itr;}const_iterator cbegin() const noexcept;iterator end() noexcept{iterator itr;itr.m_hold = empty() ? nullptr : &m_data[m_size];return itr;}const_iterator cend() const noexcept;
private:size_t m_size = 0;//当前元素数量size_t m_capacity = 0;//容量T* m_data = nullptr;//数据部分
};template<typename T>
Vector<T>::Vector(void)
{
}template<typename T>
Vector<T>::Vector(T * start, T * end)
{std::cout << "Vector(T* start, T* end)" << std::endl;assert(start != nullptr && end != nullptr);m_capacity = m_size = ((size_t)end - (size_t)start)/sizeof(T);//这里如果用int来存放可能会盛不下，size_t可以保证盛放的下assert(m_size > 0);m_data = new T[m_size];for (size_t i = 0; i < m_size; i++){m_data[i] = *start++;}
}
template<typename T>
Vector<T>::Vector(int count, int value)
{std::cout << "Vector(count, value)" << std::endl;if (count <= 0){throw std::runtime_error("size of vector to init must bigger than zero!");}m_data = new T[count];for (size_t i = 0; i < count; i++){m_data[i] = value;}m_capacity = m_size = count;
}
template<typename T>
Vector<T>& Vector<T>::operator=(const Vector<T>& from)
{std::cout << "Vector::operator=" << std::endl;if (this == &from){return *this;}//先释放自己的数据clear();deep_copy_from(from);return *this;
}template<typename T>
Vector<T>::~Vector()
{//(2) your code}
template<typename T>
size_t Vector<T>::size(void) const
{return m_size;
}
template<typename T>
bool Vector<T>::empty(void) const
{//(3) your codereturn false;//此处需要修改。
}
template<typename T>
T& Vector<T>::operator[](size_t n) const
{//(4) your codestatic T t;//此处需要修改。return t;//此处需要修改。
}
template<typename T>
T& Vector<T>::operator[](size_t n)
{//(4) your codestatic T t;//此处需要修改。return t;//此处需要修改。
}
template<typename T>
void Vector<T>::push_back(const T & val)
{//(5) your code// 这里需要考虑第一次插入数据的时候还没有开辟任何动态空间的情况，因为构造函数不再负责事先开辟好少量的初始预留空间了   
}template<typename T>
void Vector<T>::clear(void)
{//(6) your code
}template<typename T>
void Vector<T>::deep_copy_from(const Vector<T>& from)
{//(7) your code}template<typename T>
Vector<T>::Vector(const Vector& from)
{//(8) your code}template<typename T>
typename Vector<T>::const_iterator Vector<T>::cend() const noexcept
{Vector<T>::const_iterator itr;//(9) your codereturn itr;
}template<typename T>
typename Vector<T>::const_iterator Vector<T>::cbegin() const noexcept
{const_iterator itr;//(10) your codereturn itr;
}#endif

测试代码main.cpp：

#include <iostream>
#include <algorithm>
#include "Vector.h"
#include <vector>template<typename T>
void print(const Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (int i = 0; i < v.size(); ++i){std::cout << ' ' << v[i];}std::cout << '\n';
}
template<typename T>
void print_itr(Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (auto itr = v.begin(); itr != v.end(); ++itr){std::cout << ' ' << *itr;}std::cout << '\n';
}
template<typename T>
void print_const_itr(const Vector<T>& v, const std::string& msg)
{std::cout << "The contents of " << msg.c_str() << " are:";for (auto itr = v.cbegin(); itr != v.cend(); ++itr){std::cout << ' ' << *itr;}std::cout << '\n';
}int main()
{Vector<int> a;Vector<int> first;                   // empty vector of intscheck(first.empty() == true && first.size() == 0);Vector<int> second(4, 100);                       // four ints with value 100check(second.empty() == false);check(second.size() == 4);check(*second.begin() == 100);Vector<int> fourth(second);                       // a copy of thirdcheck(fourth.size() == second.size());int myints[] = { 16,2,77,29 };Vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));check(fifth.empty() == false);check(fifth[0] == 16);check(fifth[3] == 29);check(fifth.size() == sizeof(myints) / sizeof(int));print(fifth, "fifth");//The contents of fifth are:16 2 77 29 fifth.push_back(30);check(fifth[4] == 30);check(fifth.size() == 5);print(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 check(fifth.size() == sizeof(myints) / sizeof(int) + 1);first = fifth = fifth;print(first, "first");//The contents of first are:16 2 77 29 30 check(first.empty() == false && first.size() == fifth.size());print_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 print_const_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 std::sort(fifth.begin(), fifth.end());std::cout << "fifith after sort:" << std::endl;print_const_itr(fifth, "fifth");//The contents of fifth are:16 2 77 29 30 Vector<int> a1(myints, myints + sizeof(myints) / sizeof(int));{Vector<int> b(a1);b.push_back(2);check(b[4] == 2);auto result = (b == Vector<int>{ 16, 2, 77, 29, 2});check(result);//iteratorcheck(b.begin() + b.size() == b.end());auto begin = b.begin();auto itr = b.begin() + 1;check(*begin == 16);check(*itr == 2);}{Vector<int> b{ 1,3,5,7 };b.push_back(9);}{Vector<int> c;for (auto i : c){std::cout << i << " ";}c = a1;for (auto i : c){std::cout << i << " ";}std::cout << std::endl;}check(a1.size() == sizeof(myints) / sizeof(int));{Vector<int> c;c = fifth;c[0] = 1;check(c[0] == 1);}
}

预期输出

line:42 Pass
Vector(count, value)
line:44 Pass
line:45 Pass
line:46 Pass
line:48 Pass
Vector(T* start, T* end)
line:52 Pass
line:53 Pass
line:54 Pass
line:55 Pass
The contents of fifth are: 16 2 77 29
line:58 Pass
line:59 Pass
The contents of fifth are: 16 2 77 29 30
line:61 Pass
Vector::operator=
Vector::operator=
The contents of first are: 16 2 77 29 30
line:64 Pass
The contents of fifth are: 16 2 77 29 30
The contents of fifth are: 16 2 77 29 30
fifith after sort:
The contents of fifth are: 2 16 29 30 77
Vector(T* start, T* end)
line:74 Pass
line:76 Pass
Vector::operator=
16 2 77 29
line:95 Pass
Vector::operator=
line:100 Pass
Memory leak report:
No memory leak.