双方向リストの要素の追加がうまくいかない

前提・実現したいこと

C++ の勉強のために双方向リスト実装をしたいです。

発生している問題・エラーメッセージ

うまくリストの更新ができません。
例えば

input
13 5
2set 1 10
3set 2 20
4get 1

と入力したとき期待する出力は　10　なのですが、
実際の出力が

output
120

となってしまいます。

該当のソースコード

c++
1#include <bits/stdc++.h>
2using namespace std;
3struct Node
4{
5    Node* next;
6    Node* prev;
7    int key;
8    int value;
9    Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
10    Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
11};
12
13class LRarray
14{
15public:
16    int capacity;
17
18    Node* head;
19    Node* tail;
20
21    map<int,Node*> mp;
22    
23    LRarray(int);
24    void set(int,int); // key value
25    void get(int);// key
26};
27
28LRarray::LRarray(int cp)
29{
30    this -> capacity = cp;
31    this -> head = new Node(this -> tail,NULL,0,0);
32    this -> tail = new Node(NULL,this -> head,0,0);
33}
34
35void LRarray::set(int k,int v)
36{
37        Node* second = new Node(this -> head -> prev,this->head ,k,v);
38        this -> head -> prev -> next = second;
39        this -> head -> prev = second;
40        this -> mp[k] = second;
41        if( (int)(this -> mp.size() ) > ( this -> capacity ) ){
42            cout << "capacity: " << this -> capacity << endl;
43            cout << "size: " << this -> mp.size() << endl;
44            cout << "Too many items" << endl;
45        }
46　　　　delete second;
47        
48
49}
50void LRarray::get(int k)
51{
52    auto itr = this -> mp.find(k);
53    if(itr != this -> mp.end()){
54        cout << this-> mp[k]->value << endl;
55    }else{
56        cout << "There is no value attached key: " << k << endl;
57    }
58}
59
60int main() {
61    
62    int n;
63    cin >> n; //入力回数
64
65    int c;
66    cin >> c; //capasity of array
67
68    LRarray arr(c);
69
70    for(int i = 0;i<n;i++){
71        string command;
72        cin >> command;
73        if(command == "set"){
74            int key,value;
75            cin >> key >> value;
76            arr.set(key,value);
77        }else if(command == "get"){
78            int k;
79            cin >> k;
80            arr.get(k);            
81        }        
82    }
83
84
85    return 0;
86}

試したこと

gdbで実行時のポインタのさしているメモリの番地を確認しました。
arr.set を実行しているとき毎回同じ番地に second が作られていて、リストの要素の追加がうまくいっていないです。
どうすればこれを解決できるのか調べ方がよくわかっていません。

補足情報（FW/ツールのバージョンなど）

Visual Studio Code
バージョン: 1.61.2 (user setup)
コミット: 6cba118ac49a1b88332f312a8f67186f7f3c1643
日付: 2021-10-19T14:57:20.575Z
Electron: 13.5.1
Chrome: 91.0.4472.164
Node.js: 14.16.0
V8: 9.1.269.39-electron.0
OS: Windows_NT x64 10.0.19043

episteme

2021/10/28 07:07

ところで、なんでlist内にstd::mapがあるんですか?

退会済みユーザー

2021/10/28 07:12

listに要素が追加できてるか見たかったのでmapを使って例を試してました。

行動規範の内容に同意します

回答1件

ベストアンサー

[回答ではありません]

C++
1void LRarray::set(int k,int v)
2{
3        Node* second = new Node(this -> head -> prev,this->head ,k,v);
4        this -> head -> prev -> next = second;
5        this -> head -> prev = second;
6        this -> mp[k] = second;
7        if( (int)(this -> mp.size() ) > ( this -> capacity ) ){
8            cout << "capacity: " << this -> capacity << endl;
9            cout << "size: " << this -> mp.size() << endl;
10            cout << "Too many items" << endl;
11        }
12        delete second; // キャパオーバーじゃなくてもdeleteしてるけど...いいの?
13}

投稿2021/10/28 06:52

episteme

総合スコア16612

退会済みユーザー

2021/10/28 07:01

ありがとうございます。修正しました。

episteme

2021/10/28 07:05 編集

「修正しても問題は解消しなかった」んですね? setのたびにlist全部をプリントしてはいかがでしょうか。期待する結果が得られますか?

退会済みユーザー

2021/10/28 07:06

delete の位置を修正したらうまくいきました! ありがとうございました。

episteme

2021/10/28 07:08

get() 時に map使って検索したら勉強にならんのでは?

episteme

2021/10/28 07:13

質問のコードを修正したらQ&Aが台無しになるってこと、理解してますか?

退会済みユーザー

2021/10/28 07:15

確かにそうです。よく理解してませんでした。

退会済みユーザー

2021/10/28 07:22

get()の時に key の探索の仕方も考えた方がいいということでしょうか？

episteme

2021/10/28 07:22

で、listに追加した"後で"キャパオーバーを判定していいの? listに残ったままdeleteしちゃうけど。

episteme

2021/10/28 07:23

> get()の時に key の探索の仕方も考えた方がいいということでしょうか？「listに要素が追加できてるか見たかったのでmapを使って例を試してました」なら、最終的には取り除かんならんでしょ? だったらget()の実装にmap使ったらダメでしょ?

退会済みユーザー

2021/10/28 07:29

> で、listに追加した"後で"キャパオーバーを判定していいの? listに残ったままdeleteしちゃうけど。確かに判定の順番がおかしいです。

退会済みユーザー

2021/10/28 07:34

> 「listに要素が追加できてるか見たかったのでmapを使って例を試してました」なら、最終的には取り除かんならんでしょ? だったらget()の実装にmap使ったらダメでしょ? デバックで確認すればいいので使う必要はないですね。。。最終的に必要ないものはそもそも書かない方がいいということですか？

episteme

2021/10/28 08:10

> 最終的に必要ないものはそもそも書かない方がいいということですか？「あくまで動作確認が目的であるなら、それを取り除いても正しく動作せにゃ意味がない」と言うてます。

退会済みユーザー

2021/10/28 08:21

>「あくまで動作確認が目的であるなら、それを取り除いても正しく動作せにゃ意味がない」と言うてます。ありがとうございます。おっしゃって頂いたことが納得できそうです。自分の書いたコードを人に見てもらうのが初めてなので他にもおかしいところがございましたら教えていただけると嬉しいです。

episteme

2021/10/28 08:29

> 他にもおかしいところがございましたら教えていただけると嬉しいです。すっごく"おかしい"です。 listであるなら - 任意の点に要素を挿入 - 任意の点から要素を削除 - 要素の数などなどが必要だと思われるが、そんなのがない。結局作ってるのは(listを使った)mapにしか見えない。

退会済みユーザー

2021/10/28 08:41

>... などなどが必要だと思われるが、そんなのがない。今後挙げていただいた機能を追加しようと思うのですが、すべて実装してから質問したほうがよかったのでしょうか？ > 結局作ってるのは(listを使った)mapにしか見えない。 mapは std::mapのようなデータ構造ですか? 「~mapにしか見えない。」というのはkeyで検索しようとしているからでしょうか?

episteme

2021/10/28 09:10

> 今後挙げていただいた機能を追加しようと思うのですが、すべて実装してから質問したほうがよかったのでしょうか？順番が逆。listの基本機能:挿入/削除/検索/要素数が先じゃない?

退会済みユーザー

2021/10/28 11:08

>順番が逆。listの基本機能:挿入/削除/検索/要素数が先じゃない? 自分が双方向配列とlistを混同してるかもしれません。データの繋がり方が双方向配列みたいだったらいいだろうと思っていたのですが、挙げて頂いたlistの基本機能がないとlistとみなされないということでしょうか? こういったデータ構造の厳密な定義のよく書かれた参考文献をご存知であればがあれば教えてほしいです。

行動規範の内容に同意します