目錄
1.拷貝構造函數
寫法1
寫法2
測試代碼
調試找bug
解決方法:修改拷貝構造函數
測試代碼
2.operator[ ]
測試代碼
1.沒有const修飾
2.有const修飾
3.insert
迭代器失效問題
承接CD42.vector模擬實現(1)文章
1.拷貝構造函數
設置start、finish和end_of_storage這幾個參數就行,注意是深拷貝!
寫法1
vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{start = new T[x.capacity()];memmove(start, x.start, x.size()*sizeof(value_type));finish = start + x.size();end_of_storage = start + x.capacity();
}
注:new的參數可以為capacity,也可以為size,這個C++標準沒有規定,空間可以不一樣,但是有效元素必須一樣
寫法2
復用reserve和memmove函數
這個代碼有問題:
vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{reserve(x.capacity());memmove(start, x.start, x.size() * sizeof(value_type));
}
測試代碼
void const_vector_print(const mystl::vector<int> v)
{for (size_t i = 0;i < v.size(); i++)std::cout << v[i] << " ";
}void test6()
{mystl::vector<int> v;v.push_back(1); v.push_back(2);v.push_back(3); const_vector_print(v);return;
}
運行結果:什么都沒有打印
調試找bug
什么都沒有打印,可以判定沒有進入循環,
下斷點到循環,看看情況:
start和finish的地址一樣,v.size()計算出來為0,沒有進入循環,可以斷定拷貝構造函數出了問題,
下斷點到拷貝構造函數,再次調試:
x.capacity()計算出來是4,進入reserve函數內部:
對空的vector進行reserve,看以下分析圖:
解決方法:修改拷貝構造函數
reserve沒有更新finish,那就手動更新finish
vector(const vector<value_type>& x):start(0), finish(0), end_of_storage(0)
{reserve(x.capacity());finish = start + x.size();memmove(start, x.start, x.size() * sizeof(value_type));
}
而且標準庫也是這樣實現的:
運行結果:
同理,reserve函數也要修改:
void reserve(size_type n)
{if (n > capacity()){T* tmp = new T[n];size_t len = size();//delete前先保存元素的個數!bool flag = false;if (size() == 0){flag = true;len = n;}memmove(tmp,start , size()* sizeof(value_type));delete[] start;if (flag)//如果vector在什么元素都沒有{start = finish = tmp;}else{start = tmp;finish = start + len;}end_of_storage = start + n;}
}
測試代碼
void test4()
{mystl::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);mystl::vector<int> v2(v1);for (auto& a:v2)std::cout << a << " ";
}
運行結果:
2.operator[ ]
參數保持一樣的類型:
注意到返回類型被重定義過,因此先進行重定義:
typedef value_type& reference;
typedef const value_type& const_reference;
必須保證提供的n是合法的,換句話說,n<size(),可以使用assert斷言
reference operator[] (size_type n)
{assert(n < size());return *(start + n);//也可以寫成start[n]
}const_reference operator[] (size_type n) const
{assert(n < size());return *(start + n);//也可以寫成start[n]
}
測試代碼
1.沒有const修飾
void test5()
{mystl::vector<int> v;v.push_back(1); v[0]++;v.push_back(2); v[1]++;v.push_back(3); v[2]++;for (auto& a : v)std::cout << a << std::endl;return;
}
運行結果:
2.有const修飾
void const_vector_print(const mystl::vector<int> v)
{for (size_t i = 0;i < v.size(); i++)std::cout << v[i] << " ";
}void test6()
{mystl::vector<int> v;v.push_back(1); v.push_back(2);v.push_back(3); const_vector_print(v);return;
}
運行結果:
3.insert
參數保持一樣的類型,為了簡單起見,這里只實現第一個
首先要斷言,position必須合法:
assert(position >= start && position <= finish);
插入前先看看是否需要擴容,可以直接借用CD42.vector模擬實現(1)文章的push_back函數的代碼:
if (finish == nullptr)reserve(4);
if (finish == end_of_storage)reserve(capacity() * 2);
和CD38.【C++ Dev】string類的模擬實現(2)文章類似的思路,先移動再插入
迭代器失效問題
如果insert的返回值是void,
void insert(iterator position, const value_type& val)
{assert(position >= start && position <= finish);if(finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);iterator i = finish-1;while (i >= position){*(i+1) = *i;i--;}*position = val;finish++;
}
頭插:
void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.insert(v.begin(), 3);return;
}
?
尾插:
void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.insert(v.end(), 3);return;
}
中間位置插入:
void test7()
{mystl::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.insert(v.begin() + 1, 4);return;
}
貌似沒有問題,但是如果是這個測試代碼:
void test7()
{mystl::vector<int> v;v.push_back(1);auto pos = v.begin();for (size_t i = 2; i <= 8; i++)v.insert(pos, i);return;
}
運行結果會出問題:?
引出迭代器失效問題
pos記錄的是原來v的start的值,如果v擴容,start的值會改變,但pos的值沒有更新,而且原先的內存空間被釋放會導致非法訪問,因此再執行v.insert(pos, i);就會出問題(即pos為野指針)
解決方法:擴容后更新pos的值,STL的解決方法:返回值為iterator
?
iterator insert(iterator position, const value_type& val)
{assert(position >= start && position <= finish);if(finish == nullptr)reserve(4);if (finish == end_of_storage)reserve(capacity() * 2);iterator i = finish-1;while (i >= position){*(i+1) = *i;i--;}*position = val;finish++;return start;
}
注:position不能引用傳參,有可能insert的第一個參數會做算術運算,例如:
?
v.insert(pos+20, i);
測試代碼:?
void test7()
{mystl::vector<int> v;v.push_back(1);auto pos = v.begin();for (size_t i = 2; i <= 8; i++)pos=v.insert(pos, i);return;
}
驗證pos是否更新:
原先:
擴容更新后:
運行結果:退出代碼為0
當然CD42.vector模擬實現(1)文章的push_back可以復用insert的代碼
1.如果不接收insert的返回值,擴容要慎重,修改可能會報錯,因為不一定擴容,所以不一定失效;
2.insert以后就不要使用原本定義的迭代器