备注:
本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者。
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。
为了降低学习难度,作者这里换到了SGI-STL-2.91.57的源码来学习,代码下载地址为【 http://jjhou.boolan.com/jjwbooks-tass.htm 】
如果我们需要存储很多位值时,我们可以使用bvector或者bitset【 http://www.cplusplus.com/reference/bitset/bitset/ 】,这里简单的笔记下bvector的代码实现:
stl_bvector.h:
__bit_reference(unsigned int * x, unsigned int y) : p(x), mask(y) {} |
__bit_reference() : p(0), mask(0) {} |
operator bool () const { return !(!(*p & mask)); } |
__bit_reference& operator=( bool x) { |
__bit_reference& operator=( const __bit_reference& x) { return * this = bool (x); } |
bool operator==( const __bit_reference& x) const { |
return bool (* this ) == bool (x); |
bool operator<( const __bit_reference& x) const { |
return bool (* this ) < bool (x); |
void flip() { *p ^= mask; } |
inline void swap(__bit_reference x, __bit_reference y) { |
struct __bit_iterator : public random_access_iterator< bool , ptrdiff_t > { |
typedef __bit_reference reference; |
typedef __bit_reference* pointer; |
typedef __bit_iterator iterator; |
if (offset++ == __WORD_BIT - 1) { |
__bit_iterator() : p(0), offset(0) {} |
__bit_iterator(unsigned int * x, unsigned int y) : p(x), offset(y) {} |
reference operator*() const { return reference(p, 1U << offset); } |
iterator operator++( int ) { |
iterator operator--( int ) { |
iterator& operator+=(difference_type i) { |
difference_type n = i + offset; |
offset = (unsigned int ) n + __WORD_BIT; |
offset = (unsigned int ) n; |
iterator& operator-=(difference_type i) { |
iterator operator+(difference_type i) const { |
iterator operator-(difference_type i) const { |
difference_type operator-(iterator x) const { |
return __WORD_BIT * (p - x.p) + offset - x.offset; |
reference operator[](difference_type i) { return *(* this + i); } |
bool operator==( const iterator& x) const { |
return p == x.p && offset == x.offset; |
bool operator!=( const iterator& x) const { |
return p != x.p || offset != x.offset; |
bool operator<(iterator x) const { |
return p < x.p || (p == x.p && offset < x.offset); |
struct __bit_const_iterator |
: public random_access_iterator< bool , ptrdiff_t > |
typedef bool const_reference; |
typedef const bool * pointer; |
typedef __bit_const_iterator const_iterator; |
if (offset++ == __WORD_BIT - 1) { |
__bit_const_iterator() : p(0), offset(0) {} |
__bit_const_iterator(unsigned int * x, unsigned int y) : p(x), offset(y) {} |
__bit_const_iterator( const __bit_iterator& x) : p(x.p), offset(x.offset) {} |
const_reference operator*() const { |
return __bit_reference(p, 1U << offset); |
const_iterator& operator++() { |
const_iterator operator++( int ) { |
const_iterator tmp = * this ; |
const_iterator& operator--() { |
const_iterator operator--( int ) { |
const_iterator tmp = * this ; |
const_iterator& operator+=(difference_type i) { |
difference_type n = i + offset; |
offset = (unsigned int ) n + __WORD_BIT; |
offset = (unsigned int ) n; |
const_iterator& operator-=(difference_type i) { |
const_iterator operator+(difference_type i) const { |
const_iterator tmp = * this ; |
const_iterator operator-(difference_type i) const { |
const_iterator tmp = * this ; |
difference_type operator-(const_iterator x) const { |
return __WORD_BIT * (p - x.p) + offset - x.offset; |
const_reference operator[](difference_type i) { |
bool operator==( const const_iterator& x) const { |
return p == x.p && offset == x.offset; |
bool operator!=( const const_iterator& x) const { |
return p != x.p || offset != x.offset; |
bool operator<(const_iterator x) const { |
return p < x.p || (p == x.p && offset < x.offset); |
#if defined(__STL_CLASS_PARTIAL_SPECIALIZATION) && !defined(__STL_NEED_BOOL) |
#define __SGI_STL_VECBOOL_TEMPLATE |
#undef __SGI_STL_VECBOOL_TEMPLATE |
#define __BVECTOR bit_vector |
# ifdef __SGI_STL_VECBOOL_TEMPLATE |
template < class Alloc> class vector< bool , Alloc> |
# else /* __SGI_STL_VECBOOL_TEMPLATE */ |
# endif /* __SGI_STL_VECBOOL_TEMPLATE */ |
# ifdef __SGI_STL_VECBOOL_TEMPLATE |
typedef simple_alloc<unsigned int , Alloc> data_allocator; |
# else /* __SGI_STL_VECBOOL_TEMPLATE */ |
typedef simple_alloc<unsigned int , alloc> data_allocator; |
# endif /* __SGI_STL_VECBOOL_TEMPLATE */ |
typedef size_t size_type; |
typedef ptrdiff_t difference_type; |
typedef __bit_reference reference; |
typedef bool const_reference; |
typedef __bit_reference* pointer; |
typedef const bool * const_pointer; |
typedef __bit_iterator iterator; |
typedef __bit_const_iterator const_iterator; |
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION |
typedef reverse_iterator<const_iterator> const_reverse_iterator; |
typedef reverse_iterator<iterator> reverse_iterator; |
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
typedef reverse_iterator<const_iterator, value_type, const_reference, |
difference_type> const_reverse_iterator; |
typedef reverse_iterator<iterator, value_type, reference, difference_type> |
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ |
unsigned int * end_of_storage; |
unsigned int * bit_alloc(size_type n) { |
return data_allocator::allocate((n + __WORD_BIT - 1)/__WORD_BIT); |
data_allocator::deallocate(start.p, end_of_storage - start.p); |
void initialize(size_type n) { |
unsigned int * q = bit_alloc(n); |
end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; |
finish = start + difference_type(n); |
void insert_aux(iterator position, bool x) { |
if (finish.p != end_of_storage) { |
copy_backward(position, finish, finish + 1); |
size_type len = size() ? 2 * size() : __WORD_BIT; |
unsigned int * q = bit_alloc(len); |
iterator i = copy(begin(), position, iterator(q, 0)); |
finish = copy(position, end(), i); |
end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
void initialize_range(InputIterator first, InputIterator last, |
for ( ; first != last; ++first) |
template < class ForwardIterator> |
void initialize_range(ForwardIterator first, ForwardIterator last, |
distance(first, last, n); |
copy(first, last, start); |
template < class InputIterator> |
void insert_range(iterator pos, |
InputIterator first, InputIterator last, |
for ( ; first != last; ++first) { |
pos = insert(pos, *first); |
template < class ForwardIterator> |
void insert_range(iterator position, |
ForwardIterator first, ForwardIterator last, |
distance(first, last, n); |
if (capacity() - size() >= n) { |
copy_backward(position, end(), finish + difference_type(n)); |
copy(first, last, position); |
finish += difference_type(n); |
size_type len = size() + max(size(), n); |
unsigned int * q = bit_alloc(len); |
iterator i = copy(begin(), position, iterator(q, 0)); |
i = copy(first, last, i); |
finish = copy(position, end(), i); |
end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; |
#endif /* __STL_MEMBER_TEMPLATES */ |
iterator begin() { return start; } |
const_iterator begin() const { return start; } |
iterator end() { return finish; } |
const_iterator end() const { return finish; } |
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()); |
size_type size() const { return size_type(end() - begin()); } |
size_type max_size() const { return size_type(-1); } |
size_type capacity() const { |
return size_type(const_iterator(end_of_storage, 0) - begin()); |
bool empty() const { return begin() == end(); } |
reference operator[](size_type n) { |
return *(begin() + difference_type(n)); |
const_reference operator[](size_type n) const { |
return *(begin() + difference_type(n)); |
__BVECTOR() : start(iterator()), finish(iterator()), end_of_storage(0) {} |
__BVECTOR(size_type n, bool value) { |
fill(start.p, end_of_storage, value ? ~0 : 0); |
__BVECTOR( int n, bool value) { |
fill(start.p, end_of_storage, value ? ~0 : 0); |
__BVECTOR( long n, bool value) { |
fill(start.p, end_of_storage, value ? ~0 : 0); |
explicit __BVECTOR(size_type n) { |
fill(start.p, end_of_storage, 0); |
__BVECTOR( const __BVECTOR& x) { |
copy(x.begin(), x.end(), start); |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> |
__BVECTOR(InputIterator first, InputIterator last) { |
initialize_range(first, last, iterator_category(first)); |
#else /* __STL_MEMBER_TEMPLATES */ |
__BVECTOR(const_iterator first, const_iterator last) { |
distance(first, last, n); |
copy(first, last, start); |
__BVECTOR( const bool * first, const bool * last) { |
distance(first, last, n); |
copy(first, last, start); |
#endif /* __STL_MEMBER_TEMPLATES */ |
~__BVECTOR() { deallocate(); } |
__BVECTOR& operator=( const __BVECTOR& x) { |
if (&x == this ) return * this ; |
if (x.size() > capacity()) { |
copy(x.begin(), x.end(), begin()); |
finish = begin() + difference_type(x.size()); |
void reserve(size_type n) { |
unsigned int * q = bit_alloc(n); |
finish = copy(begin(), end(), iterator(q, 0)); |
end_of_storage = q + (n + __WORD_BIT - 1)/__WORD_BIT; |
reference front() { return *begin(); } |
const_reference front() const { return *begin(); } |
reference back() { return *(end() - 1); } |
const_reference back() const { return *(end() - 1); } |
if (finish.p != end_of_storage) |
void swap(__BVECTOR& x) { |
__STD::swap(start, x.start); |
__STD::swap(finish, x.finish); |
__STD::swap(end_of_storage, x.end_of_storage); |
iterator insert(iterator position, bool x = bool ()) { |
difference_type n = position - begin(); |
if (finish.p != end_of_storage && position == end()) |
#ifdef __STL_MEMBER_TEMPLATES |
template < class InputIterator> void insert(iterator position, |
insert_range(position, first, last, iterator_category(first)); |
#else /* __STL_MEMBER_TEMPLATES */ |
void insert(iterator position, const_iterator first, |
if (first == last) return ; |
distance(first, last, n); |
if (capacity() - size() >= n) { |
copy_backward(position, end(), finish + n); |
copy(first, last, position); |
size_type len = size() + max(size(), n); |
unsigned int * q = bit_alloc(len); |
iterator i = copy(begin(), position, iterator(q, 0)); |
i = copy(first, last, i); |
finish = copy(position, end(), i); |
end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; |
void insert(iterator position, const bool * first, const bool * last) { |
if (first == last) return ; |
distance(first, last, n); |
if (capacity() - size() >= n) { |
copy_backward(position, end(), finish + n); |
copy(first, last, position); |
size_type len = size() + max(size(), n); |
unsigned int * q = bit_alloc(len); |
iterator i = copy(begin(), position, iterator(q, 0)); |
i = copy(first, last, i); |
finish = copy(position, end(), i); |
end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; |
#endif /* __STL_MEMBER_TEMPLATES */ |
void insert(iterator position, size_type n, bool x) { |
if (capacity() - size() >= n) { |
copy_backward(position, end(), finish + difference_type(n)); |
fill(position, position + difference_type(n), x); |
finish += difference_type(n); |
size_type len = size() + max(size(), n); |
unsigned int * q = bit_alloc(len); |
iterator i = copy(begin(), position, iterator(q, 0)); |
finish = copy(position, end(), i + difference_type(n)); |
end_of_storage = q + (len + __WORD_BIT - 1)/__WORD_BIT; |
void insert(iterator pos, int n, bool x) { insert(pos, (size_type)n, x); } |
void insert(iterator pos, long n, bool x) { insert(pos, (size_type)n, x); } |
void pop_back() { --finish; } |
iterator erase(iterator position) { |
if (position + 1 != end()) |
copy(position + 1, end(), position); |
iterator erase(iterator first, iterator last) { |
finish = copy(last, end(), first); |
void resize(size_type new_size, bool x = bool ()) { |
erase(begin() + difference_type(new_size), end()); |
insert(end(), new_size - size(), x); |
void clear() { erase(begin(), end()); } |
#ifdef __SGI_STL_VECBOOL_TEMPLATE |
typedef vector< bool , alloc> bit_vector; |
#else /* __SGI_STL_VECBOOL_TEMPLATE */ |
inline bool operator==( const bit_vector& x, const bit_vector& y) { |
return x.size() == y.size() && equal(x.begin(), x.end(), y.begin()); |
inline bool operator<( const bit_vector& x, const bit_vector& y) { |
return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); |
#endif /* __SGI_STL_VECBOOL_TEMPLATE */ |
发表评论