StrVec(13.5)
该练习设计了一个vector的特化版本 - 一个专门用于存储string的vector，其内存分配通过一个allocator类alloc来管理，用三个指针element, first_free, end_of_storage分别表示内存区开头，已构造内存的末尾以及整个内存区的末尾。
我花了5-6小时设计整个类，但个人认为最重要，最必不可少的组成部分当属默认构造函数，push_back()，构析push_back()将元素加入的容器的操作涉及alloc的分配构造，加入元素前类会先检查容器是否已满，若是就需要通过调用reallocate()函数分配比原内存2倍大的新内存并将旧有元素移动（这里为什么用移动而不是拷贝我并不明白，反正效率更高）到新内存，然后销毁旧内存，更新三个元素指针。
void StrVec::push_back(const string& val){
if(size() == capacity()){
reallocate();
push_back(val);
}
else{
alloc.construct(first_free++,val);
}
}
reallocate()会调用其下的一个工具函数alloc_n_move(n)去新构造一片大小为n的内存并将元素移动到那上面去，至于为什么用工具函数是考虑到了设计reserve和resize的情况，不过由于时间关系我目前并未设计这两个函数。
//scaling vector to two times of its original size
void StrVec::reallocate(){
size_t new_capacity = size() * 2;
alloc_n_move(new_capacity);
}
//move all element to new memory with a size of n;
void StrVec::alloc_n_move(size_t _n){
size_t new_capacity = (size() == 0) ? 1 : _n;
string* new_elem = alloc.allocate(new_capacity);
string *dest = new_elem;
string *old_elem = element;
for(size_t i = 0; i < size(); ++i){
alloc.construct(dest++,std::move(*old_elem++));
}
free();
element = new_elem;
first_free = dest;
end_of_storage = new_elem + new_capacity;
}
构析和reallocate()都需要调用free()函数将旧内存销毁，之后的拷贝赋值函数也会调用到free()，当然需要注意先拷贝再复制以防止自赋值的情况。设计free()时一定注意三个指针是否在自己预料的位置…自己之前因此debug了半天。。。。。。。
void StrVec::free(){
//the element must exist
if(element){
for(string* it = first_free; it != element; ){
alloc.destroy(--it);
}
alloc.deallocate(element,end_of_storage - element);
}
}
上面的就都是核心功能了，后面的从初始化列表构造，拷贝构造，拷贝赋值，pop_back, reserve, resize等等就基本是点缀，不过前面的三个函数都要调用到一个alloc_n_copy(b,e)的函数，这个函数会从[b,e）的区别拷贝内存到新内存并返回新内存的区间[newb, newe)
pair<string*,string*> StrVec::alloc_n_copy(const string* b,const string* e){
auto data = alloc.allocate(e - b);
return {data, uninitialized_copy(b,e,data)};
}
StrVec.h
#pragma once
#include<iostream>
#include<string>
#include<memory>
#include<initializer_list>
using namespace std;
class StrVec{
public:
StrVec():element(nullptr),first_free(nullptr),end_of_storage(nullptr){}
StrVec(initializer_list<string> lst);
StrVec(const StrVec&);
StrVec& operator=(const StrVec&);
void push_back(const string& val);
void pop_back();
const string* begin() const { return element; } //必须在后面加const，否则有qualifer错误
const string* end() const { return first_free; }
size_t size() const { return size_t(first_free - element); }
size_t capacity() { return size_t(end_of_storage - element); }
bool empty() {return element == first_free;}
void print();
~StrVec();
private:
void reallocate();
pair<string*,string*> alloc_n_copy(const string*,const string*);
void alloc_n_move(size_t);
void free();
private:
string* element;
string* first_free;
string* end_of_storage;
allocator<string> alloc;
};
StrVec.cpp
#include"StrVec.h"
StrVec::StrVec(initializer_list<string> lst){
auto range = alloc_n_copy(lst.begin(), lst.end());
element = range.first;
first_free = range.second;
end_of_storage = element + lst.size();
}
StrVec::StrVec(const StrVec& rhs){
auto range = alloc_n_copy(rhs.begin(), rhs.end());
element = range.first;
first_free = range.second;
end_of_storage = element + rhs.size();
}
StrVec& StrVec::operator=(const StrVec& rhs){
auto range = alloc_n_copy(rhs.begin(), rhs.end());
//确保先copy再free - 防范自赋值的情况
free();
element = range.first;
first_free = range.second;
end_of_storage = element + rhs.size();
return *this;
}
void StrVec::push_back(const string& val){
if(size() == capacity()){
reallocate();
push_back(val);
}
else{
alloc.construct(first_free++,val);
}
}
void StrVec::pop_back(){
if(empty() == true)
return;
--first_free;
alloc.destroy(first_free);
}
//scaling vector to two times of its original size
void StrVec::reallocate(){
size_t new_capacity = size() * 2;
alloc_n_move(new_capacity);
}
pair<string*,string*> StrVec::alloc_n_copy(const string* b,const string* e){
auto data = alloc.allocate(e - b);
return {data, uninitialized_copy(b,e,data)};
}
//move all element to new memory with a size of n;
void StrVec::alloc_n_move(size_t _n){
size_t new_capacity = (size() == 0) ? 1 : _n;
string* new_elem = alloc.allocate(new_capacity);
string *dest = new_elem;
string *old_elem = element;
for(size_t i = 0; i < size(); ++i){
alloc.construct(dest++,std::move(*old_elem++));
}
free();
element = new_elem;
first_free = dest;
end_of_storage = new_elem + new_capacity;
}
void StrVec::free(){
//the element must exist
if(element){
for(string* it = first_free; it != element; ){
alloc.destroy(--it);
}
alloc.deallocate(element,end_of_storage - element);
}
}
void StrVec::print(){
for(string* it = element; it != first_free; it++){
cout << *it << " ";
}
cout << endl;
}
StrVec::~StrVec(){
free();
}
12.12 ADD:
将reserve和resize实现了一下，并拿去和vector测试对比，基本和当时背的八股差不多了，不过这次还惊讶的发现原来vector用resize是可能调用push_back的：参数n > capacity的情况下vector的capacity出现了两倍扩容。
源码一写，这下对于这两个函数基本没有疑问了。
void reserve(size_t);
void resize(size_t, const string& val = string());
....
/* change capacity to demanded _n,
if _n <= cap, do nothing, otherwise
make memory of capacity n and move old elements,
then destroy old memory.
*/
void StrVec::reserve(size_t _n){
if(_n < 0)
throw std::length_error("Strvec::reserve");
//实际上这里还应该检测max_size,这里就不设计了
if(_n <= capacity())
return;
else{
alloc_n_move(_n);
}
}
/*
change size to demanded _n,
if _n < size, change size to _n.
*/
void StrVec::resize(size_t _n, const string& val){
if(_n < 0)
throw std::length_error("Strvec::resize");
//实际上这里还应该检测max_size,这里就不设计了
while(size() != _n){
if(_n < size())
pop_back();
else{
//如果发生了扩容，让push_back背后的alloc_n_move承担
push_back(val);
}
}
}
测试程序（对于vector改个类型就行）
#include<vector>
#include"StrVec.h"
void print(StrVec &vec){
for(string str : vec){
cout << str << " ";
}
cout << endl;
}
int main(){
StrVec vec1({"H","G","B","N","E","G"});
cout << vec1.size() << " " << vec1.capacity() << endl;
vec1.resize(8);
cout << vec1.size() << " " << vec1.capacity() << endl;
print(vec1);
vec1.resize(12);
cout << vec1.size() << " " << vec1.capacity() << endl;
print(vec1);
vec1.resize(17,"B");
cout << vec1.size() << " " << vec1.capacity() << endl;
print(vec1);
}
String(13.5)
其实String的很多行为都和vector相似，上面的StrVec稍加改进就是一个String了， 但实际的String需要处理的细节更多，包括重载ostream输出，定义加减比较运算符等，这里只把c_str和const char*构造实现了，有趣的是不同于vector，string源码size()和capacity()其实是用的变量记录而不是指针计算，size()和capacity都是O(1）返回，底层管理的其实也是个char数组而不是用alloc（EffectiveSTL提到可能还有其他实现方式，比如引用计数指向同一块字符串内存），另外不同于vector，string不管用哪种方式构造都会预留15大小的空间，直到用完了后再两倍扩容。
另外在实现的时候遇到了一个坑，我空参构造String设置的是将三个指针都置为Nullptr，但是这样程序会出现一个莫名其妙的bug，就是调用了某个空参构造的String的c_str后，剩下的String不管有参无参都打印不出属性，起初我还以为是逻辑错误导致指针赋错值的问题，结果我gdb了半天，不断改测试代码，发现指针都是赋的正常值，始终没怪到自己的String类上，最后问了下chatGPT, 一下子就道破了我String类的问题。。。。AI牛逼啊，虽然我不知道为什么一个对象c_str返回空指针会导致其他对象输出异常。
const char* String::c_str() const{
if(element)
return element;
//这里不能直接返回空指针，不然后面对象输出会异常
return "";
}
String.h
#pragma once
#pragma once
#include<iostream>
#include<string>
#include<memory>
#include<initializer_list>
#include<algorithm>
using namespace std;
class String{
public:
String():element(nullptr),first_free(nullptr),end_of_storage(nullptr){}
String(initializer_list<char> lst);
+ String(const char*);
String(const String&);
String& operator=(const String&);
void push_back(const char& val);
void pop_back();
+ const char* c_str() const;
const char* begin() const { return element; }
const char* end() const { return first_free; }
size_t size() const { return size_t(first_free - element); }
size_t capacity() { return size_t(end_of_storage - element); }
void reserve(size_t);
void resize(size_t, const char& val = char());
bool empty() {return element == first_free;}
void print();
~String();
private:
void reallocate();
pair<char*,char*> alloc_n_copy(const char*,const char*);
void alloc_n_move(size_t);
void free();
private:
char* element;
char* first_free;
char* end_of_storage;
allocator<char> alloc;
};
String.cpp
#include"String.h"
#include <cstring>
String::String(initializer_list<char> lst){
auto range = alloc_n_copy(lst.begin(), lst.end());
element = range.first;
first_free = range.second;
end_of_storage = element + lst.size();
}
+String::String(const char* c_str) {
size_t len = strlen(c_str);
char *beg = const_cast<char*>(c_str);
char *end = beg + len;
auto range = alloc_n_copy(beg, end);
element = range.first;
first_free = range.second;
end_of_storage = element + len;
}
String::String(const String& rhs){
auto range = alloc_n_copy(rhs.begin(), rhs.end());
element = range.first;
first_free = range.second;
end_of_storage = element + rhs.size();
}
String& String::operator=(const String& rhs){
auto range = alloc_n_copy(rhs.begin(), rhs.end());
//确保先copy再free - 防范自赋值的情况
free();
element = range.first;
first_free = range.second;
end_of_storage = element + rhs.size();
return *this;
}
void String::push_back(const char& val){
if(size() == capacity()){
reallocate();
push_back(val);
}
else{
alloc.construct(first_free++,val);
}
}
void String::pop_back(){
if(empty() == true)
return;
--first_free;
alloc.destroy(first_free);
}
+const char* String::c_str() const{
if(element)
return element;
return ""; // return an empty string instead of a null pointer
}
/* change capacity to demanded _n,
if _n <= cap, do nothing, otherwise
make memory of capacity n and move old elements,
then destroy old memory.
*/
void String::reserve(size_t _n){
if(_n < 0)
throw std::length_error("Strvec::reserve");
//实际上这里还应该检测max_size,这里就不设计了
if(_n <= capacity())
return;
else{
alloc_n_move(_n);
}
}
/*
change size to demanded _n,
if _n < size, change size to _n.
*/
void String::resize(size_t _n, const char& val){
if(_n < 0)
throw std::length_error("Strvec::resize");
//实际上这里还应该检测max_size,这里就不设计了
while(size() != _n){
if(_n < size())
pop_back();
else{
//如果发生了扩容，让push_back背后的alloc_n_move承担
push_back(val);
}
}
}
//scaling vector to two times of its original size
void String::reallocate(){
size_t new_capacity = size() * 2;
alloc_n_move(new_capacity);
}
pair<char*,char*> String::alloc_n_copy(const char* b,const char* e){
auto data = alloc.allocate(e - b);
return {data, uninitialized_copy(b,e,data)};
}
/* move all element to new memory with a capacity of n;
size remain unchange.
*/
void String::alloc_n_move(size_t _n){
size_t new_capacity = (size() == 0) ? 1 : _n;
char* new_elem = alloc.allocate(new_capacity);
char *dest = new_elem;
char *old_elem = element;
for(size_t i = 0; i < size(); ++i){
alloc.construct(dest++,std::move(*old_elem++));
}
free();
element = new_elem;
first_free = dest;
end_of_storage = new_elem + new_capacity;
}
void String::free(){
//the element must exist
if(element){
for(char* it = first_free; it != element; ){
alloc.destroy(--it);
}
alloc.deallocate(element,end_of_storage - element);
}
}
void String::print(){
for(char* it = element; it != first_free; it++){
cout << *it << " ";
}
cout << endl;
}
String::~String(){
free();
}
测试代码：
#include<iostream>
#include<vector>
#include"String.h"
using namespace std;
int main(){
String cpp;
cpp.push_back('A');
cout << cpp.c_str() << cpp.size() << cpp.capacity() << endl;
String cpp2 = "bbbb";
for(auto it = cpp2.begin(); it != cpp2.end(); it++){
cout << *it << " ";
}
String cpp3(cpp);
cout << cpp3.c_str() << " " << cpp3.size() << " " << cpp3.capacity() << endl;
String cpp4 = "happy";
cout << cpp4.c_str() << " " << cpp4.size() << " " << cpp4.capacity() << endl;
}
string源码部分：
...
pointer _M_p; // The actual data.
};
_Alloc_hider _M_dataplus;
size_type _M_string_length;
enum { _S_local_capacity = 15 / sizeof(_CharT) };
union
{
_CharT _M_local_buf[_S_local_capacity + 1];
size_type _M_allocated_capacity;
};
...
size_type
size() const _GLIBCXX_NOEXCEPT
{ return _M_string_length; }
/**
* Returns the total number of characters that the %string can hold
* before needing to allocate more memory.
*/
size_type
capacity() const _GLIBCXX_NOEXCEPT
{
return _M_is_local() ? size_type(_S_local_capacity)
: _M_allocated_capacity;
}
|