最簡單的sgi vector竟然寫了四五天。

這次編寫所暴露的問題是：

1. 一定要單元測試，否則在最后差錯的時候會崩潰的

2. 寫代碼一定要仔細，記住，要bugfree

ccconstruct.h

#ifndef C_CONSTRUCT_H #define C_CONSTRUCT_H #include <iostream> #include <new.h>inline void destroy(char *, char *){} inline void destroy(int *, int *){} inline void destroy(long *, long *){} inline void destroy(float *, float *){} inline void destroy(double *, double *){}//對于int* p，也可以調用這個函數，比較怪異 template <class T> inline void destroy(T* pointer) {pointer->~T(); }template <class ForwardIterator> inline void destroy(ForwardIterator first, ForwardIterator last) {for (; first < last ; ++first)destroy(first); }template <class T1, class T2> inline void construct(T1* p, const T2& value) {new (p) T1(value); }#endif
calloc.h

#ifndef C_ALLOC_H #define C_ALLOC_H #include <stdio.h> #include <stdlib.h>enum {ALIGN = 8};// enum {MAX_BYTES = 128}; enum {NFREELISTS = 16};#define __THROW_BAD_ALLOC std::cerr << "out of memory " <<std::endl; exit(1) //第一級配置器 template <int inst>//這個模板參數在單線程中沒有用，主要用于多線程。__malloc_alloc_template<0>,__malloc_alloc_template<1>就實例化出兩個不同的類，可以用于兩個不同的線程中，這樣既不用加鎖也不會減速 class __malloc_alloc_template { private://oom: out of memorystatic void * oom_malloc( size_t);static void * oom_realloc(void *, size_t);static void (* __malloc_alloc_oom_handler )();//這是個函數指針，是一個成員變量，而不是成員函數public:static void * allocate (size_t n) {void * result = malloc(n);if (0 == result) result == oom_malloc(n);return result;}static void deallocate(void *p, size_t) {free(p);}static void *reallocate(void *p, size_t /*old size*/, size_t new_sz) {void *result = realloc(p,new_sz);if (0 == result) return oom_realloc(p, new_sz);return result;}static void (* set_malloc_handler (void (*f)())) () { //set_malloc_handler是一個函數，其參數是一個函數指針，其返回值也是一個函數指針。這地方要好好揣摩。如果將set_malloc_handler (void (*f)()) 看做p,則就是 (*p)(),set_malloc_handler的返回值就是pvoid (* old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler == f;return old;}};template<int inst> void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler) () = 0;template <int inst> void * __malloc_alloc_template<inst>::oom_malloc(size_t n) {void (* my_malloc_handler) ();void *result;for(;;) {my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {__THROW_BAD_ALLOC;}(*my_malloc_handler) ();//如果用戶自定義處理函數，則此函數會尋找可用的內存，并釋放這個內存result = malloc(n);//再重新嘗試配置內存if (result) return result;} }template <int inst> void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) {void (* my_malloc_handler) ();void * result;for (;;) {my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler) {__THROW_BAD_ALLOC;}(*my_malloc_handler) ();result = realloc(p, n);if (result) return result;} }typedef __malloc_alloc_template<0> malloc_alloc; //第二級配置器template <bool threads, int inst> class __default_alloc_template { private://bytes上調至8的倍數static size_t ROUND_UP(size_t bytes) {return ( (bytes + ALIGN -1) & ~(ALIGN - 1));}private:union obj {union obj * free_list_link;}; private:static obj * free_list[NFREELISTS];static size_t FREELIST_INDEX(size_t bytes) {return ( (bytes + ALIGN -1)/ALIGN -1);}//當freelist中沒有大小為n個塊，調用此函數，會返回從內存池中返回若干個塊，將其中的一個返回，將剩余的放入freelist中static void *refill(size_t n);//從內存池中分配一大塊空間，大小為nobjs個大小為 size的塊，如果內存不足，nobjs會減小static char *chunk_alloc(size_t size, int &nobjs);static char *start_free;//內存池起始位置static char *end_free;//內存池結束位置static size_t heap_size;//一個不太重要的變量public:static void * allocate(size_t n) {obj ** my_free_list;obj * result;if (n > MAX_BYTES) return (malloc_alloc::allocate(n));my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0) {void *r = refill(ROUND_UP(n));return r;}*my_free_list = result->free_list_link;return result;}static void deallocate(void *p, size_t n) {obj * q = (obj *) p;obj ** my_free_list;if (n >MAX_BYTES) {//對于大塊就free,對于小塊是要回收到freelist中，以備再次使用malloc_alloc::deallocate(p,n);return;}my_free_list = free_list + FREELIST_INDEX(n);q->free_list_link = *my_free_list;*my_free_list = q;}static void * reallocate(void *p, size_t old_sz, size_t new_sz) {void * result;size_t copy_sz;if (old_sz > MAX_BYTES && new_sz > MAX_BYTES) {return (malloc_alloc::reallocate(p,old_sz, new_sz));}if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;result = allocate(new_sz);copy_sz = new_sz > old_sz ? old_sz : new_sz;memcpy(result, p , copy_sz);deallocate(p, old_sz);return result;} };template<bool threads, int inst> void * __default_alloc_template<threads,inst>::refill(size_t n) {int nobjs = 20;char *chunk = chunk_alloc(n, nobjs);obj ** my_free_list;obj * result;obj * current_obj, * next_obj;int i;if (1 == nobjs) return chunk;my_free_list = free_list + FREELIST_INDEX(n);result = (obj *)chunk;*my_free_list = next_obj = (obj *)(chunk + n);for (int i = 1;; ++i) {current_obj = next_obj;next_obj = (obj *)((char *)next_obj + n);if (i == nobjs - 1) {current_obj->free_list_link = NULL;break;}current_obj->free_list_link = next_obj;}return result; }template<bool threads, int inst> char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs) {char * result;size_t total_bytes = size * nobjs;size_t bytes_left = end_free - start_free;if (bytes_left >= total_bytes) {result = start_free;start_free += total_bytes;return result;}else if (bytes_left >= size){//至少能提供一個塊result = start_free;nobjs = bytes_left / size;total_bytes = size * nobjs;start_free += total_bytes;return result;}else {size_t bytes_to_get = 2 * total_bytes +ROUND_UP(heap_size >> 4);//ROUND_UP(heap_size >> 4)作用不大if (bytes_left >0) {obj ** my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free)->free_list_link = *my_free_list;*my_free_list = (obj *)start_free;}start_free = (char *)malloc(bytes_to_get);if (0 == start_free) {//沒有多余內存，需要從freelist中找到塊int i;obj ** my_free_list, *p;for (i = size; i < MAX_BYTES; i += ALIGN) {my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;if (0 != p) {*my_free_list = p->free_list_link;start_free = (char *)p;end_free = start_free + i;return chunk_alloc(size,nobjs);}}end_free = 0;start_free = (char *)malloc_alloc::allocate(bytes_to_get);}heap_size += bytes_to_get;end_free = start_free + bytes_to_get;return chunk_alloc(size, nobjs);} }template<bool threads, int inst> char *__default_alloc_template<threads, inst>::start_free = 0;template<bool threads, int inst> char *__default_alloc_template<threads, inst>::end_free = 0;template<bool threads, int inst> size_t __default_alloc_template<threads, inst>::heap_size = 0;//注意一定要有typename告訴編譯器，這個模板類肯定有這個類型obj template<bool threads, int inst> typename __default_alloc_template<threads, inst>::obj * __default_alloc_template<threads, inst>::free_list[NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };typedef __default_alloc_template<false, 0> alloc;template<class T, class Alloc> class simple_alloc { public://返回n個T大小的內存static T *allocate(size_t n) {return 0 == n ? 0 : (T *) Alloc::allocate(n * sizeof(T));}static T *allocate() {return (T *) Alloc::allocate(sizeof(T));}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));} };#endif
cvector.h

#ifndef C_VECTOR_H #define C_VECTOR_H#include "calloc.h" //#include "stl_construct.h" #include <iostream> #include <memory> #include "cconstruct.h"using namespace std;template <class T, class Alloc = alloc> class cvector { public:typedef T value_type;typedef value_type* pointer;typedef value_type* iterator;typedef value_type& reference;typedef const value_type* const_iterator;protected:typedef simple_alloc<value_type, Alloc> data_allocator;iterator start;iterator finish;iterator end_of_storage;void insert_aux(iterator position, const T& x);//這僅是釋放vector所占內存,不是析構函數void deallocate() {if (start)data_allocator::deallocate(start, end_of_storage - start);}iterator allocate_and_fill(size_t n, const T& x) {iterator result = data_allocator::allocate(n);//獲得生內存uninitialized_fill_n(result, n, x);//uninitialized_* 之類的函數都是用于生內存的操作，效率較高return result;}void fill_initialize(size_t n, const T& value) {start = uninitialized_fill_n(n, value);finish = start + n;end_of_storage = finish;}iterator allocate_and_copy(size_t n, const_iterator first, const_iterator last) {iterator result = data_allocator::allocate(n);uninitialized_copy(first, last, result);return result;}public:iterator begin() { return start; }iterator end() { return finish; }size_t size() const { return finish - start; }size_t capacity() const { return end_of_storage - start; }bool empty() const { return start == finish; }reference operator [] (size_t n) { return *(start + n);}cvector() :start(0), finish(0), end_of_storage(0) {}cvector(size_t n, const T& x) { fill_initialize(n,x); }explicit cvector(size_t n) { fill_initialize(n, T()); }cvector(cvector<T, Alloc>& x) {start = allocate_and_copy(x.size(), x.begin(), x.end());finish = end_of_storage = start + x.size();}void swap(cvector<T, Alloc>& x) {std::swap(start, x.start);std::swap(finish, x.finish);std::swap(end_of_storage, x.end_of_storage);}void insert(iterator position, size_t n, const T& x);void resize(size_t new_sz, const T& x) {if (new_sz < size()) {erase(begin() + new_sz, end());}elseinsert(end(), new_sz - size(), x);}cvector<T, Alloc>& operator=(const cvector<T, Alloc>& x);void resize(size_t new_sz) {resize(new_sz, T());}~cvector() {destroy(start, finish);deallocate();}reference front() { return *start; }reference back() { return *(finish - 1);}void push_back(const T& x) {if (finish != end_of_storage) {construct(finish, x);++finish;}else {insert_aux(end(), x);}}iterator insert(iterator position, const T& x) {size_t n = position - start;if (finish != end_of_storage && position == finish()) {construct(finish, x);++finish;}elseinsert_aux(position, x);return begin() + n;}void pop_back() {--finish;destroy(finish);}iterator erase(iterator position) {if (position + 1 != finish)copy(position+1, finish, position);--finish;destroy(finish);return position;}iterator erase(iterator b, iterator e) { iterator i = copy(e, finish, b);destroy(i, finish);finish -= e - b;return b;}void clear() {erase(start, finish);}};template <class T, class Alloc> inline bool operator==(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return (x.size() == y.size()) && (equal(x.begin(), x.end(), y.begin())); }template <class T, class Alloc> inline bool operator<(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return lexicographical_compare(x.begin(), x.end(),y.begin(), y.end()); }template <class T, class Alloc> inline bool operator!=(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return !(x == y); }template <class T, class Alloc> inline bool operator>(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return y < x; }template <class T, class Alloc> inline bool operator<=(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return !(y < x); }template <class T, class Alloc> inline bool operator>=(const cvector<T, Alloc>& x, const cvector<T, Alloc>& y) {return !(x < y); }template<class T, class Alloc> cvector<T, Alloc>& cvector<T, Alloc>::operator=(const cvector<T,Alloc> &x) {if (&x != this) {size_t len = x.size();if (len > capacity()) {iterator tmp = allocate_and_copy(len, x.begin(), x.end());destroy(start, finish);deallocate();start = tmp;finish = start + len;end_of_storage = finish;}else if (size() >= len) {iterator tmp = copy(x.begin(), x.end(), start);erase(tmp, end());finish = tmp;}else {finish = copy(x.begin(), x.begin() + size(), start);finish = uninitialized_copy(x.begin() + size(), x.end(), finish);}} }template<class T, class Alloc> void cvector<T,Alloc>::insert_aux(iterator position, const T &x) {if (finish != end_of_storage) {//這里要考慮為什么不直接copy_backward(position, finish, finish+1)//這是因為原vector的最后一個元素要向后移動一個地址，而這個新的地址上沒有對象，所以直接construct就行了，這樣效率最高，就只有這個新地址不需要析構construct(finish, *(finish - 1));++finish;copy_backward(position, finish - 2, finish - 1);*position = x;}else {size_t old_sz = size();size_t len = old_sz !=0 ? 2 * old_sz : 1;iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;try {new_finish = uninitialized_copy(start, position, new_start);construct(new_finish, x);++new_finish;new_finish = uninitialized_copy(position , finish, new_finish);}catch (...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}destroy(begin(), end());deallocate();start = new_start;finish = new_finish;end_of_storage = start + len;} }template<class T, class Alloc> void cvector<T, Alloc>::insert(iterator position, size_t n, const T &x) {if (n != 0) {if (end_of_storage - finish >= n) {size_t elems_after = finish - position;iterator old_finish = finish;if (elems_after > n) {uninitialized_copy(finish - n, finish, finish);finish += n;copy_backward(position, old_finish - n, old_finish);fill(position, position + n, x);}else {uninitialized_fill_n(finish, n - elems_after, x);finish += n - elems_after;uninitialized_copy(position,old_finish, finish);finish += elems_after;fill(position, old_finish, x);}}else {size_t old_sz = size();size_t len = old_sz + max(old_sz, n);iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;new_finish = uninitialized_copy(begin(), position, new_start);uninitialized_fill_n(new_finish, n, x);new_finish += n;new_finish = uninitialized_copy(position, end(), new_finish);destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = start + len;}} }#endif

測試代碼：

cvector<term> vec;for (int i = 0; i < 1; ++i)vec.push_back(term("aa",i));
class term { public:string a;int b;term(const string& str, int c):a(str), b(c){}};

sizeof(term)的大小是36

push_back第一個時，這時就從內存池里申請了20個40byte的塊，一塊返回作為vector的一個元素，另外19個串成單鏈表放入freelist[4]中

push_back第二個時，將40byte的塊返還freelist，從內存池中申請20個72byte的塊，一塊返回作為vector的一個元素，另外19個串成單鏈表放入freelist[4]中

當元素較多時，就不再用freelist中的塊，這時就是，用多少，就malloc多少內存，這時因為vector是連續地址的，所以要找一個連續的內存塊

注意，erase，pop_back都不會減少vector所占內存。

當vector被析構時，先依存析構元素，最后再處理vector所占內存。如果這塊內存比較小，小于等于128，則還是返還給freelist；如果內存塊大于128，就直接釋放這塊內存

stl有一個比較好的思想，就是stl所有容器的內存分配都是用同一個freelist和內存池，這樣就減少了內存碎片和頻繁申請內存和釋放內存的費時操作

但是這樣會有一個副作用，就是程序在長時間的運行中，freelist所帶的內存塊可能會很多很多，就很占用系統資源，這些內存塊又不能主動釋放

sgi stl的二級配置器的工作原理是：

如果用戶申請的內存>=128，調用第一級配置器，也就是malloc 和free

否則，用二級配置器。

二級配置器，有一個freelist和一個內存池。freelist是一個具有16個元素的數組，每個元素就是一條空閑塊的鏈表，每條鏈表中的空閑塊大小一致，而相鄰鏈表中的空閑塊大小相差2倍

如果用戶free的內存塊大小小于128，就插入到對應freelist的鏈表的表頭

如果用戶申請的內存塊小于128，并且對應的鏈表有空閑塊，就直接返回此內存塊。如果此鏈表沒有空閑塊了，則就向內存池申請20個內存塊，返回一個給用戶，剩下的19個連接成對應的鏈表。但是，如果內存池空間不足，可能申請不到20個內存塊，但內存池的剩余空間至少能供應一個塊，同樣返回。

如果，內存池空間一個塊都不能供應了，那就通過malloc獲取40個內存塊大小的空間，將20個返回，剩下的空間留在內存池，供下次使用。

如果內存空間已經用盡，malloc也不能獲取內存了，那么就要查看freelist中的空閑塊，設用戶申請的內存大小為p, 那么先查看大于p的最小塊所在的鏈表是否為空，不為空，就將這個內存塊放入內存池中，否則，就查看更大的塊所在的鏈表

總結

以上是生活随笔為你收集整理的sgi 之vector的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。