操作系统:ubuntu10.04
STL源码版本:2.91
前言:
通过前面的两个章节,大概对stl的架构有个基础的了解,那么接下来应该怎么做呢:
应该从应用的角度,也就是最上层的应用,来看 list是如何被使用,在一步步深入。
1,list的接口:
1.1)list的各个接口的使用用例,请看:
c++ stl list使用总结
1.2)由上面可得,list的类定义为:
文件list是调用list接口的#include文件。
-
#ifndef __SGI_STL_LIST
-
#define __SGI_STL_LIST
-
-
#include <stl_algobase.h>
-
#include <stl_alloc.h>
-
#include <stl_construct.h>
-
#include <stl_uninitialized.h>
-
#include <stl_list.h>
-
-
#endif /* __SGI_STL_LIST */
1.2.1)list接口真正定义在
文件中
对于 typedef 在类中的定义有疑问的请看:c++的类中typedef的作用
-
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;
-
public:
-
typedef T value_type;
-
typedef value_type* pointer;
-
typedef const value_type* const_pointer;
-
typedef value_type& reference;
-
typedef const value_type& const_reference;
-
typedef list_node* link_type;
-
typedef size_t size_type;
-
typedef ptrdiff_t difference_type;
-
-
public:
-
typedef __list_iterator<T, T&, T*> iterator;
-
typedef __list_iterator<T, const T&, const T*> const_iterator;
-
-
typedef reverse_iterator<const_iterator> const_reverse_iterator;
-
typedef reverse_iterator<iterator> reverse_iterator;
-
-
protected:
-
link_type get_node() { return list_node_allocator::allocate(); }
-
void put_node(link_type p) { list_node_allocator::deallocate(p); }
-
-
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;
-
}
-
void destroy_node(link_type p) {
-
destroy(&p->data);
-
put_node(p);
-
}
-
-
protected:
-
void empty_initialize() {
-
node = get_node();
-
node->next = node;
-
node->prev = node;
-
}
-
-
void fill_initialize(size_type n, const T& value) {
-
empty_initialize();
-
__STL_TRY {
-
insert(begin(), n, value);
-
}
-
__STL_UNWIND(clear(); put_node(node));
-
}
-
-
template <class InputIterator>
-
void range_initialize(InputIterator first, InputIterator last) {
-
empty_initialize();
-
__STL_TRY {
-
insert(begin(), first, last);
-
}
-
__STL_UNWIND(clear(); put_node(node));
-
}
-
-
protected:
-
link_type node;
-
-
public:
-
list() { empty_initialize(); }
-
-
iterator begin() { return (link_type)((*node).next); }
-
const_iterator begin() const { return (link_type)((*node).next); }
-
iterator end() { return node; }
-
const_iterator end() const { return node; }
-
reverse_iterator rbegin() { return reverse_iterator(end()); }
-
const_reverse_iterator rbegin() const {
-
return const_reverse_iterator(end());
-
}
-
reverse_iterator rend() { return reverse_iterator(begin()); }
-
const_reverse_iterator rend() const {
-
return const_reverse_iterator(begin());
-
}
-
bool empty() const { return node->next == node; }
-
size_type size() const {
-
size_type result = 0;
-
distance(begin(), end(), result);
-
return result;
-
}
-
size_type max_size() const { return size_type(-1); }
-
reference front() { return *begin(); }
-
const_reference front() const { return *begin(); }
-
reference back() { return *(--end()); }
-
const_reference back() const { return *(--end()); }
-
void swap(list<T, Alloc>& x) { __STD::swap(node, x.node); }
-
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;
-
}
-
iterator insert(iterator position) { return insert(position, T()); }
-
-
template <class InputIterator>
-
void insert(iterator position, InputIterator first, InputIterator last);
-
-
void insert(iterator pos, size_type n, const T& x);
-
void insert(iterator pos, int n, const T& x) {
-
insert(pos, (size_type)n, x);
-
}
-
void insert(iterator pos, long n, const T& x) {
-
insert(pos, (size_type)n, x);
-
}
-
-
void push_front(const T& x) { insert(begin(), x); }
-
void push_back(const T& x) { insert(end(), x); }
-
iterator erase(iterator position) {
-
link_type next_node = link_type(position.node->next);
-
link_type prev_node = link_type(position.node->prev);
-
prev_node->next = next_node;
-
next_node->prev = prev_node;
-
destroy_node(position.node);
-
return iterator(next_node);
-
}
-
iterator erase(iterator first, iterator last);
-
void resize(size_type new_size, const T& x);
-
void resize(size_type new_size) { resize(new_size, T()); }
-
void clear();
-
-
void pop_front() { erase(begin()); }
-
void pop_back() {
-
iterator tmp = end();
-
erase(--tmp);
-
}
-
list(size_type n, const T& value) { fill_initialize(n, value); }
-
list(int n, const T& value) { fill_initialize(n, value); }
-
list(long n, const T& value) { fill_initialize(n, value); }
-
explicit list(size_type n) { fill_initialize(n, T()); }
-
-
#ifdef __STL_MEMBER_TEMPLATES
-
template <class InputIterator>
-
list(InputIterator first, InputIterator last) {
-
range_initialize(first, last);
-
}
-
-
list(const list<T, Alloc>& x) {
-
range_initialize(x.begin(), x.end());
-
}
-
~list() {
-
clear();
-
put_node(node);
-
}
-
list<T, Alloc>& operator=(const list<T, Alloc>& x);
-
-
protected:
-
void transfer(iterator position, iterator first, iterator last) {
-
if (position != last) {
-
(*(link_type((*last.node).prev))).next = position.node;
-
(*(link_type((*first.node).prev))).next = last.node;
-
(*(link_type((*position.node).prev))).next = first.node;
-
link_type tmp = link_type((*position.node).prev);
-
(*position.node).prev = (*last.node).prev;
-
(*last.node).prev = (*first.node).prev;
-
(*first.node).prev = tmp;
-
}
-
}
-
-
public:
-
void splice(iterator position, list& x) {
-
if (!x.empty())
-
transfer(position, x.begin(), x.end());
-
}
-
void splice(iterator position, list&, iterator i) {
-
iterator j = i;
-
++j;
-
if (position == i || position == j) return;
-
transfer(position, i, j);
-
}
-
void splice(iterator position, list&, iterator first, iterator last) {
-
if (first != last)
-
transfer(position, first, last);
-
}
-
void remove(const T& value);
-
void unique();
-
void merge(list& x);
-
void reverse();
-
void sort();
-
-
template <class Predicate> void remove_if(Predicate);
-
template <class BinaryPredicate> void unique(BinaryPredicate);
-
template <class StrictWeakOrdering> void merge(list&, StrictWeakOrdering);
-
template <class StrictWeakOrdering> void sort(StrictWeakOrdering);
-
-
friend bool operator== __STL_NULL_TMPL_ARGS (const list& x, const list& y);
-
};
2,空间配置器 allocate
在看class list的过程中,需要了解的第一个要点是 空间配置器 allocate,其实现内存的动态分配。
-
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)); }
-
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)); }
-
};
内存的真正的动态分配的实现在:
-
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
在ubuntu10.04中的gcc使用的宏定义中可知:
-
# ifdef __STL_PTHREADS
-
# include <pthread.h>
-
# define __NODE_ALLOCATOR_THREADS true
-
# endif
-
template <bool threads, int inst> //
-
class __default_alloc_template {
-
-
private:
-
static size_t ROUND_UP(size_t bytes) {
-
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
-
}
-
__PRIVATE:
-
union obj {
-
union obj * free_list_link;
-
char client_data[1]; /* The client sees this. */
-
};
-
private:
-
static obj * __VOLATILE free_list[__NFREELISTS];
-
-
static size_t FREELIST_INDEX(size_t bytes) {
-
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
-
}
-
-
// Returns an object of size n, and optionally adds to size n free list.
-
static void *refill(size_t n);
-
// Allocates a chunk for nobjs of size "size". nobjs may be reduced
-
// if it is inconvenient to allocate the requested number.
-
static char *chunk_alloc(size_t size, int &nobjs);
-
-
// Chunk allocation state.
-
static char *start_free;
-
static char *end_free;
-
static size_t heap_size;
-
-
static pthread_mutex_t __node_allocator_lock;
-
-
class lock {
-
public:
-
lock() { __NODE_ALLOCATOR_LOCK; }
-
~lock() { __NODE_ALLOCATOR_UNLOCK; }
-
};
-
friend class lock;
-
-
public:
-
-
/* n must be > 0 */
-
static void * allocate(size_t n)
-
{
-
obj * __VOLATILE * my_free_list;
-
obj * __RESTRICT result;
-
-
if (n > (size_t) __MAX_BYTES) {
-
return(malloc_alloc::allocate(n));
-
}
-
my_free_list = free_list + FREELIST_INDEX(n);
-
// Acquire the lock here with a constructor call.
-
// This ensures that it is released in exit or during stack
-
// unwinding.
-
-
lock lock_instance;
-
-
result = *my_free_list;
-
if (result == 0) {
-
void *r = refill(ROUND_UP(n));
-
return r;
-
}
-
*my_free_list = result -> free_list_link;
-
return (result);
-
};
-
-
/* p may not be 0 */
-
static void deallocate(void *p, size_t n)
-
{
-
obj *q = (obj *)p;
-
obj * __VOLATILE * my_free_list;
-
-
if (n > (size_t) __MAX_BYTES) {
-
malloc_alloc::deallocate(p, n);
-
return;
-
}
-
my_free_list = free_list + FREELIST_INDEX(n);
-
// acquire lock
-
-
/*REFERENCED*/
-
lock lock_instance;
-
-
q -> free_list_link = *my_free_list;
-
*my_free_list = q;
-
// lock is released here
-
}
-
-
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
-
-
} ;
malloc_alloc定义如下:
-
typedef __malloc_alloc_template<0> malloc_alloc;
-
template <int inst>
-
class __malloc_alloc_template {
-
-
private:
-
-
static void *oom_malloc(size_t);
-
-
static void *oom_realloc(void *, size_t);
-
-
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
-
static void (* __malloc_alloc_oom_handler)();
-
#endif
-
-
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 /* n */)
-
{
-
free(p);
-
}
-
-
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
-
{
-
void * result = realloc(p, new_sz);
-
if (0 == result) result = oom_realloc(p, new_sz);
-
return result;
-
}
-
-
static void (* set_malloc_handler(void (*f)()))()
-
{
-
void (* old)() = __malloc_alloc_oom_handler;
-
__malloc_alloc_oom_handler = f;
-
return(old);
-
}
-
-
};
3,__list_node的定义:
-
template <class T>
-
struct __list_node {
-
typedef void* void_pointer;
-
void_pointer next;
-
void_pointer prev;
-
T data;
-
};
4,__list_iterator的定义:
-
template<class T, class Ref, class Ptr>
-
struct __list_iterator {
-
typedef __list_iterator<T, T&, T*> iterator;
-
typedef __list_iterator<T, const T&, const T*> const_iterator;
-
typedef __list_iterator<T, Ref, Ptr> self;
-
-
typedef bidirectional_iterator_tag iterator_category;
-
typedef T value_type;
-
typedef Ptr pointer;
-
typedef Ref reference;
-
typedef __list_node<T>* link_type;
-
typedef size_t size_type;
-
typedef ptrdiff_t difference_type;
-
-
link_type node;
-
-
__list_iterator(link_type x) : node(x) {}
-
__list_iterator() {}
-
__list_iterator(const iterator& x) : node(x.node) {}
-
-
bool operator==(const self& x) const { return node == x.node; }
-
bool operator!=(const self& x) const { return node != x.node; }
-
reference operator*() const { return (*node).data; }
-
-
pointer operator->() const { return &(operator*()); }
-
-
self& operator++() {
-
node = (link_type)((*node).next);
-
return *this;
-
}
-
self operator++(int) {
-
self tmp = *this;
-
++*this;
-
return tmp;
-
}
-
self& operator--() {
-
node = (link_type)((*node).prev);
-
return *this;
-
}
-
self operator--(int) {
-
self tmp = *this;
-
--*this;
-
return tmp;
-
}
-
};
阅读(6995) | 评论(1) | 转发(3) |