C++简易vector
最后更新于：2022-04-01 19:54:57
好久没动手写一点C++程序了，以后没事多模仿STL吧，虽然达不到标准的STL的程序，但简单的功能还是要实现的。STL确实博大精深：泛型编程、容器、算法、适配器...有的是内容可以学。下面是根据STL源码，写的一个非常简单的vector，实现了部分接口。其实vector还是相对很简单的容器了，元素按在内存中连续排列，只需要三个指针就能实现很多的接口。还有一个就是内存的分配，这里采用了一个C++提供的allocator配置器，所以分配起来还是蛮简单的，SGI版本的STL中的配置器为了达到效率的极致，使用了另外的分配器，相当复杂，这里就没有写了。
~~~
#ifndef __MYVECTOR_H__
#define __MYVECTOR_H__
template
class Vector {
public:
typedef T value_type;
typedef value_type* iterator; // vector的迭代器就是原生指针
typedef value_type* pointer;
typedef value_type& reference;
typedef size_t size_type;
public:
Vector() : start(NULL), finish(NULL), end_of_storage(NULL)
{
}
Vector(size_type n, const value_type &value)
{
start = alloc.allocate(n);
end_of_storage = finish = start + n;
uninitialized_fill_n(start, n, value);
}
Vector(size_type n)
{
start = alloc.allocate(n);
end_of_storage = finish = start + n;
uninitialized_fill_n(start, n, value_type());
}
~Vector()
{
// 顺序调用元素的析构函数
for (iterator i = start; i != finish; ++i)
alloc.destroy(i);
// 销毁分配的空间
if (start != NULL)
alloc.deallocate(start, end_of_storage - start);
}
iterator begin() const
{
return start;
}
iterator end() const
{
return finish;
}
size_type size() const
{
return end() - begin(); // 使用接口函数，包裹性更好
}
size_type capacity() const
{
return end_of_storage - begin(); // 使用接口函数，包裹性更好
}
bool empty() const
{
return begin() == end();
}
// 返回的引用可被修改
reference front()
{
return *(begin());
}
// 返回的引用可被修改
reference back()
{
return *(end() - 1);
}
reference operator[] (const size_type n)
{
return *(begin() + n);
}
const reference operator[] (const size_type n) const
{
return *(begin() + n);
}
void push_back(const value_type &value)
{
if (finish == end_of_storage)
reallocate(); // 存储空间已满，则重新分配内存
alloc.construct(finish, value);
++finish;
}
void reallocate();
void pop_back()
{
--finish;
alloc.destroy(finish); // 析构最后一个函数，但不释放空间
}
// 清除一个元素
iterator erase(iterator position)
{
if (position + 1 != finish)
copy(position + 1, finish, position);
--finish;
alloc.destroy(finish);
return position;
}
// 清除一段元素
iterator erase(iterator first, iterator last)
{
if (first < start || last > finish)
throw exception("Invalid input.");
copy(last, finish, first);
int len = last - first;
while (len--)
alloc.destroy(--finish);
return first;
}
void clear()
{
erase(begin(), end());
}
private:
iterator start;
iterator finish;
iterator end_of_storage;
private:
static std::allocator alloc; // 空间配置器，采用静态属性节省空间
};
template
std::allocator Vector::alloc;
template
void Vector::reallocate()
{
size_type oldsize = size();
size_type newsize = 2 * (oldsize == 0 ? 1 : oldsize);
// 分配新的内存空间
iterator newstart = alloc.allocate(newsize);
uninitialized_copy(start, finish, newstart);
// 顺序调用每个元素的析构函数
for (iterator i = start; i != finish; ++i)
alloc.destroy(i);
// 销毁分配的空间，销毁之前主要检查是否为NULL
if (start != NULL)
alloc.deallocate(start, end_of_storage - start);
// 更新下标
start = newstart;
finish = start + oldsize;
end_of_storage = start + newsize;
}
#endif
~~~
insert操作应该算是最复杂的一个接口了，设计到元素的搬移、（可能）重新分配内存等等，这里我只实现了一个最简单的形式：
~~~
template
void Vector::insert(iterator position, const value_type &value)
{
size_type diff = position - start;
if (finish == end_of_storage)
reallocate();
position = start + diff;
// 注意，这里不能使用copy，因为目的地最后一个位置还没有被构造，
// 赋值涉及析构操作，对未构造的对象进行析构，行为未定义
alloc.construct(finish, *(finish - 1));
++finish;
copy_backward(position, finish - 1, finish);
// 不能使用uninitialized_copy，因为这个函数是从前向后构造，这会造成覆盖
//uninitialized_copy(position, finish, position + 1);
// 插入新对象，直接赋值即可
*position = value;
}
~~~
测试程序：
~~~
int main()
{
Vector v;
v.push_back(1);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(2);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(3);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(4);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(5);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
Vector::iterator iter1 = v.begin();
Vector::iterator iter2 = iter1 + 3;
v.erase(iter1, iter2);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.clear();
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
v.push_back(123);
cout << "size = " << v.size() << endl;
cout << "capacity = " << v.capacity() << endl;
for (Vector::iterator iter = v.begin(); iter != v.end(); ++iter)
cout << *iter << endl;
system("pause");
return 0;
}
~~~
运行结果：
参考：
《STL源码剖析》
《C++ primer》
';