如何实现没有返回Doubly Linked列表大小的参数的函数？ int size（）const

Question

我需要实现以下功能：

int size() const;

1. function返回列表中存储的数据块数
2. 时间复杂度 - O（1）。

基本上我有一个名为DList的类，包含在DList.h中，它具有以下结构：

class DList
{
    struct Node
    {
            T data_;
            Node *next_;
            Node *prev_;
            Node(const T &data = T{}, Node *next = nullptr, Node *prev = nullptr)
            {
                    data_ = data;
                    next_ = next;
                    prev_ = prev;
            }
    };

    Node *front_;
    Node *back_;

  public:
    class const_iterator
    {
            friend class DList;

          protected:
            Node *curr_;
            //assign curr_ with n;
            const_iterator(Node *n)
            {
                    curr_ = n;
            }

          public:
            const_iterator()
            {
                    curr_ = nullptr;
            }
            const_iterator operator++()
            {
                    //++x
                    curr_ = curr_->next_;
                    return *this;
            };
            const_iterator operator++(int)
            {
                    //x++
                    const_iterator old = *this;
                    curr_ = curr_->next_;
                    return old;
            };
            const_iterator operator--()
            {
                    curr_ = curr_->prev_;
                    return *this;
            }
            const_iterator operator--(int)
            {
                    //x--
                    const_iterator old = *this;
                    curr_ = curr_->prev_;
                    return old;
            }
            bool operator==(const_iterator rhs)
            {
                    return (curr_ == rhs.curr_);
            }
            bool operator!=(const_iterator rhs)
            {
                    return (curr_ != rhs.curr_);
            }
            const T &operator*() const
            {
                    return curr_->data_;
            }
    };

    class iterator : public const_iterator
    {
            friend class DList;
            iterator(Node *n) : const_iterator(n) {}

          public:
            iterator() {}
            iterator operator++()
            {
                    //++x
                    this->curr_ = this->curr_->next_;
                    return *this;
            }
            iterator operator++(int)
            {
                    //x++
                    iterator old = *this;
                    this->curr_ = this->curr_->next_;
                    return old;
            }
            iterator operator--()
            {
                    //--x
                    this->curr_ = this->curr_->prev_;
                    return *this;
            }
            iterator operator--(int)
            {
                    //x--
                    iterator old = *this;
                    this->curr_ = this->curr_->prev_;
                    return old;
            }
            T &operator*()
            {
                    return this->curr_->data_;
            }
    };
    DList();
    ~DList();
    DList(const DList &rhs);
    DList &operator=(const DList &rhs);
    DList(DList &&rhs);
    DList &operator=(DList &&rhs);
    iterator begin()
    {
            return iterator(front_);
    }
    iterator end()
    {
            return iterator(nullptr);
    }
    const_iterator begin() const
    {
            return const_iterator(front_);
    }
    const_iterator end() const
    {
            return const_iterator(nullptr);
    }
    void push_front(const T &data);
    void push_back(const T &data);
    void pop_front();
    void pop_back();
    iterator insert(const T &data, iterator it);
    iterator search(const T &data);
    const_iterator search(const T &data) const;
    iterator erase(iterator it);
    iterator erase(iterator first, iterator last);
    bool empty() const;
    int size() const; <--------- THIS IS THE FUNCTION I NEED TO IMPLEMENT
 };

函数size()在测试程序main.cpp中被调用如下：

 DList<Record> recList;
 DList<int> intList;
 .
 .
 .
 .
 if (!checkList(recList, mirror, 15) || recList.empty() || recList.size() != 15)
     {
           passtest = false;
           cout << "Error 9a: Bug in = operator, no deepcopy?" << endl;
     }

Answer 1

对于O（1）复杂性，您需要保留在添加或删除节点时更新的运行计数。默认构造函数必须将其初始化为零，其他构造函数和赋值必须做正确的事（DTRT）。

class DList
{
    struct Node; 
    Node *front_;
    Node *back_;
    size_t count_;  

    public:
        Dlist()
           : front_(nullptr)
           , back_(nullptr)
           , count_(0)
        {}

    size_t size() const { return count_; }
    // etc..
}