0
我正在編寫一個Deque的實現作爲編程練習，並且它不太好。我錯過了使測試主程序正確給定功能所需的幾個關鍵功能。在C++中實現Deque
這是到目前爲止我的代碼：
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
template <class T> class DequeIterator;
template <class T>
class Deque {
public:
typedef DequeIterator<T> iterator;
Deque(): vecOne(), vecTwo() { }
Deque(unsigned int size, T& initial): vecOne(size/2, initial), vecTwo(size-(size/2), initial) { }
Deque(Deque<T> & d): vecOne(d.vecOne), vecTwo(d.vecTwo) { }
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;
};
template <class T>//
T & Deque<T>::front()//returns the first element in the deque
{
if (vecOne.empty())
return vecTwo.front();
else
return vecOne.back();
}
template <class T>//
T & Deque<T>::back()//returns the last element in the deque
{
if (vecOne.empty())
return vecTwo.back();
else
return vecOne.front();
}
template <class T>//
T & Deque<T>::operator[] (unsigned int index)
{
int n = vecOne.size();
if (index < n)
return vecOne [ (n-1) - index ];
else
return vecTwo [ index - n ];
}
template <class T>//
Deque<T>::iterator DequeIterator<T>::operator ++ (int)
{
Deque<T>::iterator clone(theDeque, index);
index++;
return clone;
}
template <class T>//
void Deque<T>::pop_front()
{
}
template <class T>//
void Deque<T>::pop_back()
{
}
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>
class DequeIterator {
friend class Deque<T>;
typedef DequeIterator<T> iterator;
public:
DequeIterator(): theDeque(0), index(0) { }
DequeIterator(Deque<T> * d, int i): theDeque(d), index(i) { }
DequeIterator(const iterator & d): theDeque(d.theDeque), index(d.index) { }
T & operator*() { return (*theDeque)[index]; }
iterator & operator++(int) { ++index; return *this; }
iterator operator++();
iterator operator--(int) { --index; return *this; }
iterator & operator--();
bool operator==(const iterator & r) { return theDeque == r.theDeque && index == r.index; }
bool operator!=(const iterator & r) { return theDeque == r.theDeque && index != r.index; }
bool operator< (const iterator & r) { return theDeque == r.theDeque && index < r.index; }
T & operator[](unsigned int i) { return (*theDeque) [index + i]; }
iterator operator=(const iterator & r) { theDeque = r.theDeque; index = r.index; }
iterator operator+(int i) { return iterator(theDeque, index + i); }
iterator operator-(int i) { return iterator(theDeque, index - i); }
protected:
Deque<T> * theDeque;
int index;
};
main()
{
Deque<int> d;
d.push_back(10);
d.push_back(20);
assert(d.front() == 10);
assert(d.back() == 20);
d.push_front(1);
d.push_front(2);
d.push_front(3);
assert(d.front() == 3);
assert(d.back() == 20);
d.pop_back();
d.pop_back();
d.pop_back();
assert(d.front() == 3);
assert(d.back() == 2);
d.push_back(1);
d.push_back(0);
Deque<int>::iterator i;
int counter = 3;
for (i = d.begin(); i != d.end(); i++)
assert(*i == counter--);
for (counter = 0; counter < d.size(); counter++)
assert(d[counter] == d.size()-counter-1);
i = d.begin() + 3;
Deque<int>::iterator j(i), k;
k = j = i - 2;
assert(*k == 2);
for (i = d.begin(); not(i == d.end()); ++i)
cout << *i << " ";
cout << endl;
d.erase(d.begin()+3);
//d.erase(d.begin(), d.begin()+2);
assert(d.size() == 1);
assert(d[0] == 1);
Deque<int> c(d);
c.front() = 3;
assert(c.back() == 3);
c.push_front(1);
c.insert(c.begin(), 0);
c.insert(c.begin()+2, 2);
for (i = c.begin(); not(i == c.end()); ++i)
cout << *i << " ";
cout << endl;
for (counter = 0; counter < c.size(); counter++)
assert(c[counter] == counter);
cout << "SUCCESS\n";
}
我在想，如果有人能告訴我，我的功能從線路66回：
expected constructor, destructor, or type conversion before 'DequeIterator'
因爲我不知道我米做錯了。另外，如果有人願意給我一個pop_front（）函數的例子，以便我可以使用它來創建pop_back（）函數，那就太好了。最後，我已完成擦除功能，但我不知道如何去創建第二個，它基本上擦除了兩個迭代器範圍內的值，它在第176行中提到。
任何幫助都會不勝感激。先謝謝你。
請爲我們指出第66行，所以我們不必數數。還有第176行。 – 2011-03-07 01:21:15
我不確定兩個向量是否正確實現了雙端隊列。如果你有一個空的雙端隊列並且叫做push_back 100x，那麼它叫做pop_front 100x，它應該仍然是恆定時間。然而，在這個實現中，pop_fronts必須從vecTwo的前面移除，並且與法向矢量一樣低效。 – MerickOWA 2011-03-07 01:33:59
我認爲適當的實現是一個單一的向量和兩個索引'前'和'背部'的雙側。 – MerickOWA 2011-03-07 01:35:49