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
|
#include <vector>
using namespace std;
template <class T> class DequeIterator;
template <class T>
class Deque {
public:
typedef DequeIterator<T> iterator;
Deque(): vecOne(), vecTwo() { }
Deque(const unsigned int size, const T& initial): vecOne(size/2, initial),
vecTwo(size-(size/2), initial) { }
Deque(const Deque<T> & d): vecOne(d.vecOne), vecTwo(d.vecTwo) { }
~Deque() { } // destructors for vecOne and vecTwo are automatically called
// never call a destructor explicitly
Deque & operator=(const Deque<T>&d){DequeIterator<T> theDeque;return d=theDeque;}
T & operator[](unsigned int);
T & front();
T & back();
bool empty() {return vecOne.empty() && vecTwo.empty();}
iterator begin() {return iterator(this, 0);}
iterator end(){return iterator(this, size());}
void erase(const iterator &);
void erase(const iterator &, const iterator &);
void insert(const iterator &, const T &);
int size() {return vecOne.size() + vecTwo.size();}
void push_front(const T & value) {vecOne.push_back(value);}
void push_back(const T & value) {vecTwo.push_back(value);}
void pop_front();
void pop_back();
protected:
vector<T> vecOne;
vector<T> vecTwo;
};
// Your code goes here ...
template <class T>
T & Deque<T>::operator[](unsigned int index)
{
//return given element for deque
int n=vecOne.size();
if(index<=n)
{
return vecOne[(n-1)-index];
}
else
{
return vecTwo[index-n];
}
}
template <class T>
T & Deque<T>::front()
{
//return first element in deque
if(vecOne.empty())
{
return vecTwo.front();
}
else
{
return vecOne.back();
}
}
template <class T>
T & Deque<T>::back()
{
if(vecOne.empty())
{
return vecTwo.back();
}
else
{
return vecOne.front();
}
}
template <class T>
void Deque<T>::erase(const iterator & itr)
{
int index=itr.index;
int n=vecOne.size();
if(index < n)
{
vecOne.erase(vecOne.begin() + ((n-1)-index));
}
else
{
vecTwo.erase(vecTwo.begin() + (n-index));
}
}
template <class T>
void Deque<T>::erase(const iterator &, const iterator &)
{
//???
}
template <class T>
void Deque<T>::insert(const iterator &, const T &)
{
//???
}
template <class T>
void Deque<T>::pop_front()
{
if(vecOne.empty())
{
vecTwo.erase(vecTwo.begin());
}
else
{
vecOne.pop_back();
}
}
template <class T>
void Deque<T>::pop_back()
{
if(vecTwo.empty())
{
vecOne.pop_back();
}
else
{
vecTwo.pop_back();
}
}
|
