C++数据结构与算法 目录
本文前驱课程
1 C++自学精简教程 目录(必读)
2 Vector<T> 动态数组（模板语法）
本文目标
1 熟悉迭代器设计模式；
2 实现数组的迭代器；
3 基于迭代器的容器遍历；
迭代器语法介绍
对迭代器的详细介绍参考 ： 迭代器 iterator 范围for循环 删除容器的元素 remove erase
迭代器的功能
迭代器实际上是一个内部类。通过下面的迷你代码，我们可以看到迭代器应该具备的能力。
#include <vector>
using namespace std;
int main()
{
vector<int> arr;
auto itr = arr.begin();
for (auto itr = arr.begin(); itr != arr.end()/* (3)迭代器要能够比较相等*/; itr++/* (4)迭代器要能够移动到下一个位置 */ )
{
cout << *itr/* (5)迭代器要能够解引用得到容器的元素*/ << " ";
}
return 0;
}
迭代器的实现
现在我们考虑如何实现这种能力。
对于动态数组Vector来说：
(1)开始迭代器要能指向第一个元素 m_data[0]：可以给迭代器添加一个构造函数，传递动态数组的首元素地址给迭代器。
(2)结束迭代器指向空最后一个元素的下一个位置：可以给迭代器的构造函数传入动态数组首地址偏移 m_size 个元素后的地址。m_data + m_size
(3)迭代器要能够比较相等：让迭代器重载， 等于操作符 == 不等于操作符 !=
(4)迭代器要能够移动到下一个位置：让迭代器重载自增操作符 ++
(5)迭代器要能够解引用得到容器的元素：让迭代器重载解引用操作符 *
至此，迭代器的功能就全部实现完成了。
内部类
我们会把Vector类的迭代器类型iterator定义在Vector的内部，像下面这样：
class Vector
{
public:
class iterator
{
friend class Vector;
};
};此时iterator类叫做内部类。内部类在类外部，比如main函数内访问的时候，需要加上外部类作用域才能访问到。像下面这样：
Vector::iterator itr;友元
考虑到我们一定会在main函数这样的Vector类的外部使用迭代器类型，所以iterator类一定是公开的。这就是为什么iterator类定义的前面有一个public。
但是，我们当然不希望main函数中的代码可以访问iterator类内部的细节，因为这些细节是管理Vector类内容的关键。如果这些细节暴露了，用户就可能会误用，而且也让iterator对用户来说变复杂了。用户不应该知道这些细节，也不想知道。这就说明iterator的成员是private的。
那么，既然iterator的成员是私有的，Vector也要能够方便的访问，修改怎么办呢？我们可不想让Vector修改这些细节的时候再通过iterator的get set 方法来做。太麻烦了，而且涉及到函数调用，也是不必要的开销。
所以，可以让Vector变成iterator的自己人，也就是friend 友元。这就是为何iterator内部有这么一句声明：
friend class Vector;这样以来，Vector 类的成员函数就可以直接修改 iterator的成员数据了，哪怕这些数据是iterator的private成员也一样可以无障碍直接访问。
常见的错误实现
返回临时变量的引用
临时变量超出作用域之后，就被释放了，此时引用这样的变量是未定义行为。
返回临时变量的地址
同上。
比较元素的值来来判断迭代器相等
迭代器相等，实际上就是指向相同。也就是地址相同，而不是所指向的内容一样。
如果指向的内容一样就叫迭代器相等，那么一个拥有10个元素值都是123的数组，迭代器之间岂不是都互相相等了?
对指针运算的秒处没能用上
参考：堆数组 heap array 与指针运算（C++） - 知乎
完整测试用例
// >>>>>>>>>>>>> do not care the code about memory leak checking. begin <<<<<<<<<<<<<<<
#include <iostream>
#include <cassert>
using namespace std;
struct MemoryNode{
void* ptr = 0;
bool m_released = false;
size_t byte_count = 0;
char file[100] = { 0 };
int line = -1;
bool is_array = false;
MemoryNode* next = nullptr;
};
struct MemoryList{
~MemoryList(){
bool exist_leak = false;
auto temp = head.next;
while (temp){
if (temp->m_released == false){
cout << "memory leak " << temp->byte_count << " byte(s) !!!" << endl;
exist_leak = true;
}
temp = temp->next;
}
if (!exist_leak){
cout << "OK good job ! No memory leak." << endl;
}
}
static MemoryNode* C_NewNode(void* ptr, size_t size, const char* file, int line, bool is_array){
auto pnode = (MemoryNode*)malloc(sizeof(MemoryNode));
pnode->ptr = ptr;
pnode->m_released = false;
pnode->byte_count = size;
for (char* p = pnode->file; *file != '\0'; p++, file++) {*p = *file;}
pnode->line = line;
pnode->is_array = is_array;
pnode->next = nullptr;
return pnode;
}
void push_back(MemoryNode* pnode){
if (tail == nullptr){
head.next = tail = pnode;
}else{
tail->next = pnode;
tail = tail->next;
}
++m_size;
}
MemoryNode* find(void* ptr){
auto temp = head.next;
while (temp){
if (temp->ptr == ptr){
return temp;
}
temp = temp->next;
}
return nullptr;
}
private:
int m_size = 0;
MemoryNode head;
MemoryNode* tail = nullptr;
};
static MemoryList g_MemoryList;
void* operator new(size_t size, char const* file, int line){
void* ptr = malloc(size);
auto pnode = MemoryList::C_NewNode(ptr, size, file, line, false);
g_MemoryList.push_back(pnode);
return ptr;
}
void* operator new[](std::size_t size, char const* file, int line){
void* ptr = malloc(size);
auto pnode = MemoryList::C_NewNode(ptr, size, file, line, true);
g_MemoryList.push_back(pnode);
return ptr;
}
void operator delete(void* ptr) noexcept{
if (ptr == nullptr)
{
cout << "can not delete nullptr !!!" << endl;
assert(false);
}
auto node = g_MemoryList.find(ptr);
if (node == nullptr){
cout << "you want to free memory which is not allocated from new !!!" << endl;
assert(false);
}
else
{
if (node->is_array){
cout << "momory allocated at line " << node->line << ", you want to free memory by delete not delete[] which is allocatd from new[] !!!" << endl;
assert(false);
}
if (node->m_released){
cout << "momory allocated at line " << node->line << ", you want to free one memory twice !!!" << endl;
assert(false);
}
node->m_released = true;
}
}
void operator delete(void*, std::size_t)//Ubuntu need
{
assert(false);
}
void operator delete[](void*, std::size_t)//Ubuntu need
{
assert(false);
}
void operator delete[](void* ptr) noexcept{
if (ptr == nullptr)
{
cout << "can not delete nullptr !!!" << endl;
assert(false);
}
auto node = g_MemoryList.find(ptr);
if (node == nullptr){
cout << "you want to free memory which is not allocated from new !!!" << endl;
assert(false);
}
else{
if (!node->is_array){
cout << "momory allocated at line " << node->line << ", you want to free memory by delete[] not delete which is allocatd from new !!!" << endl;
assert(false);
}
if (node->m_released){
cout << "momory allocated at line " << node->line << ", you want to free one memory twice !!!" << endl;
assert(false);
}
node->m_released = true;
}
}
void operator delete(void* pMem, const char* pszFilename, int nLine){ //msvc need
cout << (int*)pMem << pszFilename << nLine << endl;
free(pMem);
assert(false);
}
void operator delete[](void* pMem, const char* pszFilename, int nLine){ //msvc need
cout << (int*)pMem << pszFilename << nLine << endl;
free(pMem);
assert(false);
}
#define new new(__FILE__, __LINE__)
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__);
// >>>>>>>>>>>>> do not care the code about memory leak checking. begin <<<<<<<<<<<<<<<
#include <iostream>
#include <cassert>
class Vector
{
public:
Vector(void);//1 默认构造函数
Vector(int count, int value);//2 非默认构造函数
Vector(const Vector& from);//4 复制构造函数
Vector(int* start, int* end);// 3 非默认构造函数
Vector& operator = (const Vector& from);
~Vector();
public:
size_t size(void) const;
bool empty(void) const;
const int& operator[] (size_t n) const;
int& operator[] (size_t n);
void push_back(const int& val);
public:
class iterator
{
friend class Vector;
friend bool operator == (const iterator& lhs, const iterator& rhs);//用于实现!=,因为==非常容易实现
friend bool operator != (const iterator& lhs, const iterator& rhs);
public:
iterator& operator++(); //用于前置形式
iterator operator++(int); //用于后置形式，这里有个int参数纯粹是为了区分前自增操作符而加的语法规定
int& operator*();//解引用操作符重载
private:
int* m_hold = nullptr;
};
class const_iterator
{
friend class Vector;
public:
bool operator == (const const_iterator& rhs) { return this->m_hold == rhs.m_hold; }//用于实现!=,因为==非常容易实现
bool operator != (const const_iterator& rhs) { return !(*this == rhs); };
const_iterator& operator++(); //用于前置形式 ++itr 先改变自己，指向下一个位置，再返回自己
const_iterator operator++(int); //用于后置形式 itr++ 先创建一个改变前的副本用于返回，再在返回前改变自己，指向下一个位置
const int& operator*() const;
private:
const int* m_hold = nullptr;
};
//noexcept 表示这个函数内不会抛出异常，这样有助于编译器优化代码生成
const_iterator begin() const noexcept;
iterator begin() noexcept;
const_iterator end() const noexcept;
iterator end() noexcept;
private:
void clear(void);
private:
//(0) your code 请给下面的三个成员变量定义的同时初始化，这样就不用在每个构造函数里都再初始化一遍了 C++11
size_t m_size;//当前元素数量
size_t m_capacity;//容量
int* m_data;//数据部分
};
Vector::Vector(void)
{
std::cout << "Vector()" << std::endl;
}
Vector::Vector(const Vector& from)
{
if (from.empty())
{
m_data = nullptr;
m_size = 0;
m_capacity = 0;
return;
}
m_capacity = m_size = from.m_size;
m_data = new int[m_size];
for (size_t i = 0; i < m_size; ++i)
{
m_data[i] = from.m_data[i];
}
std::cout << "Vector(const Vector & from)" << std::endl;
}
Vector::Vector(int count, int value)
: m_data(nullptr)
{
if (count <= 0)
{
throw std::runtime_error("size of vector to init must bigger than zero!");
}
m_data = new int[count];
for (int i = 0; i < count; i++)
{
m_data[i] = value;
}
m_capacity = m_size = count;
std::cout << "Vector(const, value)" << std::endl;
}
Vector::Vector(int* start, int* end)
{
check(start != nullptr && end != nullptr);
m_capacity = m_size = ((size_t)end - (size_t)start) / sizeof(int);//这里如果用int来存放可能会盛不下，size_t可以保证盛放的下
check(m_size > 0);
m_data = new int[m_size];
for (size_t i = 0; i < m_size; i++)
{
m_data[i] = *start++;
}
std::cout << "Vector(start, end)" << std::endl;
}
Vector& Vector::operator=(const Vector& from)
{
if (this == &from)
{
return *this;
}
//先释放自己的数据
clear();
m_size = from.m_size;
m_capacity = from.m_capacity;
m_data = new int[m_size];
for (size_t i = 0; i < m_size; i++)
{
m_data[i] = from.m_data[i];
}
return *this;
}
Vector::~Vector()
{
if (m_data)
{
delete[] m_data;
}
std::cout << "~Vector()" << std::endl;
}
size_t Vector::size(void) const
{
return m_size;
}
bool Vector::empty(void) const
{
return m_size == 0;
}
const int& Vector::operator[](size_t n) const
{
return m_data[n];
}
int& Vector::operator[](size_t n)
{
return m_data[n];
}
void Vector::push_back(const int& val)
{
if (m_capacity > m_size)//直接追加到最后一个
{
m_data[m_size++] = val;
}
else//只有满了的那一瞬间，才翻倍开辟新空间
{
auto pNewArray = new int[m_capacity = m_capacity + m_capacity];
//拷贝老数据
for (size_t i = 0; i < m_size; i++)
{
pNewArray[i] = m_data[i];
}
//追加最新的末尾元素
pNewArray[m_size++] = val;
delete[] m_data;
m_data = pNewArray;
}
}
//下面的代码 函数名是 Vector::begin
// 返回值类型是 Vector::const_iterator
//返回值类型之所以要加类作用域是因为，返回值类型在函数作用域之外。这是由C语言继承而来的
Vector::const_iterator Vector::begin() const noexcept
{
if (empty())
{
return end();
}
const_iterator itr;
//(1) your code 下面的代码仅仅是让编译通过，可能需要你重新实现。如需修改itr的成员，考虑到Vector是iterator类的友元，可以直接修改。
return itr;
}
Vector::iterator Vector::begin() noexcept
{
if (empty())
{
return end();
}
iterator itr;
//(1) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
return itr;
}
Vector::const_iterator Vector::end() const noexcept
{
const_iterator itr;
//(2) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
// 如果容器为空，不能返回下标返回的元素位置
return itr;
}
Vector::iterator Vector::end() noexcept
{
iterator itr;
//(2) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
// 如果容器为空，不能返回下标返回的元素位置
return itr;
}
void Vector::clear(void)
{
//(3) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
}
bool operator==(const Vector::iterator& lhs, const Vector::iterator& rhs)
{
//(4) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
cout << "test code " << lhs.m_hold << ", test code " << rhs.m_hold << endl;//请删除这行代码
return false;
}
bool operator!=(const Vector::iterator& lhs, const Vector::iterator& rhs)
{
//(5) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
cout << "test code " << lhs.m_hold << ", test code " << rhs.m_hold << endl;//请删除这行代码
return false;
}
Vector::iterator& Vector::iterator::operator++()
{
//(6) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
return *this;
}
Vector::const_iterator& Vector::const_iterator::operator++()
{
//(7) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
return *this;
}
Vector::iterator Vector::iterator::operator++(int)
{
//(8) your code 下面的代码仅仅是让编译通过，可能需要你重新实现
return iterator();
}
Vector::const_iterator Vector::const_iterator::operator++(int)
{
return Vector::const_iterator();
}
int& Vector::iterator::operator*()
{
//(9) your code 下面的代码是错误的！不可以返回临时变量的引用！仅仅是让编译通过，需要你重新实现
static int a = 0;//请删除这行代码
return a;
}
const int& Vector::const_iterator::operator*() const
{
//(9) your code 下面的代码是错误的！不可以返回临时变量的引用！仅仅是让编译通过，需要你重新实现
static int a = 0;//请删除这行代码
return a;
}
void print(const Vector& v, const char* msg)
{
std::cout << "print The contents of " << msg << " are:";
for (size_t i = 0; i < v.size(); ++i)
{
std::cout << ' ' << v[i];
}
std::cout << '\n';
}
void print_itr(Vector& v, const char* msg)
{
std::cout << "print_itr The contents of " << msg << " are:";
for (auto itr = v.begin(); itr != v.end(); ++itr)
{
std::cout << ' ' << *itr;
}
std::cout << '\n';
}
void print_const_itr(const Vector& v, const char* msg)
{
std::cout << "print_const_itr The contents of " << msg << " are:";
for (auto itr = v.begin(); itr != v.end(); ++itr)
{
//*itr = 4;
std::cout << ' ' << *itr;
}
std::cout << '\n';
}
int main()
{
Vector a;
Vector first; // empty vector of ints
check(first.empty() == true && first.size() == 0);
Vector second(4, 100); // four ints with value 100
check(second.empty() == false);
check(second.size() == 4);
check(*second.begin() == 100);
Vector fourth(second); // a copy of third
check(fourth.size() == second.size());
int myints[] = { 16,2,77,29 };
Vector 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
Vector a1(myints, myints + sizeof(myints) / sizeof(int));
{
Vector b(a1);
b.push_back(2);
check(b[4] == 2);
}
{
Vector c;
for (auto i : c)
{
std::cout << i << " ";
}
c = a1;
a1 = c;
c = a1;
for (auto i : c)
{
std::cout << i << " ";
}
std::cout << std::endl;
}
check(a1.size() == sizeof(myints) / sizeof(int));
{
Vector c;
c = fifth;
c[0] = 1;
check(c[0] == 1);
}
}期待输出：文章来源：https://www.toymoban.com/news/detail-689958.html
Vector()
Vector()
line:460 Pass
Vector(const, value)
line:462 Pass
line:463 Pass
line:464 Pass
Vector(const Vector & from)
line:466 Pass
line:244 Pass
line:246 Pass
Vector(start, end)
line:470 Pass
line:471 Pass
line:472 Pass
line:473 Pass
print The contents of fifth are: 16 2 77 29
line:476 Pass
line:477 Pass
print The contents of fifth are: 16 2 77 29 30
line:479 Pass
print The contents of first are: 16 2 77 29 30
line:482 Pass
print_itr The contents of fifth are: 16 2 77 29 30
print_const_itr The contents of fifth are: 16 2 77 29 30
line:244 Pass
line:246 Pass
Vector(start, end)
Vector(const Vector & from)
line:489 Pass
~Vector()
Vector()
16 2 77 29
~Vector()
line:507 Pass
Vector()
line:512 Pass
~Vector()
~Vector()
~Vector()
~Vector()
~Vector()
~Vector()
~Vector()
OK good job ! No memory leak.祝你好运！文章来源地址https://www.toymoban.com/news/detail-689958.html
到了这里，关于2.3 Vector 动态数组（迭代器）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
