用了双向链表,快排,<<,=,[]重载,还有erase的实现比较好玩
1 //my Vecter ;T need "operator<"
2
3 #include <iostream>
4 using std::cout;
5 using std::ostream;
6
7 template <typename T>
8 struct item
9 {
10 item():value(),next(NULL),last(NULL){}
11 item(const T t):value(t),next(NULL),last(NULL){}
12 item *next,*last;
13 T value;
14 };
15
16 template <typename T>
17 class Vector
18 {
19 public:
20 Vector():m_size(0),m_head(NULL){}
21 int size() const{return m_size;}
22 bool empty() const{return m_size?true:false;}
23 T front() const{return m_size?m_head->value:T();}
24 T back() const{return m_size?end()->value:T();}
25 bool push_back(const T&);
26 bool push_front(const T&);
27 T pop_back();
28 T pop_front();
29 void erase(int pos,int num);
30 void clear();
31 T& operator[](const int key);
32 void sort();
33 Vector<T>& operator=(Vector<T>& v);
34
35 private:
36 item<T> * end() const;
37 int m_size;
38 item<T> *m_head;
39 int partition(int,int);
40 void qsort(int,int);
41 };
42
43 template <typename T>
44 bool Vector<T>::push_back(const T& t)
45 {
46 if(m_size==0)
47 {
48 m_head=new item<T>;
49 m_head->value=t;
50 }
51 else
52 {
53 item<T>* save=end();
54 save->next=new item<T>(t);
55 save->next->last=save;
56 }
57 m_size++;
58 return true;
59 }
60
61 template <typename T>
62 bool Vector<T>::push_front(const T& t)
63 {
64 if(m_size==0)
65 {
66 m_head=new item<T>(t);
67 return true;
68 }
69 item<T> *save=m_head;
70 m_head=new item<T>(t);
71 m_head->next=save;
72 m_size++;
73 if(save!=NULL)save->last=m_head;
74 return true;
75 }
76
77 template <typename T>
78 T Vector<T>::pop_front()
79 {
80 if(m_size==0)return T();
81 if(m_size==1)
82 {
83 T t=m_head->value;
84 delete m_head;
85 m_head=NULL;
86 m_size--;
87 return t;
88 }
89 item<T>* save=m_head->next;
90 T t=m_head->value;
91 delete m_head;
92 m_head=save;
93 save->last=m_head;
94 m_size--;
95 return t;
96 }
97
98 template <typename T>
99 T Vector<T>::pop_back()
100 {
101 if(m_size==0)return T();
102 if(m_size==1)
103 {
104 T t=m_head->value;
105 delete m_head;
106 m_head=NULL;
107 m_size--;
108 return t;
109 }
110 item<T>* e=end();
111 T t=e->value;
112 e->last->next=NULL;
113 delete e;
114 m_size--;
115 return t;
116 }
117
118 template <typename T>
119 void Vector<T>::erase(int pos,int num)
120 {
121 if(m_size<pos+1)return;
122 else
123 {
124 item<T> *p=m_head,*save;
125 for(int i=0;i<pos;i++){p=p->next;}
126 for(int i=0;i<num;i++)
127 {
128 if(p==NULL)break;
129 save=p;
130 if(p->last==NULL){m_head=p->next;}
131 else p->last->next=p->next;
132 if(p->next!=NULL)p->next->last=p->last;
133 p=p->next;
134 delete save;
135 m_size--;
136 }
137 }
138 }
139
140 template <typename T>
141 T& Vector<T>::operator[](const int key)
142 {
143 if(key+1>m_size)m_size=(key+1);
144 item<T> *p=m_head,*save;
145 for(int i=0;i<key+1;i++)
146 {
147 if(m_head==NULL)
148 {
149 m_head=new item<T>;
150 save=p=m_head;
151 }
152 else if(p==NULL)
153 {
154 p=new item<T>;
155 p->last=save;
156 save->next=p;
157 }
158 save=p;
159 p=p->next;
160 }
161 return save->value;
162 }
163
164 template <typename T>
165 void Vector<T>::clear()
166 {
167 erase(0,m_size);
168 }
169
170 template <typename T>
171 item<T>* Vector<T>::end() const
172 {
173 if(m_size==0)return NULL;
174 item<T> *p=m_head;
175 for(; p->next!=NULL; p=p->next);
176 return p;
177 }
178
179 template <typename T>
180 int Vector<T>::partition(int p,int r)
181 {
182 T x=(*this)[r];
183 int i=p-1;T temp;
184 for(int j=p;j<=r-1;j++)
185 {
186 if((*this)[j]<x)
187 {
188 i++;
189 if(i!=j)
190 {temp=(*this)[i];(*this)[i]=(*this)[j];(*this)[j]=temp;}
191 }
192 }
193 if(r!=i+1)
194 {temp=(*this)[r];(*this)[r]=(*this)[i+1];(*this)[i+1]=temp;}
195 return i+1;
196 }
197
198 template <typename T>
199 void Vector<T>::sort()
200 {
201 qsort(0,m_size-1);
202 }
203 template <typename T>
204 void Vector<T>::qsort(int p,int r)
205 {
206 if(p<r)
207 {
208 int q=partition(p,r);
209 qsort(p,q-1);
210 qsort(q+1,r);
211 }
212 }
213
214 template<typename T>
215 ostream& operator<<(ostream& out,Vector<T> &v)
216 {
217 for(int i=0;i<v.size();i++)
218 {
219 out<<v[i]<<" ";
220 }
221 return out;
222 }
223 template<typename T>
224 Vector<T>& Vector<T>::operator=(Vector& v)
225 {
226 this->clear();
227 m_size=v.m_size;
228 item<T> *p=m_head,*vp=v.m_head;
229 for(int i=0;i<m_size;i++)
230 {
231 p=new item<T>(vp->value);
232 p=p->next;
233 vp=vp->next;
234 }
235 return *this;
236 }
237
238 int main()
239 {
240 int i=10;
241 Vector<int> v;
242 v.push_back(i);i--;
243 v.push_front(i);
244 v.push_back(i);i--;
245 v.push_front(i);
246 v[8]=5414;
247 cout<<v<<"\n";
248 v.erase(2,3);
249 cout<<v<<"\n";
250 v.clear();
251 for(int i=10;i>0;i--)v[i]=5-i;
252 v[5]=12;
253 v[15]=77;
254 cout<<v<<"\n";
255 v.sort();
256 cout<<"V1= "<<v<<"\n";
257 Vector<int> v2=v;
258 cout<<"V2= "<<v2<<"\n";
259 return 0;
260 }
原文链接: https://www.cnblogs.com/backinfile/p/5827786.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/239772
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!