Ciao a tutti,
a lezioni abbiamo implementato una lista semplice "unidirezionale" dove la
struct Node consiste di un valore e di uno unique_ptr al nodo successivo. Per fare pratica con gli smart pointers, ho deciso di implementare una "templated double linked list". I metodi che voglio ho inserito per ora sono :
- void push_front(const T& x)
- void push_back(const T& x)
- iterator substitute(iterator p, const T& x)
- iterator insert(iterator p, const T& x), che inserisce l'elemento x nella lista dopo p
Problema/Domanda:
Il metodo
insert funziona sempre, tranne quando viene chiamato in questo modo
auto it = insert(--p,valore)
dove
p, valore
sono rispettivamente un iteratore ed un intero, ad esempio.
Compila, ma quando eseguo ottengo segmentation fault. Sono certo che questo ha a che fare col fatto che il
nodo precedente è un raw pointer, mentre
quello successivo uno unique pointer, però non so come sistemare la mia funzione insert in modo da rendere possibile anche una chiamata di questo tipo. Vorrei questo perché
auto it = l.insert(++pp,valore);
produce il risultato sperato, come si può verificare nel main più avanti, ed è un peccato che non si possa fare anche con l'operatore --.
EDIT
Ho risolto, usando std::make_unique e sistemando push_back e push_front. Le correzioni sono già fatte nei listati qui sotto.
Per maggiore chiarezza, allego le varie parti del codice, suddiviso così:
Ho diviso il tutto in:
1. header Node.h
2. header Iterator.h
3. header List.h
4. main.cpp dove testo i metodi
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Qui di seguito il Node.h, dove c'è la struct Node: un Node ha come membri il valore dell'elemento, uno unique pointer all'elemento successivo, ed un raw pointer all'elemento precedente. Non voglio usare raw pointers.
#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});
}
}
~Node()=default;
//Move semantics, Copy semantics
void printNode(){
std::cout << "Data is: " << data <<"\n";
/*if(next){
std::cout << "Next is: " << next<<" with data: " << next->data <<"\n";
}if (previous){
std::cout << "Previous is: " <<previous<<" with data: " << previous->data <<"\n";
}*/
}
};
} //end namespace
#endif /* Node_h */
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Per poter scorrere la mia lista futura, ho costruito l'iteratore. Da notare che poiché
previous è uno raw pointer, l'operatore -- è implementato così:
__iterator& operator--(){
current=current->previous;
return *this;
}
e perciò differente dall'operatore ++, che è implementato utilizzando il metodo .get()
__iterator& operator++() {
current = current->next.get();
return *this;
}
Di seguito, il file Iterator.h nella sua interezza:
#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 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 */
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ecco infine la lista, nel file List.h
#include "Iterator.h"
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
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();
}
++_size;
}
template <typename O> //forward reference
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;
}
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 = std::make_unique<Node::Node<T>>(value);
auto prev = position.current ? position.current->previous : last;
auto ptr = prev? &prev->next:&first;
std::swap(*ptr,newNode);
(*ptr)->next=std::move(newNode);
(*ptr)->previous = prev;
++_size;
if (!last) {
last = first.get();
}
return iterator{ptr->get()};
}
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;
}
};
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ecco il main
#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); //r-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,9998);
std::cout << "My list after insertion: \t" << l<<std::endl;
auto it4 = l.insert(--p,200);
std::cout << "My list after insertion: \t" << l<<std::endl;
return 0;
}