C++ template and STL containers

Posted on |

I used C++ couple years already, but never take a close look at it. when looking back to few C++ demo works at school, I had a strong feeling at that time, to make the code running is my only goal, how it work or how to improve it, is always ignored, I am afraid in the language details, as the wisdom say: the evil is in details.

after working for three years, I feel the necessary and urgent to back to the language itself(e.g. Linux, C/C++) as the first step to move forward in application development. Frameworks, engineering-based APIs are more close to final products, making them easy to be attracted, compared to how the details implemented. like the mechanical undergradute students, who first-time run ABAQUS with beatiful visulized results, feels so good.

anyway I have to delay the short satification or self-feeling-good. C is clean and the applications have clear structure, C++ is more metaphysics, I even don’t know where to start. even I thought I knew C++ well, but actualy there are many details behind, e.g. allocator in STL.

template

template is used for generic programming, e.g. both vector and vector smell same at compiler time. Template reels off or abstract the common part “vector” as a container, and whatever type is ok to store in.

function template

1
2
3
4
5
6
7
8
9
10
11
12
template <class T>
	void func(T arg)
template <typename T>
	void func(T arg)
template <class T>
	T add(T n1, int v){};
template <class T1, class T2, class T3>
	T3 func(T1 a1, T2 a2, int arg3=3){};

the actual meaning of TYPE is deduced by compiler depending on the arg passed to this function. “class” or “typename” is similar.

template supports default parameters, once the i-th argument is set with default value, all arguments after it must using default values.

class template

1
2
3
4
5
6
7
8
9
10
11
12
template<class _Tp, class _Ref, class _Ptr>
class _list_iterator {
	typedef _List_iterator<_Tp, _Tp&, _Tp*>  iterator ;
	typedef _List_iterator<_Tp, const _Tp&, const _Tp*>  const_iterator ;
	typedef _List_iterator<_Tp, _Ref, _Ptr>  _Self ;
	typedef _Tp value_type ;
	typedef _Ptr  pointer;
	typedef _Ref  reference ;
	typedef _List_node<_Tp>  _Node; 
}

feel the power of template in STL source code.

STL containers

references:
<< the annotated STL source using SGI STL >> by jjHou
a visitor guide to C++ allocator
the annotated STL source
I took several days to start, cause the first section on allocator already blocked me.

why allocator ?

The logic of a dynamic container doesn’t depend on the specifies of how memory is obtained; namely, the design of container classes should be decoupled from the memory allocation policy.

how allocator works ?

memory allocation and object construction is separated, allocator has four operations: allocate(), deallocate(), construct(), destroy(). there are std interface to allocators

1
2
3
4
5
6
7
AllocTraits = std::allocator_traits<alloc> 
// define an allocator of type "alloc" 
AllocTraits::pointer  p = AllocTraits::allocate(a, n)  
//get memory space for n objects of type T, but not construct yet 
AllocTraits::construct(a, trueaddress(ptr), x, y, z) ;    //construct a T(x, y, z)
AllocTraits::destroy(a, trueaddress(ptr));  // ~T()
AllocTraits::deallocate(a, ptr, 1) ;   // deallocate the space for one T object

WHEN we say A is an allocator for T , where T is a type e.g. AllocatTraits::value_type. we mean, A knows how to obtain and release memory to store objects of type T. git:allocator

iterator

iterator is used to build algorithms in containers. while I don’t really get the traits 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class _Iterator>
struct iterator_traits {
	typedef typename _Iterator::iterator_category  iterator_category ;
	typedef typename _Iterator::value_type	 value_type ;
	typedef typename _Iterator::difference_type  difference_type ;
	typedef typename _Iterator::pointer	pointer;
	typedef typename _Iterator::reference reference ;
};
template<class _Tp>
struct iterator_traits<_Tp*> {
	typedef typename random_access_iterator_tag  iterator_category ;
	typedef typename _Tp	 value_type ;
	typedef typename ptrdiff_t  difference_type ;
	typedef typename _Tp*	pointer;
	typedef typename _Tp& eference ;
};

vector

std::vector is dynamic, continous.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
template <class _Tp,  class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
class vector:: protected _Vector_base<_Tp,  _Alloc>
{
	public:
		typedef  _Tp value_type ;
		typedef  value_type*  pointer ;
		typedef  const value_type*  const_pointer ;
		typedef value_type* iterator ;
		typedef const value_type*  const_iterator ;
		iterator begin() {return _M_start;};
		iterator end() {return _M_finish ;};
	protected:
		_Tp* _M_start ; // the starting point of current used space 
		_Tp* _M_finish; // the ending point of current sued space 
	      _Tp*  _M_end_of_storage; // the end of total avialable space(capacity)
	public:
		explicit vector(const allocator_type& __a = allocator_type())
			: _Base(__a){}  //default constructor 
		// construt of n elements of initial-value 
		vector(size_type __n, const _Tp& __value, const allocator_type& __a = allocator_type())
			: _Base(__n, __a)
		{
			_M_finish = uninitialized_fill_n(_M_start, __n, __value);
		}
		//copy construtor
		vector(const vector<_Tp, _Alloc>& __x)
			:_Base(__x.size(),  __x.get_allocator())
		{
			_M_finish = uninitialized_copy(__x.begin(),  __x.end(), _M_start);
		}
		size_type  size() const {return size_type(end() - begin());}
		size_type capacity() const {return size_type(_M_end_of_storage - begin()); 
		bool empty() const{return begin() == end();}
		reference operator[](size_type __n){return *(begin() + __n);}
		void reserve(size_type __n){
			if (capacity() < __n)
			{
				const size_type __old_size = size(); 
				iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
				destroy(_M_start, _M_finish);
				_M_deallocate(_M_start, _M_end_of_storage-_M_start); 
				_M_start = __tmp;
				_M_finish = __tmp + __old_size ;
				_M_end_of_storage = _M_start + __n ;
			}
		}
		void push_back(const _Tp& __x)
		{
			if(_M_finish != _M_end_of_storage)
			{
				construct(_M_finish, __x);
				++_M_finish;
			}else
				_M_insert_aux(end(), __x);
		}
		template<class _Tp,  class _Alloc>
		inline bool operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
		{
			return __x.size() == __y.size() && 
			equal(__x.begin(), __x.end(), __y.begin());
		}
};

list

std::list is cycling double-direction link list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
struct _List_node_base 
{
	_List_node_base * _M_next ;
	_List_node_base * _M_prev ;
};
template <class _Tp>
struct _List_node : public _List_node_base 
{
	_Tp _M_data;
};
struct _List_iterator_base 
{
	typedef size_t   size_type ;
	typedef ptrdiff_t   difference_type ;
	typedef bidirectional_iterator_tag  iterator_category; 
	_List_node_base*  _M_node ;
	//constructor 
	_List_iterator_base(_List_node_base* __x) : _M_node(__x){}
	_List_iterator_base(){};
	void _M_incr() { _M_node = _M_node->_M_next; };
	void _M_decr() { _M_node = _M_node->_M_prev; };
	bool operator==(const _List_iterator_base& __x) const
	{
		return _M_node == __x.M_node ;
	}
};
template<class _Tp,  class _Ref,  class _Ptr>
struct _List_iterator : public _List_iterator_base 
{
	typedef _List_iterator<_Tp, _Tp&, _Tp*>  iterator ;
	typedef _List_iterator<_Tp, const _Tp&, const _Tp*>  const_iterator ;
	typedef _List_iterator<_Tp, _Ref, _Ptr>  _Self ;
	typedef _Tp value_type ;
	typedef _Ptr  pointer;
	typedef _Ref  reference ;
	typedef _List_node<_Tp>  _Node; 
	//constructor 
	_List_iterator(_Node* __x): _List_iterator_base(__x){}
	_List_iterator(){}
	reference operator*() const {return ( (_Node*) _M_node)->_M_data; }
	_Self&  operator++()
	{
		this->_M_incr();
		return *this;
	}
};
template <class _Tp,  class _Alloc=_STL_DEFAULT_ALLOCATOR(_Tp)>
class list : protected _List_base<_Tp, _Alloc>
{
	public:
		typedef _List_node<_Tp> _Node;
	protected:
		_List_node<_Tp> * _M_node; 
	public:
		list(size_type __n,   const _Tp&  __value,
			const allocator_type& __a = allocator_type())
			: Base_(__a)
		{
			insert(begin(), __n, __value);
		}
		explicit list(size_type __n)
			:_Base(allocator_type())
		{
			insert(begin(), __n, _Tp());
		}
	protected:
		_Node* _M_create_node(const _Tp& __x)
		{
			_Node* __p = _M_get_node(); 
			__STL_TRY
			{
				_Construct(&_p->_M_data, __x);
			}
			return __p;
		}
	public:
		iterator begin() { return (_Node*)(_M_node->_M_next);}
		iterator end() { return _M_node; }
		bool empty() const {return _M_node->_M_next == _M_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();}
		reference back() {return *(--end());}
		void swap(list<_Tp, _Alloc>& __x)
		{
			__STD::swap(_M_node, __x._M_node);
		}
		interator insert(iterator __position,  const _Tp& __x)
		{
			_Node* __tmp = _M_create_node(__x);
			__tmp->_M_next = __position._M_node ;
			__tmp->_M_prev = __position._M_node->_M_prev ;
			
			__position._M_node->_M_prev->_M_next = __tmp;
			__position._M_node->_M_prev  = __tmp;
			
			return __tmp;
		}
		void push_front(const _Tp& __x){insert(begin(), __x);}
		void push_back(const _Tp& __x){insert(end(), __x);}
		iterator erase(iterator __position)
		{
			_List_node_base* __next_node = __position._M_node->_M_next ;
			_List_node_base* __prev_node = __position._M_node->_M_prev ;
			_Node* __n = (_Node*) __position._M_node ;
			__prev_node->next = __next_node ;
			__next_node->prev = __prev_node;
	
			_Destroy(&__n->_M_data);
			_M_put_data(__n);
			return iterator((_Node*) __next_node);
		}
}

dequeue

std::dequeue can operate elements at both ends, and the memory is multi-sectional, in each memory section is linear continous, with advantage of vector and list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
template <class _Tp,  class _Ref,  class _Ptr>
struct _Deque_iterator {
	typedef _Deque_iterator<_Tp, _Tp&, _Tp*>   iterator ;
	typedef _Deque_iterator<_Tp, const _Tp&, const  _Tp*>  const_iterator ;
	static size_t _S_buffer_size() {return __deque_buf_size(sizeof(_Tp));}
	typedef random_access_iterator_tag  iterator_category;
	typedef _Tp value_type ;
	typedef _Ptr  pointer;
	typedef _Ref reference;
	typedef size_t  size_type ;
	typedef ptrdiff_t  difference_type ;
	typedef _Tp** _Map_pointer ;
	typedef _Deque_iterator _Self; 
	_Tp* _M_cur ; //current point in cache
	_Tp* _M_first; //first point in cache
	_Tp* _M_last; 
	_Map_pointer _M_node ; 
	/* deque support multi-section memory space, in each memory section is linear continous
	 * Map index is used to point to the memory sections
	 */
	
	_Deque_iterator(_Tp* __x, _Map_pointer __y)
		:_M_cur(__x), 
		 _M_first(*__y),
		 _M_last(*__y + _S_buffer_size()), 
		 _M_node(__y)
	{}
	//default 
	//copy
	
	difference_type operator-(const _Self& __x) const
	{
		return difference_type(_S_buffer_size()) *  (_M_node - __x.M_node - 1) + 
			(_M_cur - _M_first) + (__x._M_last - __x._M_cur);
	}
	_Self& operator++()
	{
		++_M_cur ; 
		if(_M_cur == _M_last){
			_M_set_node(_M_node + 1);
			_M_cur = _M_first;
		}
		return *this;
	}
	_Self& operator--()
	{
		if(_M_cur == _M_first){
			_M_set_node(_M_node - 1);
			_M_cur = _M_last;
		}
		--_M_cur ;
		return *this;
	}
}
	
/*  deque has two iterator:
   start -> the first element in first cache space;  
   finish -> the last element in last cache space */
template <class _Tp,  class _Alloc>
class _Deque_base {
	protected:		
		_Tp** _M_map ;
		size_t _M_map_size; 
		iterator _M_start;
		iterator _M_finish;
};
template <class _Tp,  class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp)>
class deque : protected _Deque_base<_Tp, _Alloc>
{
	public:
		typedef typename _Base::iterator  iterator ;
		typedef typename _Base::const_iterator  const_iterator ;
	protected:
		using _Base::_M_map ; 
		using _Base::_M_map_size ;
		using _Base::_M_start ; 
		using _Base::_M_finish ;
	public:
		explicit deque(const allocator_type& __a = allocator_type())
			:_Base(__a, 0)
		{}
		deque(const deque& __x):
			_Base(__x.get_allocator(), __x.size())
		{
			uninitialized_copy(__x.begin(),  __x.end(), _M_start);
		}
		~deque(){ destroy(_M_start, _M_finish);}
		void push_back(const value_type& __t)
		{
			if(_M_finish._M_cur != _M_finish._M_last - 1)
			{
				construct(_M_finish._M_cur, __t);
				++_M_finish._M_cur ;
			}else
				_M_push_back_aux(__t);
		}
		void push_front(const value_type&  __t)
		{
			if(_M_start._M_cur != _M_start._M_first)
			{
				construct(_M_start._M_cur - 1,  __t);
				--_M_start._M_cur;
			}else
				_M_push_front_aux(__t);
		}
		void pop_back()
		{
			if(_M_finish._M_cur != _M_finish._M_first)
			{
				--_M_finish._M_cur;
				destroy(_M_finish._M_cur);
			}else
				_M_pop_back_aux();
		}
		void pop_front()
		{
			if(_M_start._M_cur != _M_start._M_last -1)
			{
				destroy(_M_start._M_cur);
				++_M_start._M_cur;
			}else
				_M_pop_back_aux();
		}
		iterator insert(iterator position, const value_type&  __x)
		{
			if(position._M_cur == _M_start._M_cur)
			{
				push_front(__x);
				return _M_start;
			}else if(position._M_cur == _M_finish._M_cur)
			{
				push_back(__x);
				iterator __tmp = _M_finish;
				--__tmp;
				return __tmp;
			}
		}
};

stack

std::stack only operate on the top element (first in last out), can’t iterate the container, the default container for stack is deque. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
temlate <class _Tp, class _Sequence>
class stack
{
	public:
		typedef typname _Sequence::value_type  value_type ;
		typedef typname _Sequence::size_type   size_type ;
		typedef typname _Sequence	  container_type ;
		typedef typname _Sequence::reference  reference ;
		typedef typname _Sequence::const_reference const_reference;
	protected:
		_Sequence c;  // the fundmental container:  deque by default
	public:
		stack() : c() {}
		explicit stack(const _Sequence& __s) : c(__s) {}
		
		bool empty() const { return c.empty();}
		size_type size() const {return c.size();}
		reference top() {return c.back(); }
		void push(const value_type& __x){ c.push_back(__x);}
		void pop() { c.pop_back();}
	
		template<class _Tp,  class _Seq>
			bool operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
			{
				return __x.c == __y.c ;
			}
};

queue

std::queue supports only pop element from front, and push element into end, the default container is dequeue 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <class _Tp, class _Sequence>
class queue
{
	public:
		typedef typname _Sequence::value_type  value_type ;
		typedef typname _Sequence::size_type   size_type ;
		typedef typname _Sequence	  container_type ;
		typedef typname _Sequence::reference  reference ;
		typedef typname _Sequence::const_reference const_reference;
	protected:
		_Sequence c;  // the fundmental container:  deque by default
	public:
		queue() : c() {}
		explicit queue(const _Sequence& __s) : c(__s) {}
		bool empty() const { return c.empty();}
		size_type size() const {return c.size();}
		reference top() {return c.back(); }
		void push(const value_type& __x){ c.push_back(__x);}
		void pop() { c.pop_front();}
	
		template<class _Tp,  class _Seq>
			bool operator==(const queue<_Tp, _Seq>& __x, const queue<_Tp, _Seq>& __y)
			{
				return __x.c == __y.c ;
			}
};

priority queue

std::priority_queue is queue with priority.