stl原始碼學習(版本2.91)--list
一，閱讀list()建構式的識訓
1，默認建構式的作用和被呼叫的時機
struct no{
no(int i){}
//no(){
// std::cout << "s" << std::endl;
//}
long data;
};
struct A{
no n;
};
int main(){
A a;
}
這段代碼報錯，提示無法構造A類的a物件，編譯器會給A類提供默認建構式，但是A類的默認建構式去構造它成員no類的n時，發現no類沒有建構式（理由：因為自己定義了no(int)建構式，所以編譯器就不提供no類的默認建構式了），所以就無法構造n物件，也就無法構造a物件了，
知識點：
- 如果類沒有自己提供建構式，則編譯器會提供一個默認建構式
- 當類A里的成員里有類成員b時，當構造A時，就會去找b的建構式，如果類b有建構式或者默認建構式則構造b成功，
1.cpp: In function ‘int main()’:
1.cpp:22:5: error: use of deleted function ‘A::A()’
A a;
^
1.cpp:12:8: note: ‘A::A()’ is implicitly deleted because the default definition would be ill-formed:
2，allocator和定位new的用法
- allocator：用于開辟記憶體空間，但是不呼叫建構式
- 定位new：不開辟記憶體空間，只呼叫建構式
stl_list.h原始碼節選
template <class T>
struct __list_node {
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
T data;
};
template <class T, class Alloc = alloc>
class list {
protected:
typedef __list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
public:
typedef list_node* link_type;
protected:
link_type node;//list唯一的成員，是end()函式的回傳值
public:
list() { empty_initialize(); }
protected:
void empty_initialize() {
node = get_node();
node->next = node;
node->prev = node;
}
protected:
link_type get_node() { return list_node_allocator::allocate(); }
link_type create_node(const T& x) {
link_type p = get_node();
__STL_TRY {
construct(&p->data, x);
}
__STL_UNWIND(put_node(p));
return p;
}
S
iterator insert(iterator position, const T& x) {
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
stl_alloc.h
template<class T, class Alloc>
class simple_alloc {
public:
static T *allocate(size_t n)
{ return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
stl_construct.h
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
從以上的stl list原始碼可以看出：
- list的建構式list()，只開辟了node的記憶體空間，并沒有構造node里的data物件，理由：這個node的哨兵node不是list里保存資料的節點，
- 但呼叫insert方法時，會呼叫create_node，這里面既開辟了節點的記憶體空間（通過呼叫get_node();）又呼叫了節點里data的構造方法（通過呼叫construct(&p->data, x);），然后在construct里使用了定位new(new (p) T1(value)??
- stl里開辟空間和構造物件是分開的
- stl里使用專用的allocator類來開辟空間
二，閱讀list()解構式的識訓
- 釋放節點的方法：
- 先呼叫節點里元素的析構方法（pointer->~T();）
- 在釋放節點的空間（Alloc::deallocate(p, sizeof (T));）
stl_list.h原始碼節選
public:
~list() {
clear();//釋放list里存的元素的空間
put_node(node);//釋放list的唯一的node成員變數的空間
}
void clear();
protected:
//呼叫list_node_allocator的static的deallocate方法，釋放空間
//list_node_allocator是simple_alloc<list_node, Alloc>
void put_node(link_type p) { list_node_allocator::deallocate(p); }
template <class T, class Alloc = alloc>
class list {
protected:
typedef void* void_pointer;
typedef __list_node<T> list_node;
typedef simple_alloc<list_node, Alloc> list_node_allocator;
//使用方法destroy，來呼叫節點里data物件的析構方法，并使用方法put_node釋放這個節點的空間
void destroy_node(link_type p) {
destroy(&p->data);//destroy是個inline方法，定義在下面的stl_construct.h
put_node(p);
}
template <class T, class Alloc>
void list<T, Alloc>::clear()
{
//得到第一個節點
link_type cur = (link_type) node->next;
//從第一個節點開始，依次釋放每個節點
while (cur != node) {
link_type tmp = cur;
cur = (link_type) cur->next;
destroy_node(tmp);
}
//形成環形佇列，讓node的前后節點都指向它自己
node->next = node;
node->prev = node;
}
stl_alloc.h
template<class T, class Alloc>
class simple_alloc {
static void deallocate(T *p, size_t n)
{ if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
stl_construct.h
template <class T>
inline void destroy(T* pointer) {
pointer->~T();
}
三，由寫erase函式發生的Segmentation fault錯誤，產生的反省
erase函式代碼如下：
template<typename T, typename Alloc>
typename list<T, Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last){
//for( ; first != last; ++first) erase(first);//--------①
while(first != last) erase(first++);//------------------②
return iterator(last);
}
template<typename T, typename Alloc>
typename list<T, Alloc>::iterator list<T, Alloc>::erase(iterator position){
link_type n = position.node->next;
link_type p = position.node->prev;
p->next = n;
n->prev = p;
destroy_node(position.node);
return iterator(n);
}
//下面是iterator的++i和i++的運算子多載
//iterator類里只有一個成員變數node
//++i
self& operator++() {
node = node->next;//------③
return *this;
}
//i++
self operator++(int){
self tmp = *this;
++*this;
return tmp;
}
bool operator!=(const self & x){ return node != x.node; }
1，如果打開①處的注釋，就會發生Segmentation fault錯誤，
- 錯誤原因：第一次執行erase(first)后，first里的node指向的空間已經被釋放了，所以first.node指向一個不明區域，變成了一個野指標；然后執行++first，也就是類iterator的多載運算子前++方法，也就是執行到了③處，node本身就是first.node，已經是野指標了，所以node->next就導致了Segmentation fault錯誤，
2，注釋掉①處的代碼，使用②處的代碼，就能夠正確處理了，
- 變正確的原因：釋放first.node之前，已經讓first.node指向了first.node->next了.
四，通過list的size方法，了解了iterator_traits技術
stl標準庫 iterator_traits
c/c++ 學習互助QQ群：877684253
本人微信：xiaoshitou5854
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/89853.html
標籤：C++