メモリ割り当て、リンクリストの地図を使用すると、私が使用しています

Question

基礎となるデータ構造は次のとおりです。実際には

map<int, Cell> struct Cell{ char c; Cell*next; }; 

データ構造は、リンクされたリストにint型をマップします。マップ（この場合はハッシュマップとして実装されています）は、リスト内の値の検索が一定の時間内に実行されるようにします。リンクリストにより、挿入と削除も一定の時間内に実行されます。リストは私がマップ内の要素電池を入れて構築されると、リンクされたリスト

を構築し、

Cell *cellPointer1 = new Cell; 

//プロセス細胞：各処理の繰り返しで私は何かなどをやっています。構造はうまく動いていて、私のプログラムの後で私はメモリを解放します。リスト内の各セルに対して。

delete cellPointer1 

しかし、私のプログラムの最後には、メモリリークがあります。 は、メモリリークをテストするために私が使用します。私はどこかの道に沿って私はマップ内の細胞を入れていたという事実は私が正しくメモリを解放することはできませんことを考えてい

#include <stdlib.h> 
#include <crtdbg.h> 
#define _CRTDBG_MAP_ALLOC 

_CrtDumpMemoryLeaks(); 

。誰もがこの問題を解決する方法についてのアイデアを持っていますか？

Answer 1

STLなどのビルトインコンテナを使用していない理由はありますか？

何とか、割り当てが行われる場所のコードやマップの定義は表示されません（これはライブラリからのものですか？）。

前に割り当てられたCellをすべて割り当て解除してください。最後のものから始めて、最初のものから後ろに行くのですか？

Answer 2

コードを挿入して削除する必要があります。

私はコードを削除/ memleakのフリーインサートとして参照してくださいねは次のようになります。 （注：私はあなたがマップに割り当てるセルを格納しないと仮定しています）

// 
// insert 
// 
std::map<int, Cell> _map; 
Cell a; // no new here! 

Cell *iter = &a; 
while(condition) 
{ 
    Cell *b = new Cell(); 
    iter->next = b; 
    iter = b; 
} 
_map[id] = a; // will 'copy' a into the container slot of the map 

// 
// cleanup: 
// 
std::map<int,Cell>::iterator i = _map.begin(); 
while(i != _map.end()) 
{ 
    Cell &a = i->second; 

    Cell *iter = a.next; // list of cells associated to 'a'. 
    while(iter != NULL) 
    { 
    Cell *to_delete = iter; 
    iter = iter->next; 
    delete to_delete; 
    } 
    _map.erase(i); // will remove the Cell from the map. No need to 'delete' 
    i++; 
} 

を編集：私が問題を完全に理解していない可能性があることを示すコメントがありました。マップに割り当てるセルをすべて挿入すると、マップにではなく、Cellが含まれていることが間違いです。

あなたのようにあなたのマップを定義する場合：あなたはマップ

整数（キー）に割り当てるすべてセルを挿入

1. ：std::map<int, Cell *>、あなたの問題が2つの条件で解決されるだろう各セルに関連付けられているユニーク（重要!!）

今すぐ削除は、単にの問題です：あなたはSTLを使用してこれを行うことが

std::map<int, Cell*>::iterator i = _map.begin(); 
while(i != _map.end()) 
{ 
    Cell *c = i->second; 
    if (c != NULL) delete c; 
} 
_map.clear(); 

Answer 3

（）セルからnextを削除：

は

std::unordered_map<int,std::list<Cell>> 

またはセルのみが含まれている場合char

std::unordered_map<int,std::string> 

コンパイラがstd::unordered_mapをサポートしていない場合は、boost::unordered_mapを試してください。

本当に侵入型のデータ構造を使用する場合は、Boost Intrusiveをご覧ください。

Answer 4

代わりにunordered_mapを使用する場合、同じアルゴリズムの複雑さを持つリスト/マップとほぼ同じハイブリッドデータ構造を構築していますが、それは10年近くも時折使用していますかさばる構造（私は効率よりも念頭に置いて利便性を利用するもの）の一種。

これはちょうどstd::unordered_mapを使用するのとは全く異なることに注意する価値があります。最初は要素を挿入する元の順序を保持します。挿入、削除、および検索は、対数時間（またはキー検索が含まれているかどうか、ハッシュテーブルまたはBSTを使用しているかどうかによって一定の時間がかかる）で行われることが保証されています。イテレータは挿入/削除時に無効になりませんあなたはこのようにそれを行う場合

// I use this as the iterator for my container with 
// the list being the main 'focal point' while I 
// treat the map as a secondary structure to accelerate 
// key searches. 
typedef typename std::list<Value>::iterator iterator; 

// Values are stored in the list. 
std::list<Value> data; 

// Keys and iterators into the list are stored in a map. 
std::map<Key, iterator> accelerator; 

、それは非常に容易になる：これは私が、私はそれがこのようなものだった行った方法など

のstd :: unordered_map以上のstd ::マップ）を、賛成しました。 push_backはリストに戻って最後のイテレータをマップに追加することです。イテレータの削除は、イテレータが指すキーをマップから削除してから、リストイテレータとしてリストから要素を削除し、キーはマップを検索し、マップ内の関連付けられた値を返します。これはリストイテレータになります。キーの削除はキーを見つけてイテレータを削除することです。

すべてのメソッドを改善したい場合私はここでやったのと同じようにstd :: mapの代わりにstd :: unordered_mapを使うことができます（それにはいくつかの注意点があります）。

このようなアプローチをとると、手作業でメモリを解放しなければならないリストベースの侵入型ソリューションに比べてかなり簡単になります。

Answer 5

他の人が指摘しているように、コードを見て間違っていることを確認するのは難しいかもしれません。

ただし、2つのコンテナタイプをここに重ねることであなた自身を助けているわけではありません。 hash_mapを使用している場合は、一定の挿入時間と削除時間が既にあります。関連するHash : How does it work internally?投稿を参照してください。 O（c）ルックアップ時間の唯一の例外は、実装がコンテナのサイズ変更を決定した場合です。この場合、リンクリストの追加に関係なくオーバーヘッドが追加されます。 2つのアドレス指定スキームを持つことは、物事を遅くするだけです（バグはもちろんですが）。

残念ですが、これはメモリリークを指摘していませんが、メモリリークやバグの多くは、stl/boostコンテナを使用しないことからくる可能性があります。それを最初に見てください。

Answer 6

C++マップの値をコピー可能にする必要があり、ローポインタを持つ構造体でコピーのセマンティクスを適切に処理する必要があるため、実行している作業には非常に注意する必要があります。

コピーセマンティクスについて心配する必要がないstd :: listを使うほうがはるかに良いでしょう。

これを変更できない場合は、少なくともstd::map<int, Cell*>がより管理しやすくなりますが、std :: mapはそれらを管理しないため、マップ内のポインタを管理する必要があります。

おそらくstd::map<int, shared_ptr<Cell> >を使用することができます。これはおそらく現在最も簡単です。

また、あなたのCellオブジェクト自体の中のshared_ptrを使用する場合は、循環参照に注意する必要があります、そしてセルとして、あなたが私の最後のポイントがあることになりますenable_shared_from_this

からそれを引き出すことができshared_ptr'dされていることを知っているだろうリストはごくまれに正しいコレクションタイプです。これは、LRUキャッシュ状況があり、アクセスされた要素をリストの最後まで高速に移動したい場合に、時には適切なものです。しかし、それは少数派であり、ここではおそらく適用されません。あなたが本当に望む別のコレクションを考えてみてください。 map< int, set<char> >おそらく？またはmap< int, vector<char> >？

リストには、いくつかの文字を格納するためのオーバーヘッドがたくさんあります。