本文参考了侯捷的 《stl 源码分析》一书，出于兴趣，自行实现了简单的 vector 容器。
之后会陆续上传 list， deque 等容器的代码，若有错误，欢迎留言指出。
vector 容易实现的几点注意事项：
1. 由于vector 是动态数组。
出于效率的考虑，在往vector 中加入元素时，内存的扩展遵循的规则是：
1> 如果当前可用内存不够，开 2倍大的内存，将原来的数组复制到新数组中，撤销原来的数组。
2> 加入新的元素
2. 通常当我们 int *p = new int(1)时， new 其实做了两件事情： 1> 分配内存 2>在分配的内存中调用类的构造函数。
出于效率的考虑，在 vector 的内存管理中，我们将这两个操作分开。
c 提供了 模板类 allocator 来实现上述的功能。
3. vector 中三个指针，分别是 start, finish, end_of_storage;
[start, finish) 就是数组元素；
[finish, end_of_storage) 是预先分配的空间（还没有调用构造函数）
参考书籍：
1. c primer， lippman
2. stl 源码分析， 侯捷
// last update:2014-04-11 15:44:44
/**
* @file vector.h
* @brief a simple vector class
* @author [email protected]
* @version 0.1.00
* @date 2014-04-09
*/
#ifndef my_vector_h
#define my_vector_h
#include
#include
#include
template
void destroy(t* pointer)
{
pointer->~t();
}
template
void destroy(forwarditerator first, forwarditerator last)
{
for(forwarditerator it = first; it != last; it)
{
destroy(&*it);
}
}
template
class myvector
{
public:
typedef t value_type;
typedef t* iterator;
typedef const t*const_iterator;
typedef t* pointer;
typedef const t* const_pointer;
typedef t& reference;
typedef const t& const_reference;
typedef size_t size_type;
myvector();
myvector(size_type n, t value = t());
myvector(iterator begin, iterator end);
~myvector();
//copy control
myvector(const myvector&);
myvector& operator=(const myvector&);
bool empty() const { return begin() == end(); }
size_type size() const {return (size_type)(finish - start);}
size_type capacity() const {return (size_type)(end_of_storage - start);}
iterator begin() { return start; }
const_iterator begin() const{ return start; }
iterator end() { return finish;}
const_iterator end() const{ return finish; }
reference operator[](size_type i){return *(start i);}
const_reference operator[](size_type i)const {return *(start i);}
void insert(iterator position, size_type n, const t& value);
void push_back(const t& value);
void pop_back();
void erase(iterator first, iterator last);
void clear();
void reserve(size_type n);
protected:
iterator start; //空间的头
iterator finish; //空间的尾
iterator end_of_storage; //可用空间的尾巴
private:
static std::allocator alloc; // object to get raw memory
};
// static class member needed to be defined outside of class
template
std::allocator myvector::alloc;
// default constructor
template
myvector::myvector()
: start(null), finish(null), end_of_storage(null)
{
}
template
myvector::myvector(size_type n, t value)
{
start = alloc.allocate(n);
end_of_storage = finish = start n;
for(iterator i=start; i!=finish; i)
alloc.construct(i, value);
}
template
myvector::myvector(iterator begin, iterator end)
{
const size_type n = end - begin;
/* allocate space */
start = alloc.allocate(n);
finish = end_of_storage = start n;
/* call constructor */
std::uninitialized_copy(begin, end, start);
}
template
myvector::~myvector()
{
/* call destructor */
::destroy(start, finish);
/* free space */
alloc.deallocate(start, end_of_storage - start);
}
// copy control
template
myvector::myvector(const myvector& rhs)
{
start = alloc.allocate(rhs.capacity());
std::uninitialized_copy(rhs.start, rhs.finish, start);
finish = start (rhs.finish - rhs.start);
end_of_storage = start (rhs.end_of_storage - rhs.start);
}
template
myvector& myvector::operator=(const myvector& rhs)
{
start = alloc.allocate(rhs.capacity());
std::uninitialized_copy(rhs.start, rhs.finish, start);
finish = start rhs.finish - rhs.start;
end_of_storage = start rhs.end_of_storage - rhs.start;
return *this;
}
template
void myvector::insert(iterator position, size_type n, const t& value)
{
if(n <= end_of_storage - finish)
{/* enough memory */
if(n <= finish - position)
{
std::uninitialized_copy(finish-n, finish, finish);
std::copy(position, finish-n, position n);
std::fill_n(position, n, value);
}
else
{
std::uninitialized_fill_n(finish, n - (finish - position), value);
std::uninitialized_copy(position, finish, position n);
std::fill(position, finish, value);
}
finish = n;
}
else
{/* reallocate */
pointer new_start(null), new_finish(null);
size_type old_type = end_of_storage - start;
size_type new_size = old_type std::max(old_type, n);
new_start = alloc.allocate(new_size);
// copy old vector to new vector
new_finish = std::uninitialized_copy(start, position, new_start);
std::uninitialized_fill_n(new_finish, n, value);
new_finish = n;
new_finish = std::uninitialized_copy(position, finish, new_finish);
alloc.deallocate(start, end_of_storage - start);
start = new_start;
finish = new_finish;
end_of_storage = new_start new_size;
}
}
template
void myvector::push_back(const t &value)
{
insert(end(), 1, value);
}
template
void myvector::pop_back()
{
alloc.destroy(--finish);
}
template
void myvector::erase(iterator first, iterator last)
{
iterator old_finish = finish;
finish = std::copy(last, finish, first);
::destroy(finish, old_finish);
}
template
void myvector::clear()
{
erase(start, finish);
}
template
void myvector::reserve(size_type n)
{
if(capacity() < n)
{
iterator new_start = alloc.allocate(n);
std::uninitialized_copy(start, finish, new_start);
::destroy(start, finish);
alloc.deallocate(start, size());
const size_type old_size = finish - start;
start = new_start;
finish = new_start old_size;
end_of_storage = new_start n;
}
}
#endif /*my_vector_h*/