Lista enlazada doble con punteros inteligentes: problemas con el método de inserción
Estoy tratando de implementar una lista enlazada doble con plantilla, siguiendo el libro de Stroustrup "Principios y práctica usando C ++", Capítulo 20.4. En lugar de punteros sin formato, quiero usar punteros únicos . El código está organizado de la siguiente manera:
- encabezado Node.h donde
Nodese implementa la estructura : aunique_pointerse usa para el siguiente nodo y uno sin formato para el anterior - encabezado Iterator.h donde
Iteratorse implementa - encabezado List.h donde
Listse implementa la clase - un main.cpp donde se prueban los métodos
He visto que ha habido otras preguntas bastante similares, como esta, pero no sé si el diseño de mi método de inserción iterator insert(iterator p, const T& x)está bien . En particular, obtengo una falla de segmentación si llamo auto it3 = insert(--p,4). ¿Está bien o debería arreglarlo?
Aquí está mi 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 */
Entonces, aquí está el 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 */
Aquí está el encabezado 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, aquí está el archivo main.cpp con las pruebas:
#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 :
Versión corregida 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;
}
Respuestas
Tiene varios problemas con la administración de la memoria en esta lista vinculada. La clave para recordar es que unique_ptrindica la propiedad de un objeto. El uso de release, resety, en menor medida, getes un olor a código: no siempre es incorrecto, pero a menudo es una indicación de que la clase se está utilizando incorrectamente. Por lo general, debería usar swapy mover-asignación en su lugar. Los mencionaré mientras trabajo en los archivos.
Una nota rápida: no he probado ni siquiera compilado el siguiente código; puede contener algunos errores.
Node.h
En general, esto está bien. El constructor "copy" ( Node(std::unique_ptr<Node>&)) probablemente debería eliminarse. Realmente no tiene sentido copiar un nodo y todos sus descendientes. Incluso si quisiera ese comportamiento, esta implementación tiene errores. Elimina todos los enlaces anteriores, por lo que tiene una lista de enlaces individuales que pretende ser una lista de enlaces dobles.
Iterador.h
Su clase de iterador no es del todo correcta. No funciona como enditerador. En particular, --l.end()exhibe un comportamiento indefinido porque elimina la referencia a un puntero nulo. En la práctica, las clases de iteradores tienden a necesitar una referencia a la colección de la que provienen.
Además, este iterador no cumple con los requisitos de un iterador bidireccional (sé que lo marca como un iterador hacia adelante, pero tampoco cumple con esos requisitos). En particular, viola:
- "lvalores de tipo Satisface Swappable"; Estoy un poco oxidado aquí, pero estoy bastante seguro de que su destructor declarado por el usuario evita que se genere el constructor de movimiento declarado implícitamente y el operador de asignación de movimiento; debe proporcionar esas funciones (por ejemplo, usar
= default) o unaswapfunción. - No admite los operadores de incremento y decremento de sufijo.
List.h
List::lastno está realmente implementado correctamente. Por lo que puedo entender, en realidad nunca se establece en otra cosa que no sea nullptrel código tal como está. En cualquier caso, esto no debería ser un unique_ptr, porque cualquier cosa a la que apunte ya pertenece a otro unique_ptr.
Así que cambiemos lasta a Node::Node<T>*. Tenemos los siguientes invariantes que son verdaderas antes y después de cada función miembro de salidas: Si _size == 0, first==last==nullptr. De otra manera,
firstapunta al primer nodo de la listafirst->previous == nullptr- Dado un nodo accesible
n,n->nextes nulo on->next.get() == n->next->previous lastapunta al último nodo accesible de la lista.last.nextes nulo._sizelos nodos son accesibles.
Necesitamos escribir nuestras funciones miembro para que estas invariantes sigan siendo verdaderas.
go_tonormalmente se lograría mediante la aplicación std::nextal iterador de inicio. Eso tiene una diferencia de comportamiento cuando intentas pasar del final de la lista; el uso std::nextresultaría en un comportamiento indefinido en ese caso. Si desea el comportamiento actual, puede implementarlo con algo como
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
Cuando usa unique_ptrpara administrar la memoria, generalmente no debe usar new. En su lugar, utilícelo std::make_uniquesi está usando C ++ 14 o posterior (y escriba el suyo make_uniqueen C ++ 11). Esto le permite mejorar la seguridad de excepción de su código. Prueba esto 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;
}
Aquí, el nodo se crea de manera segura para excepciones. No hay posibilidad de fugas first, ya que no lo publicamos (su código se filtraría firstsi la asignación fallara o si Nodeel constructor arrojó (debido al Tlanzamiento del constructor de movimientos)). Suponiendo que su swapy moveson operaciones sin lanzamiento, o push_fronttiene éxito y el nuevo elemento se ha insertado al principio, o la asignación falla, se push_frontarroja y la estructura de datos no se ha cambiado.
En cuanto a push_back, si no está usando lastaquí, no hay ninguna razón para hacerlo 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;
}
Nuevamente, nos aseguramos de que los invariantes de la clase se mantengan, incluso si lanzamos mientras construimos el nuevo nodo.
No creo que substitutesea una función razonable. El usuario de su lista debe escribir *it = x;y debe saber si su iterador es válido o no.
La semántica normal para insertes insertar un valor justo antes de que pase el iterador, no solo después. Esto permite insertinsertar en cualquier posición de la lista y significa que inserttiene semántica sensible cuando end()se pasa como 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());
}
Muévete class Nodey struct __iteratorentraclass List
Es muy extraño ver Node::Node<T>dentro del código. A Nodees un detalle de implementación de su List, por lo que debe declararse dentro class List. Lo mismo ocurre con __iterator. Por ejemplo:
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 cómo todo esto evita la necesidad de introducir namespaces o __prefijos ( que debe evitar ) para ocultarlos, y cómo esto reduce la cantidad de veces que tiene que escribir explícitamente <T>. Por supuesto, ahora todo tiene que ser declarado por dentro List.h, pero no veo eso como un inconveniente.
Creo que debería seguir el estándar C ++ insertpara contenedores pasando un beginy un enditerador, por ejemplo
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);