双链表的实现С++ 内容来源于 Stack Overflow，并遵循CC BY-SA 3.0许可协议进行翻译与使用

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

``````namespace pjc
{

class list
{
private:
struct node
{
double val = 0;
node *prev = nullptr;
node *next = 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);
``````

``````namespace pjc
{

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

}

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()
{
{
delete temp;
}
}

list &list::operator=(const pjc::list &rhs)
{
{
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++)
{
{
node *new_node = new node;
new_node->val = vec[i];
}
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)
{
}
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;
{
}
else
{
new_node->prev = nullptr;
}
num_elements++;
}

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

{
num_elements--;
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");
}

{
num_elements--;
tail = nullptr;
return;
}

num_elements--;
}

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

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

if (temp != nullptr)
{
}
}

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

void list::swap(pjc::list &rhs) {
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
{
}

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

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

double &list::front()
{
}

double const &list::front() const
{
}

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

``````list::iterator list::begin() {
}
``````

``````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) {}
``````

1 个回答

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

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