顺序容器

欢迎访问我的博客首页。

---

1. vector

---

  实现 vector 的重点是实现迭代器。

template<typename T>
class Vector {
public:
	Vector() :m_ptr(nullptr), m_size(0), m_capacity(0) {}
	Vector(size_t n, const T& val) {
		m_ptr = alloc.allocate(n);
		for (int i = 0; i < n; i++)
			alloc.construct(m_ptr + i, val);
		m_size = m_capacity = n;
	}
	Vector(std::initializer_list<T> vals) {
		m_ptr = alloc.allocate(vals.size());
		for (int i = 0; i < vals.size(); i++)
			alloc.construct(m_ptr + i, vals.begin()[i]);
		m_size = m_capacity = vals.size();
	}
	Vector(const Vector& vec) {
		m_ptr = alloc.allocate(vec.capacity());
		memcpy(m_ptr, vec.m_ptr, sizeof(T) * vec.size());
		m_size = vec.size();
		m_capacity = vec.capacity();
	}
	Vector& operator=(const Vector& vec) {
		if (this == &vec)
			return *this;
		// 删除自己的。
		for (int i = 0; i < m_size; i++)
			alloc.destroy(m_ptr + i);
		alloc.deallocate(m_ptr, m_capacity);
		// 创建新的。
		m_ptr = alloc.allocate(vec.capacity());
		memcpy(m_ptr, vec.m_ptr, sizeof(T) * vec.size());
		// 更新成员变量。
		m_size = vec.size();
		m_capacity = vec.capacity();
		return *this;
	}
	void reserve(size_t cpa) {
		// 增大容量。
		if (cpa <= m_capacity)
			return;
		// 创建新的。
		T* ptr = alloc.allocate(cpa);
		memcpy(ptr, m_ptr, sizeof(T) * m_size);
		// 删除自己的。
		for (int i = 0; i < m_size; i++)
			alloc.destroy(m_ptr + i);
		alloc.deallocate(m_ptr, m_capacity);
		// 更新成员变量。
		m_ptr = ptr;
		m_capacity = cpa;
	}
	void resize(size_t sz, const T& val) {
		// 调整元素个数。
		if (sz < m_size) {
			for (int i = sz; i < m_size; i++)
				alloc.destroy(m_ptr + i);
		}
		else if (m_size < sz && sz <= m_capacity) {
			for (int i = m_size; i < sz; i++)
				alloc.construct(m_ptr + i, val);
		}
		else if (m_capacity < sz) {
			reserve(sz);
			for (int i = m_size; i < sz; i++)
				alloc.construct(m_ptr + i, val);
		}
		m_size = sz;
	}
	void shrink_to_fit() {
		// 祛除多余容量。
		if (m_size == m_capacity)
			return;
		// 创建新的。
		T* ptr = alloc.allocate(m_size);
		memcpy(ptr, m_ptr, sizeof(T) * m_size);
		// 删除自己的。
		for (int i = 0; i < m_size; i++)
			alloc.destroy(m_ptr + i);
		alloc.deallocate(m_ptr, m_capacity);
		// 更新成员变量。
		m_ptr = ptr;
		m_capacity = m_size;
	}
	void push_back(const T& val) {
		if (m_size == m_capacity) {
			size_t new_capacity = m_capacity + m_capacity / 2;
			new_capacity = new_capacity > m_size + 1 ? new_capacity : m_size + 1;
			reserve(new_capacity);
		}
		alloc.construct(m_ptr + m_size, val);
		m_size += 1;
	}
	void pop_back() {
		m_size -= 1;
		alloc.destroy(m_ptr + m_size);
	}
	size_t size() const { return m_size; }
	size_t capacity() const { return m_capacity; }
	T& operator[](size_t i) { return m_ptr[i]; }
	T& at(size_t i) { return m_ptr[i]; }
	void swap(Vector& vec) { std::swap(*this, vec); }
	void clear() {
		for (int i = 0; i < m_size; i++)
			alloc.destroy(m_ptr + i);
		m_size = 0;
	}
	~Vector() {
		clear();
		alloc.deallocate(m_ptr, m_capacity);
		m_capacity = 0;
		//delete m_ptr; 不要这一步！
		m_ptr = nullptr;
	}
private:
	std::allocator<T> alloc;
	T* m_ptr;
	size_t m_size, m_capacity;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

  成员变量alloc应该定义成静态。拷贝元素可以用下面两种方法：

memcpy(ptr, m_ptr, sizeof(T) * m_size);
// 上面1行与下面2行作用等价。
for (int i = 0; i < m_size; i++)
	alloc.construct(ptr + i, m_ptr[i]);
1
2
3
4

2. 参考

---

1. 实现vector