C++中双端队列的实现

Question

我正在编写 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 行中引用。

任何帮助将不胜感激。先感谢您。

Answer 1

至于错误，您可能需要在该行的 Deque::iterator 之前添加 typename 。

typename Deque<T>::iterator DequeIterator<T>::operator++(int)

Answer 2

我认为实现双端队列是一个很好的编程练习。但先决条件是实现向量和列表。 deque 是实现起来最复杂的 std::container 之一。您应该从更简单的之一（向量和列表）开始。

Answer 3

嗯，您在第 65 行得到了错误，因为您返回了一个尚未定义的类的对象。您只有类 DequeIterator 的前向声明（原型），而不是实现。

Answer 4

void pop_back() {
  vecTwo.pop_back();
}

void pop_front() {
  vecOne.pop_back();
}