Double Linked List com smart pointers: problemas com o método de inserção
Estou tentando implementar uma lista duplamente vinculada modelada, seguindo o livro de Stroustrup "Principles and Practice using C ++", Capítulo 20.4. Em vez de ponteiros brutos, quero usar ponteiros exclusivos . O código é organizado da seguinte forma:
- header Node.h onde a estrutura
Nodeé implementada: aunique_pointeré usado para o próximo nó, e um bruto para o anterior - cabeçalho Iterator.h onde o
Iteratoré implementado - cabeçalho List.h onde a classe
Listé implementada - um main.cpp onde os métodos são testados
Eu vi que houve outras perguntas bem semelhantes, como esta, mas não sei se o design do meu método de inserção: iterator insert(iterator p, const T& x)está correto . Em particular, recebo uma falha de segmentação se ligar auto it3 = insert(--p,4). Está tudo bem ou devo consertar?
Aqui está meu Node.h
#ifndef Node_h
#define Node_h
#include <algorithm>
#include <iostream>
#include <memory> // std::unique_ptr
#include <utility> // std::move
namespace Node {
template <typename T>
struct Node {
T data;
std::unique_ptr<Node> next;
Node* previous;
Node() noexcept = default;
explicit Node(const T& _data) : data{_data}, next{nullptr},previous{nullptr} {
std::cout << "l-value"<<std::endl;
}
Node(const T& _data, Node* _next, Node* _previous): data{_data}, next{_next}, previous{_previous} {}
explicit Node(T&& x) : data{std::move(x)} {
std::cout << "r-value" << std::endl;
}
Node(T&& x, Node* _next, Node* _previous) : data{std::move(x)}, next{_next}, previous{_previous} {
std::cout << "r-value" << std::endl;
}
explicit Node(const std::unique_ptr<Node> &x) : data{x->data} {
if (x->next){
next.reset(new Node{x->next});
}
// if (x->previous){
// previous.reset(new Node{x->previous});
// }
}
~Node()=default;
//Move semantics, Copy semantics
void printNode(){
std::cout << "Data is: " << data <<"\n";
}
};
} //end namespace
#endif /* Node_h */
Então, aqui está o Iterator.h
#ifndef Iterator_h
#define Iterator_h
#include "Node.h"
#include <iterator>
template <typename T >
struct __iterator {;
using NodeT = Node::Node<T>;
NodeT* current;
//public:
using value_type = T;
using difference_type = std::ptrdiff_t;
using iterator_category = std::forward_iterator_tag;
using reference = value_type&;
using pointer = value_type *;
explicit __iterator(NodeT* p) : current{p} {}
__iterator() noexcept=default;
~__iterator()=default;
reference operator*() const noexcept{
return current->data;
}
pointer operator->() const noexcept{
return &**this;
}
__iterator& operator++() {
current = current->next.get();
return *this;
}
__iterator& operator--(){
current=current->previous; //previous is just a raw pointer
return *this;
}
friend bool operator==(__iterator &a, __iterator &b) {
return a.current == b.current;
}
friend bool operator!=(__iterator &a, __iterator &b) { return !(a == b); }
};
#endif /* Iterator_h */
Aqui está o cabeçalho List.h
#include "Iterator.h"
#include <cassert>
template <typename T>
class List {
private:
std::unique_ptr<Node::Node<T>> first;
std::unique_ptr<Node::Node<T>> last;
int _size;
public:
using iterator = __iterator<T>;
iterator begin(){return iterator{first.get()};}
iterator end(){return iterator{nullptr};} //one past the last
iterator go_to(const int n){
assert(n>=0);
int i=0;
if (n < _size) {
auto tmp{begin()};
while (i<n) {
++tmp;
++i;
}
return tmp;
}else{
return iterator{nullptr};
}
}
List() : first{nullptr}, last{nullptr},_size{0} {}
~List() noexcept = default;
template <typename O>
void push_front(O &&x) { // forwarding ref. not r-value
first.reset(new Node::Node<T>{std::forward<O>(x),first.release(),nullptr});
if (_size==0) {
last.reset(nullptr);
}
++_size;
}
template <typename O> //forward reference
void push_back(O&& x){
auto tmp = first.get();
auto _node = new Node::Node<T>{std::forward<O>(x)};
if (!tmp) {
first.reset(_node);
return;
}
while (tmp->next) {
tmp = tmp->next.get();
}
tmp->next.reset(_node);
++_size;
}
iterator substitute(iterator p, const T& x){
//_size must not be incremented!
iterator tmp{p};
if(tmp.current){
*tmp = x;
return tmp;
}else{
return iterator{nullptr};
}
}
iterator insert(iterator position,const T& value) {
auto newNode = new Node::Node<T>(value, position.current->next.get(), position.current);
std::cout << position.current << std::endl;
if (position.current == last.get() ) {
last.reset(newNode);
}
position.current->next.release(); //otherwise: "pointer being freed was not allocated"
position.current->next.reset(newNode); //set next of previous node to newNode
++_size;
return position;
}
friend std::ostream& operator<<(std::ostream& os, List& l){
auto itStop = l.end();
os << "The list has " << l._size << " elements"<<"\n";
for (auto it = l.begin(); it!=itStop; ++it) {
os<< *it << " ";
}
return os;
}
};
Finalmente, aqui está o arquivo main.cpp com os testes:
#include "List.h"
int main() {
List<int> l{};
int i=8;
l.push_front(i); //l-value
l.push_back(4); //r-value
l.push_back(i+2); //r-value
l.push_back(95); //r-value
l.push_front(29); //l-value
l.push_front(i*i); //r-value
std::cout << "My list so far: " << l<<std::endl;
auto p{l.go_to(3)};
auto itt = l.substitute(p, 29);
std::cout << "My list after substitution: \t" << l<<std::endl;
auto pp{l.go_to(2)};
auto it2 = l.insert(pp,98);
std::cout << "My list after insertion: \t" << l<<std::endl;
auto it3= l.insert(--pp,998);
std::cout << "My list after insertion: \t" << l<<std::endl;
return 0;
}
EDITAR :
Versão corrigida de push_front:
template <typename O>
void push_front(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
std::swap(node, first);
first->next = std::move(node);
if (_size == 0) {
assert(!last);
assert(!first->next);
last = first.get();
}else{
first->next->previous = first.get()
}
++_size;
}
Respostas
Você tem vários problemas com o gerenciamento de memória nesta lista vinculada. A principal coisa a lembrar é que unique_ptrindica a propriedade de um objeto. O uso de release, resete em menor extensão getsão um cheiro de código: nem sempre errado, mas geralmente uma indicação de que a classe está sendo usada incorretamente. Normalmente, você deve usar swape mover-atribuição em vez disso. Vou destacar isso enquanto trabalho nos arquivos.
Uma nota rápida: não testei nem compilei o código a seguir; pode conter alguns erros.
Node.h
Isso está quase tudo bem. O construtor "copiar" ( Node(std::unique_ptr<Node>&)) provavelmente deve ser removido. Realmente não faz sentido copiar um nó e todos os seus descendentes. Mesmo se você quisesse esse comportamento, essa implementação tem bugs. Ele remove todos os links anteriores, para que você tenha uma lista de links individuais que finge ser uma lista de links duplos.
Iterator.h
Sua classe iteradora não está correta. Não funciona como um enditerador. Em particular, --l.end()exibe um comportamento indefinido porque desreferencia um ponteiro nulo. Na prática, as classes do iterador tendem a precisar de uma referência à coleção de onde vêm.
Além disso, esse iterador não atende aos requisitos de um iterador bidirecional (sei que você marca isso como um iterador direto, mas também não atende a esses requisitos). Em particular, viola:
- "lvalores do tipo Satisfaz a troca"; Estou um pouco enferrujado aqui, mas tenho quase certeza de que seu destruidor declarado pelo usuário impede que o construtor move declarado implicitamente e o operador de atribuição de movimento sejam gerados; você deve fornecer essas funções (por exemplo, usando
= default) ou umaswapfunção. - Ele não suporta os operadores de incremento e decremento postfix.
List.h
List::lastnão está realmente implementado corretamente. Até onde eu posso entender, na verdade nunca é definido para nada além nullptrdo código como está. Em qualquer caso, não deve ser um unique_ptr, porque tudo o que ele aponta já pertence a outro unique_ptr.
Então, vamos mudar lastpara um Node::Node<T>*. Temos as seguintes invariantes que são verdadeiras antes e depois de cada função de membro saídas: Se _size == 0, first==last==nullptr. De outra forma,
firstaponta para o primeiro nó da listafirst->previous == nullptr- Dado um nó alcançável
n,n->nexté nulo oun->next.get() == n->next->previous lastaponta para o último nó alcançável na lista.last.nexté nulo._sizenós são alcançáveis.
Precisamos escrever nossas funções-membro para que essas invariantes permaneçam verdadeiras.
go_tonormalmente seria alcançado aplicando- std::nextse ao iterador inicial. Isso tem uma diferença de comportamento quando você está tentando ir além do final da lista; usar std::nextresultaria em comportamento indefinido nesse caso. Se você quiser o comportamento atual, pode implementá-lo com algo como
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Quando você está usando unique_ptrpara gerenciar memória, geralmente não deve usar new. Em vez disso, use std::make_uniquese estiver usando C ++ 14 ou posterior (e escreva seu próprio make_uniqueem C ++ 11). Isso permite que você melhore a segurança de exceção de seu código. Experimente para push_front:
template <typename O>
void push_front(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
swap(node, first); // assuming you implement swap or add a "using std::swap;" on the previous line
first->next = std::move(node);
if (_size == 0) {
assert(!last);
assert(!first->next);
last = first.get();
}
++_size;
}
Aqui, o nó é criado de maneira segura para exceções. Não há chance de vazamento first, uma vez que não o liberamos (seu código vazaria firstse a alocação falhou ou se Nodeo construtor de jogou (devido ao Tlançamento do construtor de movimento)). Assumindo que suas operações swape movenão sejam lançadas, ambas são push_frontbem-sucedidas e o novo elemento foi inserido no início ou a alocação falha, push_frontlança e a estrutura de dados não foi alterada.
Quanto a push_back, se você não está usando lastaqui, não há motivo para usar last.
template <typename O>
void push_back(O&& x) {
auto node = std::make_unique<Node::Node<T>>(std::forward<O>(x));
if (_size == 0) {
assert(!last);
assert(!first);
first = std::move(node);
last = node.get();
_size = 1;
return;
}
assert(!last->next);
node->previous = last;
last->next = std::move(node);
last = last->next.get();
++_size;
}
Novamente, garantimos que as invariantes da classe se mantêm, mesmo se lançarmos durante a construção do novo nó.
Não acho que substituteseja uma função razoável. O usuário da sua lista deve escrever *it = x;e saber se seu iterador é válido ou não.
A semântica normal para inserté inserir um valor logo antes do iterador ser transmitido, não logo depois. Isso permite insertinserir em qualquer posição da lista e significa que inserttem semântica sensível quando end()é passado como o iterador.
iterator insert(iterator it, const T& value) {
auto node = std::make_unique<Node::Node<T>>(value);
auto prev = it.current ? it.current->previous : last;
auto ptr = prev ? &first : &prev->next;
swap(*ptr, node);
(*ptr)->next = std::move(node);
(*ptr)->previous = prev;
++_size;
if (!last) last = first.get();
return iterator(ptr->get());
}
Mover class Nodee struct __iteratorentrarclass List
É muito estranho ver Node::Node<T>dentro do código. A Nodeé um detalhe de implementação seu List, por isso deve ser declarado internamente class List. O mesmo vale para __iterator. Por exemplo:
template<typename T>
class List {
class Node {
T data;
std::unique_ptr<Node> next;
Node *previous;
};
std::unique_ptr<Node> first;
std::unique_ptr<Node> last;
...
public:
class iterator {
Node *current;
public:
using value_type = T;
...
};
iterator begin() {...};
...
};
Observe como tudo isso evita a necessidade de introduzir namespaces ou __prefixos ( que você deve evitar ) para ocultá-los, e como isso reduz o número de vezes que você precisa escrever explicitamente <T>. Claro, agora tudo tem que ser declarado internamente List.h, mas não vejo isso como uma desvantagem.
Acho que você deve seguir o padrão C ++ insertpara contêineres, passando um begine um enditerador, por exemplo
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);