双链表的实现С++

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (1)
  • 关注 (1)
  • 查看 (56)

这是我对双链表的一些方法的实现。但我有自定义迭代器,Const_Iterators和运算符的实现问题。

我的list.hpp文件

namespace pjc
{

class list
{
private:
  struct node
  {
    double val = 0;
    node *prev = nullptr;
    node *next = nullptr;
  };

  node *head = nullptr;
  node *tail = nullptr;
  size_t num_elements = 0;

public:
  class const_iterator
  {
    node *current_ptr = nullptr;
    const list *o_list = nullptr;

  public:
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = const double;
    using reference = const double &;
    using pointer = const double *;

    const_iterator() = default;
    const_iterator(node *ptr, const list *gen);

    const_iterator &operator++();
    const_iterator operator++(int);
    const_iterator &operator--();
    const_iterator operator--(int);

    reference operator*() const;
    pointer operator->() const;

    bool operator==(const const_iterator &rhs) const;
    bool operator!=(const const_iterator &rhs) const;

    friend class list;
  };

  class iterator
  {
    node *current_ptr = nullptr;
    const list *o_list = nullptr;

  public:
    using difference_type = std::ptrdiff_t;
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = double;
    using reference = double &;
    using pointer = double *;

    iterator() = default;
    iterator(node *ptr, const list *gen);

    iterator &operator++();
    iterator operator++(int);
    iterator &operator--();
    iterator operator--(int);

    reference operator*() const;
    pointer operator->() const;

    operator const_iterator() const;

    bool operator==(const iterator &rhs) const;
    bool operator!=(const iterator &rhs) const;

    friend class list;
  };

  list() = default;
  list(const list &rhs);
  list &operator=(const list &rhs);
  list(list &&rhs);
  list &operator=(list &&rhs);
  ~list();

.....

  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;
  const_iterator cbegin() const;
  const_iterator cend() const;

  std::pair<list, list> split(const_iterator place);


  void merge(list &rhs);


  void sort();
  bool operator!=(const list &lhs, const list &rhs);

  bool operator>(const list &lhs, const list &rhs);

  bool operator<=(const list &lhs, const list &rhs);

  bool operator>=(const list &lhs, const list &rhs);


  void swap(list &lhs, list &rhs);

我的list.cpp文件

namespace pjc
{

list::list(pjc::list &&rhs)
{
    head = rhs.head;
    tail = rhs.tail;
    num_elements = rhs.num_elements;

    rhs.head = rhs.tail = nullptr;
}

void list::copy_list(const pjc::list &rhs)
{
    for (node *current_node = rhs.head; current_node != nullptr; current_node = current_node->next)
    {
        this->push_back(current_node->val);
    }
}

list::list(const pjc::list &rhs)
{
    copy_list(rhs);
}

void list::free_list()
{
    while (head != nullptr)
    {
        node *temp = head;
        head = head->next;
        delete temp;
    }
    head = tail = nullptr;
}

list &list::operator=(const pjc::list &rhs)
{
    if (head != nullptr)
    {
        free_list();
    }

    copy_list(rhs);
    return *this;
}

list::~list()
{
    free_list();
}

list::list(const std::vector<double> &vec)
{
    for (unsigned i = 0; i < vec.size(); i++)
    {
        if (head == nullptr)
        {
            node *new_node = new node;
            new_node->val = vec[i];
            head = new_node;
            tail = head;
        }
        else
        {
            node *current = new node;
            current->val = vec[i];
            tail->next = current;
            current->prev = tail;
            tail = current;
        }
        num_elements++;
    }
}

void list::push_back(double elem)
{
    node *new_node = new node;
    new_node->val = elem;
    if (head == nullptr && tail == nullptr)
    {
        head = new_node;
        tail = head;
    }
    else
    {
        tail->next = new_node;
        new_node->prev = tail;
        new_node->next = nullptr;
        tail = new_node;
    }
    num_elements++;
}

void list::push_front(double elem)
{
    node *new_node = new node;
    new_node->val = elem;
    if (head == nullptr)
    {
        head = new_node;
        tail = head;
    }
    else
    {
        head->prev = new_node;
        new_node->next = head;
        new_node->prev = nullptr;
        head = new_node;
    }
    num_elements++;
}

void list::pop_back()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        num_elements--;
        head = nullptr;
        tail = nullptr;
        return;
    }

    tail = tail->prev;
    delete tail->next;
    tail->next = nullptr;
    num_elements--;
}

void list::pop_front()
{
    if (empty())
    {
        throw std::out_of_range("Can't pop from empty list");
    }

    if (head == tail)
    {
        delete head;
        num_elements--;
        head = nullptr;
        tail = nullptr;
        return;
    }

    head = head->next;
    delete head->prev;
    head->prev = nullptr;
    num_elements--;
}

void list::reverse()
{
    node *temp = nullptr;
    node *current = head;

    while (current != nullptr)
    {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }

    if (temp != nullptr)
    {
        head = temp->prev;
    }
}

list& list::list::operator=(pjc::list &&rhs) {
    if(this != &rhs){
        std::swap(*this, rhs);
    }
    return *this;
}

void list::swap(pjc::list &rhs) {
    std::swap(head, rhs.head);
    std::swap(num_elements, rhs.num_elements);
}

list::iterator &list::iterator::operator++()
{
    current_ptr = this->current_ptr->next;
    return *this;
}

list::iterator &list::iterator::operator--()
{
    current_ptr = this->current_ptr->prev;
    return *this;
}


list::iterator list::iterator::operator++(int)
{
    iterator old(*this);
    ++(*this);
    return old;
}

list::iterator list::iterator::operator--(int)
{
    iterator left(*this);
    --(*this);
    return left;
}

double &list::iterator::operator*() const
{
    return current_ptr->val;
}

list::iterator::pointer list::iterator::operator->() const
{
    return &(current_ptr->val);
}

bool list::iterator::operator==(const pjc::list::iterator &rhs) const
{
    return current_ptr == rhs.current_ptr;
}

bool list::iterator::operator!=(const pjc::list::iterator &rhs) const
{
    return current_ptr != rhs.current_ptr;
}

bool list::const_iterator::operator==(const pjc::list::const_iterator &rhs) const {
    return current_ptr == rhs.current_ptr;
}

bool list::const_iterator::operator!=(const pjc::list::const_iterator &rhs) const {
    return !(*this == rhs);
}

list::const_iterator& list::const_iterator::operator++() {
    current_ptr = current_ptr->next;
    return *this;
}

list::const_iterator list::const_iterator::operator++(int) {
    const_iterator old = *this;
    ++(*this);
    return old;
}

list::const_iterator& list::const_iterator::operator--() {
    current_ptr = current_ptr->prev;
    return *this;
}

list::const_iterator list::const_iterator::operator--(int) {
    const_iterator old = *(this);
    --(*this);
    return old;
}

list::const_iterator::const_iterator(pjc::list::node *ptr, const pjc::list *gen) {
    this->current_ptr = ptr;
    this->o_list = gen;
}

const double & list::const_iterator::operator*() const {
    return current_ptr->val;
}

list::const_iterator::pointer list::const_iterator::operator->() const {
    return &(current_ptr->val);
}

list::iterator::iterator(pjc::list::node *ptr, const pjc::list *gen) {
    this->current_ptr = ptr;
    this->o_list = gen;
}

bool list::operator==(const pjc::list &rhs) const {}

bool list::operator<(const pjc::list &rhs) const {}

bool list::empty() const
{
    return head == nullptr;
}

double &list::back()
{
    return this->tail->val;
}

double const &list::back() const
{
    return this->tail->val;
}

double &list::front()
{
    return this->head->val;
}

double const &list::front() const
{
    return this->head->val;
}

size_t list::size() const
{
    return this->num_elements;
}

您可以检查此代码是否有错误和内存泄漏?我是C ++的新手。当我尝试实现Iterator的方法begin(),end(),cbegin()atd。像这样,

list::iterator list::begin() {
    return list::iterator(head->next, *this)
}

我得到错误:没有用于初始化'list :: iterator'的匹配构造函数

请解释一下我做错了什么?

而且我也不知道如何实现这些方法:

bool operator!=(const list &lhs, const list &rhs);
bool operator>(const list &lhs, const list &rhs);
bool operator<=(const list &lhs, const list &rhs);
bool operator>=(const list &lhs, const list &rhs);
list& list::list::operator=(pjc::list &&rhs) {}
std::pair<list, list> list::split(pjc::list::const_iterator place) {}
void list::merge(pjc::list &rhs) {}

谢谢你的回复:)

提问于
用户回答回答于

您尝试调用的构造函数是这样定义的

iterator(node *ptr, const list *gen);

即第二个参数是指向a的指针list。但你这样称呼它

return list::iterator(head->next, *this)

但是*this是一个list。你只需要this,这是一个指针list

所属标签

可能回答问题的人

  • 应用案例分享

    1 粉丝490 提问5 回答
  • o o

    4 粉丝495 提问5 回答
  • 找虫虫

    5 粉丝0 提问4 回答
  • 学生

    8 粉丝476 提问3 回答

扫码关注云+社区

领取腾讯云代金券