1.sort
在里面有一个专门的排序接口sort
我们只需要传入起止位置的迭代器就可以了,注意对于所有“传起止位置的迭代器”都遵循左闭右开原则,后一个迭代器一定指向的是要排序的末尾元素的下一个位置,不要搞混了。
除此之外我们还能注意到sort存在第三个参数Compare,这是仿函数,仿函数不是函数,而是一个对象,但它通过运算符重载(operator())使其有着类似函数的用法。
下面来看一段代码:
#include
#include
#include
using namespace std;
int main()
{
vector v;
v.push_back(5);
v.push_back(3);
v.push_back(4);
v.push_back(1);
v.push_back(0);
v.push_back(2);
sort(v.begin(), v.end());
for (auto& e : v)
{
cout << e;
}
cout << endl;
sort(v.begin(), v.end(), greater());
for (auto& e : v)
{
cout << e;
}
return 0;
}
运行结果:
我们发现,默认情况下,排序默认排成升序,在第三个参数带上仿函数之后就会排成降序。
仿函数的基本用法:
在用法上,仿函数确实跟函数很相似,但是我们要清楚它的本质是一个自定义类型。
很多人在这里会表示疑问:为什么一定要传仿函数才能够区分升降序,难道不能通过begin和rbegin来区分吗?
事实上,sort是一个模板函数,只要你传的两个迭代器是同一类型,模板函数都能实例化。但是模板函数不能辨别你传的迭代器是正向的还是反向的,因此必须强制引入第三个参数来区分。
2.vector模拟实现
链表适合插入,vector适合尾插尾删,下标操作。
和string类似,vector的核心接口就是insert、erase。实现这两个接口前我们还需要实现如扩容,size,capacity等函数接口,我们只需见招拆招就行,不必去记到底要先写哪些函数。模板声明定义放到一个文件。下面分段讲解:
(1)reserve
是,这个函数控制扩容的,如果_size == _capacity的时候,就需要扩容。当然,_size和_capacity需要单独实现。
size_t size() const
{
return _finish - _start;//有效数据大小
}
size_t capacity() const
{
return _end_of_storage - _start;//总开辟空间
}
扩容要注意_finish的更新要依靠oldsize进行,因为扩容后_start指向了新的位置,而_finish指向的旧空间,两者相减得到的不是size,因此需要在扩容前保存size
void reserve(size_t n)
{
if (n <= capacity())//一律不缩容
return;
size_t oldsize = size();
T* tmp = new T[n];
if (_start)
{
for (size_t count = 0; count + begin() < end(); count++)//将原空间数据移到新的存储空间
{
tmp[count] = *(count + begin());//如果T是类,这里调用对应的拷贝构造
}
delete[] _start;//不能用memmove,当析构_start时如果类里面有指向堆区的指针,那么memmove后的类中就会出现指向已被释放的指针
}
_start = tmp;
_finish = _start + oldsize;
_end_of_storage = _start + n;
}
(2)insert
在实现reserve后,我们就可以实现insert了。
_start首位置,_finish存储位置的下一个位置,_end_of_storage开辟空间的最后一个下标下一个
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
首先我们注意知道成员变量的类型都是iterator,按语法来说iterator不能进行大小比较,相加相减操作,这里是因为iterator本质是T*才可以直接进行这些操作的。
iterator insert(iterator pos, size_t n, const T& val)
{
assert(pos - _start >= 0 && pos - _finish = _end_of_storage - _start)//预计算空间,如果不够,则扩容
reserve((capacity() + n) * 2);
iterator newpos = oldpos + _start;//更新新的位置迭代器,原来的pos可能失效
for (iterator curpos = _finish + n - 1; curpos - _start >= newpos + n - _start; curpos--)//从pos开始将数据向后移动n个元素
{
*curpos = *(curpos - n);
}
for (size_t count = 0; count < n; count++)
{
*(newpos + count) = val;
}
_finish += n;
return newpos;
}
需要注意的如何移动数据,以及这里的pos都是指的迭代器而不是下标
这里涉及迭代器失效的一种形式:野指针。
当开辟空间后,_start首位置,_finish存储位置的下一个位置,_end_of_storage都更新了,pos迭代器也要去更新,insert、erase都存在这种可能,所以统一规定只要调用了相关函数,迭代器就会失效,就算这个时候它没有越界。
(3)erase
由于上面的insert的数据移动有些混乱,迭代器和下标混在了一起,所以这里我使用了两个函数将使用到的迭代器全部转换成下标。
size_t GetPos(const_iterator it)
{
return it - _start;
}
size_t GetPos(iterator it)
{
return it - _start;
}
注意控制边界的下标,防止出现越界
iterator erase(iterator first, iterator last)
{
assert(first - _start >= 0 && first - _finish = 0 && last - _finish = first - _start);//三个assert规范参数
size_t firstpos = GetPos(first);
size_t lastpos = GetPos(last);
size_t len = lastpos - firstpos;
for (size_t count = lastpos; count < GetPos(_finish); count++)
{
_start[count - len] = _start[count];
}
_finish -= len;
return first;//返回清除数据后的第一个位置迭代器
}
(4)构造函数
当我们实现了一个构造函数后(包括拷贝构造),编译器就默认不会生成构造函数了,如果需要强制生成,在函数声明后加上 = default
vector() = default;//强制生成默认构造
vector(const vector& v)
{
//用push_back
for (const auto& e : v)
{
push_back(e);
}
}
vector(const initializer_list& lt)
{
for (const auto& e : lt)
{
push_back(e);
}
}
其中我们需要注意initializer_list这个类是std里面的。
需要防止误会的是,vector v = {1,2,3,4,5,6}不是多参数的隐式类型转换,因为传的参数个数不固定,有无穷种情况,因此它的本质是vector支持一种构造,auto il = {1,2,3,4,5}将任意个数的数据(常量数组)给initializer_list,这个对象里有两个指针,分别指向开始和结束的下一个位置,它也支持迭代器,范围for。当初始化格式为{ }是就会去调用它,这个类会用即可。
(5)复用
其中swap在operator=的实现中很有用,swap不仅交换了数据,还帮忙处理了无用数据
void swap(vector v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector& operator=(const vector v)
{
swap(v);
return *this;
}
(6)全部代码
其余接口都算简单,就不再介绍了
#pragma once
#include
#include
using namespace std;
namespace my_vector
{
template
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector() = default;//强制生成默认构造
vector(const vector& v)
{
//用push_back
for (const auto& e : v)
{
push_back(e);
}
}
vector(const initializer_list& lt)
{
for (const auto& e : lt)
{
push_back(e);
}
}
T& operator[](size_t pos)
{
assert(pos + _start < _finish);//避免越界访问
return *(pos + _start);
}
const T& operator[](size_t pos) const
{
assert(pos + _start < _finish);
return *(pos + _start);
}
size_t size() const
{
return _finish - _start;//有效数据大小
}
size_t capacity() const
{
return _end_of_storage - _start;//总开辟空间
}
void reserve(size_t n)
{
if (n <= capacity())//一律不缩容
return;
size_t oldsize = size();
T* tmp = new T[n];
if (_start)
{
for (size_t count = 0; count + begin() = 0 && pos - _finish = _end_of_storage - _start)//预计算空间,如果不够,则扩容
reserve((capacity() + n) * 2);
iterator newpos = oldpos + _start;//更新新的位置迭代器,原来的pos可能失效
for (iterator curpos = _finish + n - 1; curpos - _start >= newpos + n - _start; curpos--)//从pos开始将数据向后移动n个元素
{
*curpos = *(curpos - n);
}
for (size_t count = 0; count = 0 && first - _finish = 0 && last - _finish = first - _start);//三个assert规范参数
size_t firstpos = GetPos(first);
size_t lastpos = GetPos(last);
size_t len = lastpos - firstpos;
for (size_t count = lastpos; count < GetPos(_finish); count++)
{
_start[count - len] = _start[count];
}
_finish -= len;
return first;//返回清除数据后的第一个位置迭代器
}
void clear()
{
erase(_start, _finish);
}
void swap(vector v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector& operator=(const vector v)
{
swap(v);
return *this;
}
private:
size_t GetPos(const_iterator it)
{
return it - _start;
}
size_t GetPos(iterator it)
{
return it - _start;
}
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}