c++List容器(随意写的

  1 #include <iostream>
  2 #include<my.hpp>
  3 using namespace std;
  4 
  5 void line_feed() {
  6     cout << endl;
  7 }
  8 
  9 template<class T>class List {
 10 public:
 11     T* a;
 12     List() { init(); }
 13 
 14     List(T data) {
 15         init();
 16         this->push_back(data);
 17         curr = begin();
 18     }
 19 
 20     List(List<T>& want) {
 21         init();
 22         auto cp = want.begin();
 23         while (cp != want.end()) {
 24             sz++;
 25             curr = curr->insertsurr(cp->data);
 26             cp = cp->surr;
 27         }
 28 
 29     }
 30     List<T>& operator=(List<T>& want) {
 31         init();
 32         auto cp = want.begin();
 33         while (cp != want.end()) {
 34             sz++;
 35             curr = curr->insertsurr(cp->data);
 36             cp = cp->surr;
 37         }
 38         return *this;
 39     }
 40 
 41     ~List() {
 42         clear();
 43         delete head;
 44         delete tail;
 45     }
 46 
 47     List(initializer_list<T>input) {
 48         init();
 49         this->push_back(input);
 50 
 51     }
 52 
 53     const T& operator [](int times) {
 54         ListNode<T>* cp = begin();
 55         for (auto i = 0; i < times; ++i)cp = cp->surr;
 56         return cp->data;
 57     }
 58     ListNode<T>* operator++() {
 59         curr = curr->surr;
 60         return curr;
 61     }
 62 
 63     ListNode<T>* operator++(int) {
 64         curr = curr->surr;
 65         return curr;
 66     }
 67 
 68     ListNode<T>* operator--() {
 69         curr = curr->pre;
 70         return curr;
 71     }
 72 
 73     ListNode<T>* operator--(int) {
 74         curr = curr->pre;
 75         return curr;
 76     }
 77 
 78     void unique();
 79 
 80     void push_back(const ListNode<T>* list) {
 81         sz++;
 82         tail->pre = tail->pre->insertsurr(list->data);
 83     }
 84 
 85     void push_back(T data) {
 86         sz++;
 87         tail->pre = tail->pre->insertsurr(data);
 88     }
 89 
 90     void push_back(initializer_list<T>input) {
 91         for (auto i = input.begin(); i < input.end(); ++i) {
 92             sz++;
 93             tail->pre = tail->pre->insertsurr(*i);
 94 
 95         }
 96     }
 97 
 98     void push_front(const ListNode<T>* list) {
 99         sz++;
100         head->surr = head->surr->insertpre(list->data);
101     }
102 
103     void push_front(T data) {
104         sz++;
105         head->surr = head->surr->insertpre(data);
106     }
107 
108     void push_front(initializer_list<T>input) {
109         for (auto i = input.begin(); i < input.end(); ++i) {
110             sz++;
111             head->surr = head->surr->insertpre(*i);
112         }
113     }
114 
115     ListNode<T>* begin() { return head->surr; }
116 
117     ListNode<T>* end() { return tail; }
118 
119     auto traverse() {
120         ListNode<T>* cp = begin();
121         auto s = sz;
122         while (s--)
123         {
124             cout << cp->data << ends;
125             cp = cp->surr;
126         }
127     }
128     int find(int begin, int end, T data) {
129         int get = begin;
130         while (get != end) {
131             if (operator[](get++) == data)return get - 1;
132         }
133         return -1;
134     }
135 
136     ListNode<T>* find(ListNode<T>* begin, ListNode<T>* end, T data) {
137         decltype(begin) get = this->begin();
138         while (get != end) {
139             if (get->data == data)return  get;
140             get = get->surr;
141         }
142         return get;
143     }
144 
145     ListNode<T>* current() { return curr; }
146 
147     T current_data() { return curr->data; }
148 
149     size_t size()
150     {
151         return sz;
152     }
153     void insert(ListNode<T>* begin, T data);
154 
155     void insert(ListNode<T>* ptr, const ListNode<T>* begin, const ListNode<T>* end) const;
156 
157     void insert(ListNode<T>* begin, int site, T data);
158 
159     ListNode<T>* remove(ListNode<T>* want);
160 
161     ListNode<T>* remove(ListNode<T>* want, int site);
162 
163     void clear() {
164         decltype(head)ptr = begin();
165         while (--sz) {
166             ptr = ptr->surr;
167 
168             delete ptr->pre;
169         }
170         curr = head;
171     }
172 
173     void sorted_unique();
174 
175     void insert_sort();
176 
177     ListNode<T>* selectMax(ListNode<T>* cp);
178 
179     auto search(int begin, int end, T data) {
180         int get = end;
181         while (get != begin) {
182             if (operator[](--get) <= data)break;
183 
184         }
185         return get + 1;
186 
187     }
188 
189     void insert_after(ListNode<T>* begin, int site, T data);
190 
191     auto generate(List<T>ls) {
192         ListNode<T>* a = begin();
193         int num = 0;
194         while (num != ls.size()) {
195 
196             a->data = ls[num++];
197             a = a->surr;
198         }
199     }
200 
201     void select_sort();
202 
203     void swap(ListNode<T>* ls, ListNode<T>* rs) {
204         T t = ls->data;
205         ls->data = rs->data;
206         rs->data = t;
207     }
208 
209 
210 protected:
211 
212     auto init() {
213         sz = 0;
214         head = new ListNode<T>(), tail = new ListNode<T>();
215         head->surr = tail;
216         tail->pre = head;
217         head->pre = NULL;
218         tail->surr = NULL;
219         curr = head;
220         rpre = tail;
221     }
222 
223 
224 private:
225 
226     mutable size_t sz;
227 
228     ListNode<T>* head, * tail;
229 
230     ListNode<T>* curr, * rpre;
231 };
232 template<class T> inline void List<T>::insert(ListNode<T>* begin, T data) {
233     decltype(begin)cp(begin);
234     sz++;
235     cp = cp->insertpre(data);
236 }
237 
238 template<class T> inline void List<T>::insert(ListNode<T>* begin, int site, T data) {
239     sz++;
240     decltype(begin)cp(begin);
241     while (site--) { cp = cp->surr; }
242     cp->insertpre(data);
243 }
244 
245 template<class T> inline void List<T>::insert_after(ListNode<T>* begin, int site, T data) {
246     sz++;
247     decltype(begin)cp(begin);
248     while (site--) { cp = cp->surr; }
249     cp->insertsurr(data);
250 }
251 
252 template<class T> inline void List<T>::insert(ListNode<T>* ptr, const ListNode<T>* begin, const ListNode<T>* end) const {
253     decltype(begin)cp(begin);
254     while (cp != end) {
255         sz++;
256         ptr->insertpre(cp->data);
257         cp = cp->surr;
258     }
259 }
260 template<class T> inline ListNode<T>* List<T>::remove(ListNode<T>* want) {
261     decltype(want)& p1 = want->pre;
262     decltype(want)& p2 = want->surr;
263     p1->surr = want->surr;
264     p2->pre = want->pre;
265     delete want;
266     --sz;
267     return p2;
268 }
269 
270 template<class T> inline ListNode<T>* List<T>::remove(ListNode<T>* want, int site) {
271 
272     while (site--)
273         want = want->surr;
274     return remove(want);
275 
276 
277 }
278 
279 template<class T>void List<T>::unique() {
280     int r = 0, site;
281     while (r != size()) {
282         {int num = this->operator[](r);
283         if ((site = find(r + 1, size(), num)) != -1) {
284             remove(begin(), site);
285 
286         }
287         else r++;
288         }
289     }
290 
291 }
292 
293 template<class T>void List<T>::sorted_unique() {
294     ListNode<T>* cp = begin(), * nextcp = cp->surr;
295     while (nextcp != end()) {
296         {
297             if (cp->data == nextcp->data) {
298                 nextcp = nextcp->surr;
299                 remove(nextcp->pre);
300             }
301             else {
302                 cp = nextcp;
303                 nextcp = nextcp->surr;
304             }}
305     }
306 
307 }
308 
309 
310 
311 template<class T>void List<T>::insert_sort() {
312     List<T>newlist(0);
313     ListNode<T>* cp = begin();
314     size_t s = sz;
315 
316     while (s--) {
317 
318         int site = newlist.search(0, newlist.size(), cp->data);
319         newlist.insert(newlist.begin(), site, cp->data);
320         cp = cp->surr;
321         //newlist.traverse();
322         //cout << newlist.begin()->data;
323     }
324     newlist.remove(newlist.begin(), 0);
325     generate(newlist);
326 
327 
328 
329 }
330 template<class T>ListNode<T>* List<T>::selectMax(ListNode<T>* cp) {
331     ListNode<T>* where = cp;
332     ListNode<T>* other = where;
333     T max = where->data;
334     while (where != begin()) {
335         where = where->pre;
336         if (where->data > max)
337         {
338             max = where->data;
339             other = where;
340         }
341     }
342     return other;
343 }
344 
345 template<class T>void List<T>::select_sort()
346 {
347     using std::swap;
348     ListNode<T>* cp = end()->pre;
349     size_t s = sz;
350     while (s--) {
351 
352         this->swap(cp, selectMax(cp));
353         cp = cp->pre;
354     }
355 
356 }
357 
358 int main()
359 {
360     List<int>a{ 100,5,2,7,4,6,3,1,1,1,5,42,52, };
361     a.select_sort();
362     a.push_back(3);
363     a.push_back(1);
364 
365     a.traverse();
366     line_feed();
367     a.insert_sort();
368     a.traverse();
369 
370 
371 
372 }

 1 #pragma once
 2 template<class T>struct ListNode {
 3     ListNode() = default;
 4     ListNode(T data, ListNode<T>* pre = NULL, ListNode<T>* surr = NULL) :pre(pre), surr(surr), data(data) {}
 5     ListNode<T>* pre, *surr;
 6     T data;
 7     ListNode<T>*insertpre(const T& data);
 8     ListNode<T>*insertsurr(const T& data);
 9     ListNode<T>* operator++() { this = this->surr; return this; }
10     bool operator!=(const ListNode<T>right)const { return &this != right; }
11     T operator*() const { return this->data; }    
12     ListNode<T>* operator++() const { return this->surr; }
13     ~ListNode() {}
14 };
15 template<class T>ListNode<T>* ListNode<T>::insertpre(const T& data) {
16     ListNode<T>* newptr = new ListNode<T>(data);
17     newptr->surr = this;
18     newptr->pre = pre;
19     pre->surr = newptr;
20     pre = newptr;
21     return newptr;
22 }
23 template<class T>ListNode<T>* ListNode<T>::insertsurr(const T& data) {
24     ListNode<T>* newptr = new ListNode<T>(data);
25     newptr->surr = surr;
26     newptr->pre = this;
27     surr->pre = newptr;
28     surr = newptr;
29     return newptr;
30 }