随笔档案

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