首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >双链表的实现С++

双链表的实现С++
EN

Stack Overflow用户
提问于 2018-12-13 05:53:41
回答 1查看 0关注 0票数 0

这是我对双链表的一些方法的实现。但我有自定义迭代器,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) {}

谢谢你的回复:)

EN

Stack Overflow用户

发布于 2018-12-13 14:54:02

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

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

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

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

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

票数 0
EN
查看全部 1 条回答
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/-100006285

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档