スマートポインタを使用した二重リンクリスト：挿入メソッドの問題
Stroustrupの著書「C ++を使用した原則と実践」の第20.4章に従って、テンプレート化された二重リンクリストを実装しようとしています。生のポインタの代わりに、一意のポインタを使用したいと思います。コードは次のように構成されています。
- 構造体
Nodeが実装されているヘッダーNode.h ：aunique_pointerは次のノードに使用され、rawノードは前のノードに使用されます Iteratorが実装されているヘッダーIterator.h- クラス
Listが実装されているヘッダーList.h - メソッドがテストされるmain.cpp
私のような他のかなり類似した質問、があったことを見てきたこの1しかし、私のinsertメソッドの設計があれば、私にはわからない：iterator insert(iterator p, const T& x)大丈夫です。特に、を呼び出すとセグメンテーション違反が発生しますauto it3 = insert(--p,4)。これは大丈夫ですか、それとも修正する必要がありますか？
これが私の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 */
次に、これが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 */
これがヘッダー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;
}
};
最後に、テストを含むmain.cppファイルを次に示します。
#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;
}
編集：
の修正バージョン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;
}
回答
このリンクリストのメモリ管理には多くの問題があります。覚えておくべき重要なことunique_ptrは、オブジェクトの所有権を示すことです。使用release、resetおよびより少ない程度にはget常に間違っていないが、クラスが誤って使用されていることが多い適応症：コードのにおいです。通常はswap、代わりにムーブ代入を使用する必要があります。ファイルを処理するときに、これらを呼び出します。
簡単なメモ：私は次のコードをテストしたり、コンパイルしたりしていません。いくつかのエラーが含まれている可能性があります。
Node.h
これはほとんど問題ありません。「コピー」コンストラクター（Node(std::unique_ptr<Node>&)）はおそらく削除する必要があります。ノードとそのすべての子孫をコピーすることは実際には意味がありません。その動作が必要な場合でも、この実装にはバグがあります。以前のすべてのリンクが削除されるため、二重リンクリストのふりをする単一リンクリストが得られます。
Iterator.h
イテレータクラスは完全に正しくありません。endイテレータとしては機能しません。特に、--l.end()nullポインターを逆参照するため、未定義の動作を示します。実際には、イテレータクラスは、それらが由来するコレクションへの参照を必要とする傾向があります。
さらに、このイテレーターは双方向イテレーターの要件を満たしていません（これを順方向イテレーターとしてマークしていることは知っていますが、これらの要件も満たしていません）。特に、次の違反があります。
- "タイプの左辺値はSwappableを満たします"; ここでは少し錆びていますが、ユーザーが宣言したデストラクタが、暗黙的に宣言されたムーブコンストラクタとムーブ代入演算子が生成されないようにしていると確信しています。これらの関数（たとえば、を使用
= default）または関数を提供する必要がありますswap。 - 接尾辞のインクリメントおよびデクリメント演算子はサポートしていません。
List.h
List::last実際には正しく実装されていません。私の知る限り、実際にnullptrはコード以外に設定されることはありません。いずれにせよ、これは、を指すものはすでに別のによって所有されているため、であってはなりません。unique_ptrunique_ptr
それでは、に変更lastしましょうNode::Node<T>*。各メンバー関数が終了する前後に当てはまる次の不変条件があります。の場合_size == 0、first==last==nullptr。さもないと、
firstリストの最初のノードを指しますfirst->previous == nullptr- 到達可能なノードが与えられた場合
n、n->nextはnullまたはn->next.get() == n->next->previous lastリスト内の最後の到達可能なノードを指します。last.next無効です。_sizeノードに到達可能です。
これらの不変条件が真のままであるように、メンバー関数を作成する必要があります。
go_to通常std::next、開始イテレータに適用することで実現されます。リストの最後を超えようとしているときは、動作に違いがあります。std::nextその場合、を使用すると未定義の動作になります。現在の動作が必要な場合は、次のようなもので実装できます。
iterator go_to(const int n) const {
if (n >= _size) {
return end();
} else {
return std::next(begin(), n);
}
}
を使用unique_ptrしてメモリを管理している場合、通常はを使用しないでくださいnew。代わりに、std::make_uniqueC ++ 14以降を使用している場合に使用します（make_uniqueC ++ 11で独自に記述します）。これにより、コードの例外安全性を向上させることができます。これを試してみてください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;
}
ここでは、ノードは例外安全な方法で作成されます。firstリリースしないため、リークの可能性はありません（first割り当てが失敗した場合、またはNodeのコンストラクTターがスローされた場合（'moveコンストラクターがスローされたため）、コードがリークします）。とがスローなしの操作であると仮定するswapとmove、push_front成功して新しい要素が最初に挿入されたか、割り当てが失敗してpush_frontスローされ、データ構造が変更されていません。
に関してはpush_back、lastここを使わないのなら、持っている理由は全くありません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;
}
ここでも、新しいノードの構築中にスローした場合でも、クラスの不変条件が保持されるようにします。
substitute合理的な機能ではないと思います。リストのユーザーは書き込み*it = x;を行う必要があり、イテレーターが有効かどうかを知っている必要があります。
の通常のセマンティクスは、イテレータが渡された直後ではなく、insert直前に値を挿入することです。これによりinsert、リスト内の任意の位置に挿入できます。これは、がイテレーターとして渡されたinsertときに意味のあるセマンティクスがあることを意味しend()ます。
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());
}
移動class Nodeしstruct __iteratorてclass List
Node::Node<T>コードの内部を見るのは非常に奇妙です。ANodeはの実装の詳細であるListため、内で宣言する必要がありclass Listます。同じことが__iterator。にも当てはまります。例えば：
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() {...};
...
};
これらすべてが、それらを非表示にするためにnamespacesまたは__プレフィックス（避けるべき）を導入する必要性をどのように回避するか、そしてこれが明示的に書く必要がある回数をどのように減らすかに注意してください<T>。もちろん、今ではすべてを内部List.hで宣言する必要がありますが、それが欠点だとは思いません。
たとえばinsert、beginとendイテレータを渡すことで、コンテナのC ++標準に従う必要があると思います。
template<typename T>
void insert(Iterator begin, Iterator begin2, Iterator end2);
void insert(Iterator begin, T value);