Marine Library  1.0
C++ library for Linux Networking Development
single_list.hh
1 #ifndef DOZERG_SINGLE_LIST_H_20070917
2 #define DOZERG_SINGLE_LIST_H_20070917
3 
4 /*
5  STL风格单向链表,主要实现push_back,front,pop_front,size函数
6  除了erase_after(iterator,iterator)
7  和insert_after(iterator,size_type,const_reference)
8  复杂度为O(n)外,其余函数复杂度均为O(1)
9  CSingleList
10  History:
11  20080520 修正insertChainAfter里插入节点后未更改phead_->tail_的bug
12  修正eraseNodeAfter和eraseChainAfter里未更改phead_->tail_的bug
13  20080912 增加append函数
14  20080917 增加copy构造，赋值等函数，完成应有的接口 20111227 增加assert //*/ #include <cassert> #include "template.hh" //CTypeTraits #include "tools/memory.hh" //Destroy #include "impl/single_list_impl.hh" NS_SERVER_BEGIN template< class T, class Alloc = std::allocator<T> >class CSingleList { //typedefs: typedef CSingleList<T, Alloc> __Myt; public: typedef T value_type; typedef T & reference; typedef const T & const_reference; typedef T * pointer; typedef const T * const_pointer; typedef size_t size_type; typedef std::ptrdiff_t difference_type; typedef typename Alloc:: template rebind<T>::other allocator_type; typedef NS_IMPL::__slist_const_iterator<T> const_iterator; typedef NS_IMPL::__slist_iterator<T,Alloc> iterator; private: typedef typename iterator::__node __node; typedef typename iterator::__node_ptr __node_ptr; typedef typename Alloc:: template rebind<__node>::other __node_alloc; //functions: public: explicit CSingleList(allocator_type = allocator_type()) : phead_(0) { init(); } explicit CSingleList(size_type sz, const_reference value = value_type()) : phead_(0) { init(); insert_after(phead_->tail_, sz, value); } CSingleList(const __Myt & a) : phead_(0) { init(); insert_after(phead_->tail_, a.begin(), a.end()); } template<class InputIter> CSingleList(InputIter first,InputIter last) : phead_(0) { init(); insert_after(phead_->tail_, first, last); } ~CSingleList() {destroy();} iterator begin() {return phead_->next_;} iterator end() {return 0;} const_iterator begin() const {return phead_->next_;} const_iterator end() const {return 0;} reference front() {return *begin();} reference back() {return *phead_->tail_->pdata_;} const_reference front() const {return *begin();} const_reference back() const {return *phead_->tail_->pdata_;} bool empty() const {return size_ == 0;} size_type size() const {return size_;} void clear() throw() {eraseChainAfter(phead_,0);} allocator_type get_allocator() const {return allocator_type();} void push_front(const_reference v) {insert_after(phead_,v);} void push_back(const_reference v) {insert_after(phead_->tail_,v);} void pop_front() throw() {eraseNodeAfter(phead_);} //no pop_back() void erase_after(iterator pos) throw() {eraseNodeAfter(pos.ptr_);} void erase_after(iterator before_first,iterator last) throw() { //erase range [before_first->next,last) eraseChainAfter(before_first.ptr_,last.ptr_); } iterator insert_after(iterator pos,const_reference v){ assert(pos.ptr_); __node_ptr node = createNode(v); insertNodeAfter(pos.ptr_,node); return node; } void insert_after(iterator pos,size_type elemSz,const_reference v){ assert(pos.ptr_); __node_ptr head = 0,tail = 0; createChainFill(head,tail,elemSz,v); insertChainAfter(pos.ptr_,head,tail,elemSz); } template<class InputIter> void insert_after(iterator pos,InputIter first,InputIter last){ typedef typename CTypeTraits<InputIter>::__IsInteger __Tag; insertAfterAux(pos,first,last,__Tag()); } void assign(size_type elemSz,const_reference value){ if(elemSz == 0){ clear(); }else if(elemSz < size()){ iterator befor_first = std::fill_n(begin(),elemSz - 1,value); *befor_first = value; erase_after(befor_first,end()); }else{ if(size() > 0) std::fill(begin(),end(),value); insert_after(phead_->tail_,elemSz - size(),value); } } template<class InputIter> void assign(InputIter first,InputIter last){ typedef typename CTypeTraits<InputIter>::__IsInteger __Tag; assignAux(first,last,__Tag()); } void resize(size_type sz,const_reference value = value_type()){ if(sz < size()){ iterator befor_first = begin(); for(;--sz > 0;++befor_first); erase_after(befor_first,end()); }else insert_after(phead_->tail_,sz - size(),value); } __Myt & operator =(const __Myt & a){ if(this != &a) assignAux(a.begin(),a.end(),NS_IMPL::CTrueType()); return *this; } void swap(__Myt & a) throw() { std::swap(size_,a.size_); std::swap(phead_,a.phead_); } void append(__Myt & a) throw() { if(!a.empty()){ insertChainAfter(phead_->tail_,a.phead_->next_,a.phead_->tail_,a.size()); a.init(); } } bool operator ==(const __Myt & other) const{ return size() == other.size() && std::equal<const_iterator,const_iterator>(begin(),end(),other.begin()); } bool operator <(const __Myt & other) const{ return std::lexicographical_compare(begin(),end(),other.begin(),other.end()); } bool operator !=(const __Myt & other) const {return !operator ==(other);} bool operator <=(const __Myt & other) const {return !(other < *this);} bool operator >(const __Myt & other) const {return other < *this;} bool operator >=(const __Myt & other) const {return !(*this < other);} private: template<class IntegerType> void assignAux(IntegerType sz,IntegerType val,NS_IMPL::CTrueType){ assign(size_type(sz),value_type(val)); } template<class InputIter> void assignAux(InputIter first,InputIter last,NS_IMPL::CFalseType){ if(first == last){ clear(); }else{ if(empty()){ insertAfterAux(phead_->tail_,first,last,NS_IMPL::CFalseType()); }else{ iterator cur = begin(),befor_first = cur; *cur++ = *first++; for(;first != last && cur != end();++befor_first) *cur++ = *first++; if(cur == end()){ insertAfterAux(phead_->tail_,first,last,NS_IMPL::CFalseType()); }else erase_after(befor_first,end()); } } } template<class IntegerType> void insertAfterAux(iterator pos,IntegerType sz,IntegerType val,NS_IMPL::CTrueType){ insert_after(pos,size_type(sz),value_type(val)); } template<class InputIter> void insertAfterAux(iterator pos,InputIter first,InputIter last,NS_IMPL::CFalseType){ assert(pos.ptr_); if(first != last){ __node_ptr head,tail; size_type sz = createChainCopy(head,tail,first,last); insertChainAfter(pos.ptr_,head,tail,sz); } } void eraseNodeAfter(__node_ptr pos){ assert(phead_ && pos); __node_ptr cur = pos->next_; if(cur){ pos->next_ = cur->next_; if(phead_->tail_ == cur) phead_->tail_ = pos; --size_; destroyNode(cur); } } void eraseChainAfter(__node_ptr pos,__node_ptr last){ assert(phead_ && pos); __node_ptr first = pos->next_; pos->next_ = last; if(!last) phead_->tail_ = pos; size_ -= destroyChain(first,last); } template<class InputIter> size_type createChainCopy(__node_ptr & head,__node_ptr & tail,InputIter first,InputIter last) const{ size_type ret = 0; head = tail = 0; for(__node_ptr cur = 0;first != last;++ret,++first){ try{ cur = createNode(*first); }catch(...){ destroyChain(head,0); throw; } cur->next_ = 0; if(!head) head = cur; if(tail) tail->next_ = cur; tail = cur; } return ret; } void createChainFill(__node_ptr & head,__node_ptr & tail,size_type elemSz,const_reference v) const{ if(elemSz > 0){ tail = head = createNode(v); try{ for(tail->next_ = 0;--elemSz > 0;tail = tail->next_,tail->next_ = 0) tail->next_ = createNode(v); }catch(...){ destroyChain(head,0); throw; } } } size_type destroyChain(__node_ptr first,__node_ptr last) const throw() { size_type ret = 0; for(;first != last;++ret){ __node_ptr cur = first; first = first->next_; destroyNode(cur); } return ret; } void insertNodeAfter(__node_ptr pos,__node_ptr node) throw() { insertChainAfter(pos,node,node,1); } void insertChainAfter(__node_ptr pos,__node_ptr head,__node_ptr tail,size_type sz) throw() { assert(phead_ && pos && head && tail); tail->next_ = pos->next_; pos->next_ = head; if(!tail->next_) phead_->tail_ = tail; size_ += sz; } __node_ptr createNode(const_reference v) const{ __node_ptr ret = __node_alloc().allocate(1); ret->pdata_ = 0; try{ ret->pdata_ = allocator_type().allocate(1); allocator_type().construct(ret->pdata_,v); }catch(...){ tools::Deallocate(ret->pdata_,allocator_type()); tools::Deallocate(ret,__node_alloc()); throw; } return ret; } void destroyNode(__node_ptr & node) const throw() { if(node){ tools::Delete(node->pdata_,allocator_type()); tools::Deallocate(node,__node_alloc()); } } void init(){ if(!phead_) phead_ = __node_alloc().allocate(1); phead_->next_ = 0; phead_->tail_ = phead_; size_ = 0; } void destroy() throw() { clear(); tools::Deallocate(phead_,__node_alloc()); } //fields: __node * phead_; //链表头节点 size_type size_; }; template<class T,class Alloc> void swap(CSingleList<T,Alloc> & a,CSingleList<T,Alloc> & b) { a.swap(b); } NS_SERVER_END #endif
15  20111227 增加assert
16 //*/
17 
18 #include <cassert>
19 #include "template.hh" //CTypeTraits
20 #include "tools/memory.hh" //Destroy
21 #include "impl/single_list_impl.hh"
22 
23 NS_SERVER_BEGIN
24 
25 template<
26  class T,
27  class Alloc = std::allocator<T>
28 >class CSingleList
29 {
30 //typedefs:
31  typedef CSingleList<T, Alloc> __Myt;
32 public:
33  typedef T value_type;
34  typedef T & reference;
35  typedef const T & const_reference;
36  typedef T * pointer;
37  typedef const T * const_pointer;
38  typedef size_t size_type;
39  typedef std::ptrdiff_t difference_type;
40  typedef typename Alloc::
41  template rebind<T>::other allocator_type;
42  typedef NS_IMPL::__slist_const_iterator<T> const_iterator;
43  typedef NS_IMPL::__slist_iterator<T,Alloc> iterator;
44 private:
45  typedef typename iterator::__node __node;
46  typedef typename iterator::__node_ptr __node_ptr;
47  typedef typename Alloc::
48  template rebind<__node>::other __node_alloc;
49 //functions:
50 public:
51  explicit CSingleList(allocator_type = allocator_type())
52  : phead_(0)
53  {
54  init();
55  }
56  explicit CSingleList(size_type sz, const_reference value = value_type())
57  : phead_(0)
58  {
59  init();
60  insert_after(phead_->tail_, sz, value);
61  }
62  CSingleList(const __Myt & a)
63  : phead_(0)
64  {
65  init();
66  insert_after(phead_->tail_, a.begin(), a.end());
67  }
68  template<class InputIter>
69  CSingleList(InputIter first,InputIter last)
70  : phead_(0)
71  {
72  init();
73  insert_after(phead_->tail_, first, last);
74  }
75  ~CSingleList() {destroy();}
76  iterator begin() {return phead_->next_;}
77  iterator end() {return 0;}
78  const_iterator begin() const {return phead_->next_;}
79  const_iterator end() const {return 0;}
80  reference front() {return *begin();}
81  reference back() {return *phead_->tail_->pdata_;}
82  const_reference front() const {return *begin();}
83  const_reference back() const {return *phead_->tail_->pdata_;}
84  bool empty() const {return size_ == 0;}
85  size_type size() const {return size_;}
86  void clear() throw() {eraseChainAfter(phead_,0);}
87  allocator_type get_allocator() const {return allocator_type();}
88  void push_front(const_reference v) {insert_after(phead_,v);}
89  void push_back(const_reference v) {insert_after(phead_->tail_,v);}
90  void pop_front() throw() {eraseNodeAfter(phead_);} //no pop_back()
91  void erase_after(iterator pos) throw() {eraseNodeAfter(pos.ptr_);}
92  void erase_after(iterator before_first,iterator last) throw() { //erase range [before_first->next,last)
93  eraseChainAfter(before_first.ptr_,last.ptr_);
94  }
95  iterator insert_after(iterator pos,const_reference v){
96  assert(pos.ptr_);
97  __node_ptr node = createNode(v);
98  insertNodeAfter(pos.ptr_,node);
99  return node;
100  }
101  void insert_after(iterator pos,size_type elemSz,const_reference v){
102  assert(pos.ptr_);
103  __node_ptr head = 0,tail = 0;
104  createChainFill(head,tail,elemSz,v);
105  insertChainAfter(pos.ptr_,head,tail,elemSz);
106  }
107  template<class InputIter>
108  void insert_after(iterator pos,InputIter first,InputIter last){
109  typedef typename CTypeTraits<InputIter>::__IsInteger __Tag;
110  insertAfterAux(pos,first,last,__Tag());
111  }
112  void assign(size_type elemSz,const_reference value){
113  if(elemSz == 0){
114  clear();
115  }else if(elemSz < size()){
116  iterator befor_first = std::fill_n(begin(),elemSz - 1,value);
117  *befor_first = value;
118  erase_after(befor_first,end());
119  }else{
120  if(size() > 0)
121  std::fill(begin(),end(),value);
122  insert_after(phead_->tail_,elemSz - size(),value);
123  }
124  }
125  template<class InputIter>
126  void assign(InputIter first,InputIter last){
127  typedef typename CTypeTraits<InputIter>::__IsInteger __Tag;
128  assignAux(first,last,__Tag());
129  }
130  void resize(size_type sz,const_reference value = value_type()){
131  if(sz < size()){
132  iterator befor_first = begin();
133  for(;--sz > 0;++befor_first);
134  erase_after(befor_first,end());
135  }else
136  insert_after(phead_->tail_,sz - size(),value);
137  }
138  __Myt & operator =(const __Myt & a){
139  if(this != &a)
140  assignAux(a.begin(),a.end(),NS_IMPL::CTrueType());
141  return *this;
142  }
143  void swap(__Myt & a) throw() {
144  std::swap(size_,a.size_);
145  std::swap(phead_,a.phead_);
146  }
147  void append(__Myt & a) throw() {
148  if(!a.empty()){
149  insertChainAfter(phead_->tail_,a.phead_->next_,a.phead_->tail_,a.size());
150  a.init();
151  }
152  }
153  bool operator ==(const __Myt & other) const{
154  return size() == other.size() &&
155  std::equal<const_iterator,const_iterator>(begin(),end(),other.begin());
156  }
157  bool operator <(const __Myt & other) const{
158  return std::lexicographical_compare(begin(),end(),other.begin(),other.end());
159  }
160  bool operator !=(const __Myt & other) const {return !operator ==(other);}
161  bool operator <=(const __Myt & other) const {return !(other < *this);}
162  bool operator >(const __Myt & other) const {return other < *this;}
163  bool operator >=(const __Myt & other) const {return !(*this < other);}
164 private:
165  template<class IntegerType>
166  void assignAux(IntegerType sz,IntegerType val,NS_IMPL::CTrueType){
167  assign(size_type(sz),value_type(val));
168  }
169  template<class InputIter>
170  void assignAux(InputIter first,InputIter last,NS_IMPL::CFalseType){
171  if(first == last){
172  clear();
173  }else{
174  if(empty()){
175  insertAfterAux(phead_->tail_,first,last,NS_IMPL::CFalseType());
176  }else{
177  iterator cur = begin(),befor_first = cur;
178  *cur++ = *first++;
179  for(;first != last && cur != end();++befor_first)
180  *cur++ = *first++;
181  if(cur == end()){
182  insertAfterAux(phead_->tail_,first,last,NS_IMPL::CFalseType());
183  }else
184  erase_after(befor_first,end());
185  }
186  }
187  }
188  template<class IntegerType>
189  void insertAfterAux(iterator pos,IntegerType sz,IntegerType val,NS_IMPL::CTrueType){
190  insert_after(pos,size_type(sz),value_type(val));
191  }
192  template<class InputIter>
193  void insertAfterAux(iterator pos,InputIter first,InputIter last,NS_IMPL::CFalseType){
194  assert(pos.ptr_);
195  if(first != last){
196  __node_ptr head,tail;
197  size_type sz = createChainCopy(head,tail,first,last);
198  insertChainAfter(pos.ptr_,head,tail,sz);
199  }
200  }
201  void eraseNodeAfter(__node_ptr pos){
202  assert(phead_ && pos);
203  __node_ptr cur = pos->next_;
204  if(cur){
205  pos->next_ = cur->next_;
206  if(phead_->tail_ == cur)
207  phead_->tail_ = pos;
208  --size_;
209  destroyNode(cur);
210  }
211  }
212  void eraseChainAfter(__node_ptr pos,__node_ptr last){
213  assert(phead_ && pos);
214  __node_ptr first = pos->next_;
215  pos->next_ = last;
216  if(!last)
217  phead_->tail_ = pos;
218  size_ -= destroyChain(first,last);
219  }
220  template<class InputIter>
221  size_type createChainCopy(__node_ptr & head,__node_ptr & tail,InputIter first,InputIter last) const{
222  size_type ret = 0;
223  head = tail = 0;
224  for(__node_ptr cur = 0;first != last;++ret,++first){
225  try{
226  cur = createNode(*first);
227  }catch(...){
228  destroyChain(head,0);
229  throw;
230  }
231  cur->next_ = 0;
232  if(!head)
233  head = cur;
234  if(tail)
235  tail->next_ = cur;
236  tail = cur;
237  }
238  return ret;
239  }
240  void createChainFill(__node_ptr & head,__node_ptr & tail,size_type elemSz,const_reference v) const{
241  if(elemSz > 0){
242  tail = head = createNode(v);
243  try{
244  for(tail->next_ = 0;--elemSz > 0;tail = tail->next_,tail->next_ = 0)
245  tail->next_ = createNode(v);
246  }catch(...){
247  destroyChain(head,0);
248  throw;
249  }
250  }
251  }
252  size_type destroyChain(__node_ptr first,__node_ptr last) const throw() {
253  size_type ret = 0;
254  for(;first != last;++ret){
255  __node_ptr cur = first;
256  first = first->next_;
257  destroyNode(cur);
258  }
259  return ret;
260  }
261  void insertNodeAfter(__node_ptr pos,__node_ptr node) throw() {
262  insertChainAfter(pos,node,node,1);
263  }
264  void insertChainAfter(__node_ptr pos,__node_ptr head,__node_ptr tail,size_type sz) throw() {
265  assert(phead_ && pos && head && tail);
266  tail->next_ = pos->next_;
267  pos->next_ = head;
268  if(!tail->next_)
269  phead_->tail_ = tail;
270  size_ += sz;
271  }
272  __node_ptr createNode(const_reference v) const{
273  __node_ptr ret = __node_alloc().allocate(1);
274  ret->pdata_ = 0;
275  try{
276  ret->pdata_ = allocator_type().allocate(1);
277  allocator_type().construct(ret->pdata_,v);
278  }catch(...){
279  tools::Deallocate(ret->pdata_,allocator_type());
280  tools::Deallocate(ret,__node_alloc());
281  throw;
282  }
283  return ret;
284  }
285  void destroyNode(__node_ptr & node) const throw() {
286  if(node){
287  tools::Delete(node->pdata_,allocator_type());
288  tools::Deallocate(node,__node_alloc());
289  }
290  }
291  void init(){
292  if(!phead_)
293  phead_ = __node_alloc().allocate(1);
294  phead_->next_ = 0;
295  phead_->tail_ = phead_;
296  size_ = 0;
297  }
298  void destroy() throw() {
299  clear();
300  tools::Deallocate(phead_,__node_alloc());
301  }
302 //fields:
303  __node * phead_; //链表头节点 size_type size_; }; template<class T,class Alloc> void swap(CSingleList<T,Alloc> & a,CSingleList<T,Alloc> & b) { a.swap(b); } NS_SERVER_END #endif
304  size_type size_;
305 };
306 
307 template<class T,class Alloc>
308 void swap(CSingleList<T,Alloc> & a,CSingleList<T,Alloc> & b)
309 {
310  a.swap(b);
311 }
312 
313 NS_SERVER_END
314 
315 #endif
CSingleList
Definition: single_list.hh:28
Generated by   doxygen 1.8.11