C++ Primer 第十三章 13.5 动态内存管理类 类StrVec

StrVec 类完整实现

#include
#include
#include
#include
#include
using namespace std;
class StrVec
{
public:
	StrVec() :elements(nullptr), first_free(nullptr), cap(nullptr) {}  // alloc默认初始化
	StrVec(initializer_list li);
	StrVec(const StrVec&);
	StrVec& operator=(const StrVec&);
	string& operator[](size_t n)
	{
		return elements[n];
	}
	const string& operator[](size_t n)const
	{
		return elements[n];
	}
	~StrVec();
public:
	void push_back(const string&);
	size_t size()const { return first_free - elements; }
	size_t capacity()const { return cap - elements; }
	string* begin()const { return elements; }
	string* end()const { return first_free; }
	string& back();
	const string& back()const;
	void reserve(size_t n) { if (n > capacity()) reallocate(n); }
	void resize(size_t n);
	void resize(size_t n, const string& s);
private:
	static allocator alloc;   // 静态成员分配元素
	// 被添加元素的函数所使用
	void chk_n_alloc() { if (size() == capacity())	reallocate(); }
	// 工具函数，被拷贝构造函数，赋值运算符和析构函数所使用。
	pair alloc_n_copy(const string*, const string*);
	void free();			 // 销毁元素并释放内存
	void reallocate();		 // 获得更多内存并拷贝已有元素
	void reallocate(size_t);
	string* elements;        // 指向数组首元素的指针
	string* first_free;      // 指向数组第一个空闲元素的指针
	string* cap;			 // 指向数组尾后位置的指针
};
inline string& StrVec::back()
{
	assert(size() >= 1);
	return *(end() - 1);
}
inline const string& StrVec::back()const
{
	assert(size() >= 1);
	return *(end() - 1);
}

inline void StrVec::resize(size_t n)
{
	if (n > size())
	{
		//reserve(n);
		//auto sz = size();
		//while (sz++ != n)
		//	alloc.construct(first_free++, "");
		while (size() < n)
			push_back("");
	}
	else if (n < size())
	{
		while (size() > n)
			alloc.destroy(--first_free);
	}
}

inline void StrVec::resize(size_t n, const string& s)
{
	if (n > size())
	{
		while (size() < n)
			push_back(s);
	}
}


inline void StrVec::reallocate(size_t sz)
{
	assert(sz >= size());  // 其实没有必要，因为这个函数是私有成员函数，不会被外界调用，因此调用的时候都是合理的。
	auto newbegin = alloc.allocate(sz);
	auto dest = newbegin;
	for (auto i = elements; i != first_free; ++i)
		alloc.construct(dest++, std::move(*i));
	free();
	elements = newbegin;
	first_free = dest;
	cap = elements + sz;
}

StrVec::StrVec(const StrVec& v)
{
	auto ret = alloc_n_copy(v.begin(), v.end());
	elements = ret.first;
	cap = first_free = ret.second;
}

StrVec::StrVec(initializer_list li)
{
	//size_t sz = li.end() - li.begin();
	//auto begin = alloc.allocate(sz);
	//auto dest = begin;
	//for (auto i = li.begin(); i != li.end(); ++i)
	//	alloc.construct(dest++, *i);
	//elements = begin;
	//cap = first_free = dest;
	auto sp = alloc_n_copy(li.begin(), li.end());
	elements = sp.first;
	cap = first_free = sp.second;
}

StrVec::~StrVec()
{
	free();
}

StrVec& StrVec::operator=(const StrVec& v)
{
	auto ret = alloc_n_copy(v.begin(), v.end());
	free();
	elements = ret.first;
	cap = first_free = ret.second;
	return *this;
}

void StrVec::push_back(const string& s)
{
	chk_n_alloc();  // 确保有空间可以进行构造
	alloc.construct(first_free++, s);  // 在first_free指向的元素中构造s的副本
	// 会根据参数确定用哪个构造函数来构造对象，本例中只有一个额外参数，类型为string，因此会使用string的拷贝构造函数
}

pair StrVec::alloc_n_copy(const string* begin, const string* end)
{
	auto first = alloc.allocate(end - begin);
	return { first, uninitialized_copy(begin, end, first) };  // first指向开辟空间的首地址，second指向用本对象的内存数据构造之后的内存空间的尾地址。
}

void StrVec::free()
{
	//free(3)
	auto t = elements;
	for_each(t, first_free, [](string& s) {alloc.destroy(&s); });
	alloc.deallocate(elements, cap - elements);
	// free(2)
	//if (elements)
	//{
	//	// 将已经构造的元素销毁，然后调用deallocate释放所有最初申请的空间
	//	for (auto p = first_free; p != elements; )  
	//		alloc.destroy(--p);
	//	alloc.deallocate(elements, cap - elements);
	//}

	// free(1)
	//auto tmp = elements;
	//while (tmp != first_free)
	//	alloc.destroy(tmp++);
	//alloc.deallocate(elements, cap - elements);
}

void StrVec::reallocate()
{
	// 先开辟更大的空间，然后逐个移动。
	auto newcapacity = size() ? size() * 2 : 1;
	auto newdata = alloc.allocate(newcapacity);

	auto dest = newdata;
	auto src = elements;
	for (size_t i = 0; i != size(); ++i)
		alloc.construct(dest++, std::move(*src++));  //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	free();
	elements = newdata;
	first_free = dest;
	cap = newdata + newcapacity;
}
allocator StrVec::alloc;
void test_StrVec()
{
	StrVec vec;
	vec.push_back("hahaha");
	int i = 0;
	cin >> i;
	string s;
	while (i-- && cin >> s)
		vec.push_back(s);
	for (auto i = vec.begin(); i != vec.end(); ++i)
		cout << *i << endl;
	StrVec vec2 = vec;
	vec2.push_back("zzz");
	cout << vec2.back() << endl;
	cout << vec.back() << endl;
}

void test_initializer()
{
	StrVec v({ "11","22","33" });
	cout << v.back() << endl;
}

void test_resize()
{
	StrVec v;
	v.resize(5, "sss");
	cout << v.size() << endl;
	cout << v.back() << endl;
}

int main()
{
	test_resize();
	return 0;
}

大致介绍：此类用于模拟vector。使用allocator类对象来申请空间，再用allocator类成员函数来构造元素，销毁元素，释放元素。

三种构造函数，参数为列表的以及拷贝构造函数都使用了alloc_n_copy私有成员函数。并且拷贝赋值运算符也使用了这个函数。那些公有的成员函数就不介绍了，都是一些基本实现。 

1.  私有成员中，静态数据成员allocator alloc的使用有点新颖，注意此成员可以给任意个StrVec对象申请空间，因为这个数据成员属于类，并且allocator类对象本身也有这个功能，可以无限申请空间。

2.  elements first_free cap数据成员用于指向alloc申请的内存的特定位置地址。

alloc_n_copy

pair StrVec::alloc_n_copy(const string* begin, const string* end)
{
	auto first = alloc.allocate(end - begin);
	return { first, uninitialized_copy(begin, end, first) };  // first指向开辟空间的首地址，second指向用本对象的内存数据构造之后的内存空间的尾地址。
}

 这个函数的实现可以说是这个类的最秀的地方了，接收的参数是任意一个范围的起始地址和末尾地址，作用是开辟另一块同大小的内存，并将这个范围的数据拷贝过去。

  C++ Primer源码中的注释：

    // allocate space to hold as many elements as are in the range
    auto data = alloc.allocate(e - b);

    // initialize and return a pair constructed from data and
    // the value returned by uninitialized_copy

并且你会发现，拷贝构造，以及以initializer_list为参数的构造函数，拷贝赋值运算符，都用到了alloc_n_copy。非常方便。

free()的实现

void StrVec::free()
{
	//free(3)
	auto t = elements;
	for_each(t, first_free, [](string& s) {alloc.destroy(&s); });
	alloc.deallocate(elements, cap - elements);
	// free(2)
	//if (elements)
	//{
	//	// 将已经构造的元素销毁，然后调用deallocate释放所有最初申请的空间
	//	for (auto p = first_free; p != elements; )  
	//		alloc.destroy(--p);
	//	alloc.deallocate(elements, cap - elements);
	//}

	// free(1)
	//auto tmp = elements;
	//while (tmp != first_free)
	//	alloc.destroy(tmp++);
	//alloc.deallocate(elements, cap - elements);
}

reallocate()

void StrVec::reallocate()
{
	// 先开辟更大的空间，然后逐个移动。
	auto newcapacity = size() ? size() * 2 : 1;
	auto newdata = alloc.allocate(newcapacity);

	auto dest = newdata;
	auto src = elements;
	for (size_t i = 0; i != size(); ++i)
		alloc.construct(dest++, std::move(*src++));  //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	free();
	elements = newdata;
	first_free = dest;
	cap = newdata + newcapacity;
}

引用书中的三句话来说明这个函数：

1. 当reallocate在新内存中构造string时，它必须调用move来表示它希望使用string的移动构造函数。（string类内部已经实现了这些移动构造函数了）

2.  construct的第二个参数（即，确定使用哪个构造函数的参数）是move的返回值。调用move返回的结果会令construct使用string的移动构造函数。

3.  由于我们使用了移动构造函数，这些string管理的内存将不会被拷贝。相反，我们构造的每个string都会从elem指向的string那里接管内存的所有权（具体细节我也不知道了，需要学习13.6节 对象移动）。

其实，这个函数也一般吧，也就是开辟一个更大的内存，然后将之前已有的元素利用std::move()在新内存中构造同样的元素。