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; } ~~~ 运行结果: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-08-11_57ac4c8bcc81c.jpg) 参考: 《STL源码剖析》 《C++ primer》
';