c++11简易手写vector

代码要点

• placement new：原地构造对象，避免内存频繁地申请和释放
• 手动析构 + operator delete：和placement new配套使用，析构对象不一定要释放内存
• 三个指针成员：当然也可以一个指针 + size + capacity，但gcc中用的是三个指针
• ~MyVector()：不可以写成~MyVector() { delete(_start); }，否则只有 _start指向的元素会被析构

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>

template<typename T>
class MyVector {
private:
	T* _start;
	T* _finish;
	T* _end_of_range;

	void reallocate() {
		size_t oldCapacity = capacity();
		size_t newCapacity = oldCapacity ? 2 * oldCapacity : 1;

		T* newStart = static_cast<T*>(operator new(newCapacity * sizeof(T)));
		if (!newStart) {
			throw std::bad_alloc();
		}
		size_t oldSize = size();
		for (T* p = _start; p != _finish; p++) {
			new (newStart + (p - _start)) T(*p);
		}

		// 析构旧元素
		for (T* p = _start; p != _finish; ++p) {
			p->~T();
		}

		// 释放旧内存
		operator delete(_start);

		_start = newStart;
		_finish = _start + oldSize;
		_end_of_range = _start + newCapacity;
	}


	// 将 [first, last) 区间的元素右移一位
	void shiftRight(T* first, T* last) {
		for (T* p = last; p > first; --p) {
			new (p) T(*(p - 1));
			(p - 1)->~T();
		}
	}


	// 将 [first, last) 区间的元素左移一位
	void shiftLeft(T* first, T* last) {
		for (T* p = first; p < last - 1; ++p) {
			p->~T();
			new (p) T(*(p + 1));
		}
		(last - 1)->~T();
	}

public:
	MyVector() : _start(nullptr), _finish(nullptr), _end_of_range(nullptr) {}


	explicit MyVector(size_t n) {
		_start = static_cast<T*>(operator new(n * sizeof(T)));
		_finish = _start + n;
		_end_of_range = _start + n;

		// 使用 placement new 初始化元素, 内存复用
		for (T* p = _start; p != _finish; ++p) {
			new (p) T();
		}
	}


	~MyVector() {
		for (T* p = _start; p != _finish; ++p) {
			p->~T();
		}
		operator delete(_start);
	}


	size_t size() const { return _finish - _start; }

	size_t capacity() const { return _end_of_range - _start; }

	bool empty() const { return _start == _finish; }

	T& operator[](size_t index) { return *(_start + index); }

	const T& operator[](size_t index) const { return *(_start + index); }


	void push_back(const T& value) {
		if (_finish == _end_of_range) {
			reallocate();
		}

		// 使用 placement new 构造元素
		new (_finish) T(value);
		++_finish;
	}


	void pop_back() {
		if (!empty()) {
			_finish--;
			_finish->~T();
		}
	}


	void insert(size_t pos, const T& value) {
		if (pos > size()) {
			throw std::out_of_range("Insert position out of range");
		}
		if (_finish == _end_of_range) {
			reallocate();
		}
		T* insertPos = _start + pos;
		shiftRight(insertPos, _finish);
		new (insertPos) T(value);
		++_finish;
	}


	void erase(size_t pos) {
		if (pos >= size()) {
			throw std::out_of_range("Erase position out of range");
		}
		T* erasePos = _start + pos;
		erasePos->~T();
		shiftLeft(erasePos, _finish);
		--_finish;
	}


	T& front() {
		if (empty()) {
			throw std::out_of_range("Vector is empty");
		}
		return *_start;
	}


	T& back() {
		if (empty()) {
			throw std::out_of_range("Vector is empty");
		}
		return *(_finish - 1);
	}


	void clear() {
		for (T* p = _start; p != _finish; ++p) {
			p->~T();
		}
		_finish = _start;
	}
};


// 测试插入元素的时间
template<typename VectorType>
void testInsertion(size_t numElements) {
	VectorType vec;
	auto start = std::chrono::high_resolution_clock::now();
	for (size_t i = 0; i < numElements; ++i) {
		vec.push_back(i);
	}
	auto end = std::chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
	std::cout << "插入 " << numElements << " 个元素耗时: " << duration << " 毫秒" << std::endl;
}


// 测试访问元素的时间
template<typename VectorType>
void testAccess(size_t numElements) {
	VectorType vec;
	for (size_t i = 0; i < numElements; ++i) {
		vec.push_back(i);
	}
	auto start = std::chrono::high_resolution_clock::now();
	for (size_t i = 0; i < numElements; ++i) {
		volatile auto value = vec[i];
	}
	auto end = std::chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
	std::cout << "访问 " << numElements << " 个元素耗时: " << duration << " 毫秒" << std::endl;
}


void functionTest() {
	MyVector<int> vec(3);

	vec.push_back(10);
	vec.push_back(20);
	vec.push_back(30);

	std::cout << "第一个元素: " << vec[0] << std::endl;
	std::cout << "第二个元素: " << vec[1] << std::endl;

	vec[1] = 25;
	std::cout << "修改后的第二个元素: " << vec[1] << std::endl;

	vec.pop_back();
	std::cout << "删除最后一个元素后，MyVector 的大小: " << vec.size() << std::endl;

	vec.insert(1, 40);
	std::cout << "插入元素后，第二个元素: " << vec[1] << std::endl;

	vec.erase(1);
	std::cout << "删除元素后，第二个元素: " << vec[1] << std::endl;

	std::cout << "首元素: " << vec.front() << std::endl;
	std::cout << "尾元素: " << vec.back() << std::endl;

	vec.clear();
	std::cout << "清除元素后，MyVector 的大小: " << vec.size() << std::endl;
}


int main() {
	//functionTest();

	const size_t numElements = 10000000;

	std::cout << "MyVector 测试:" << std::endl;
	testInsertion<MyVector<int>>(numElements);
	testAccess<MyVector<int>>(numElements);

	std::cout << "\nstd::vector 测试:" << std::endl;
	testInsertion<std::vector<int>>(numElements);
	testAccess<std::vector<int>>(numElements);


	return 0;
}

测试结果

gcc下：

惊人地发现我们随便手写的vector比std::vector更快

一些猜测的可能解释如下：

• std::vector有更严格的安全和异常检查，运行时开销更大
• std::vector不是直接使用的placement new，而是用的allocator模板类，在其中使用的placement new；而allocator的复杂设计中可能会带来一些运行时开销