메모리 할당은

Question

내가 사용하고 기본 데이터 구조는 다음과 같습니다

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

는 사실상 데이터 구조는 연결리스트에 int를 매핑합니다. 맵 (이 경우 해시 맵으로 구현 됨)은 목록에서 값을 찾는 것이 일정한 시간에 실행되도록합니다. Linked List는 삽입 및 삭제가 일정한 시간에 실행되도록합니다. 각 처리의 반복에서 내가 좋아하는 뭔가를하고있는 중이 야 : 목록 내가지도의 요소 셀을 넣어 내장되면

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이 아니라, Cell*이 아니라는 것입니다.

당신으로지도를 정의하면

: std::map<int, Cell *>, 문제는이 조건에서 해결 될 것입니다 : 당신은 당신이지도에

정수 (키)를 할당 모든 세포를 삽입

1. 각 셀에 연결된 고유 한 (중요 !!)

지금 삭제가 단순히의 문제입니다 : 당신은 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; 

, 그것은 아주 쉽게된다 : 어느 날 내가이 같았다했던 방법 등

표준 :: unordered_map도 이상 표준 : :지도)을 선호했다. push_back은리스트로 돌아가서 마지막 반복자를 맵에 추가하는 문제이다. 반복자를 제거하는 것은 목록에서 요소를리스트 반복자로 제거하기 전에 맵에서 반복자가 가리키는 키를 제거하는 것이다. 키는지도를 검색하고 목록 반복자가되는지도에서 연관된 값을 반환하는 문제입니다. 키 제거는 키를 찾고 반복자 제거 등을하는 것입니다.

모든 방법을 개선하려는 경우 상수 시간이되면 std :: map 대신 std :: unordered_map을 사용할 수 있습니다 (단점이 있습니다).

이와 같은 접근 방식을 사용하면 메모리를 수동으로 해제해야하는 방해가되는 목록 기반 솔루션에 비해 상당히 단순 해집니다.

Answer 5

다른 사람들이 지적했듯이 코드를 보지 않고도 잘못된 것을보고 어려울 수도 있습니다.

그러나 두 가지 컨테이너 유형을 여기에 중첩 시켜서 도움을주지 못한다고 언급해야합니다. hash_map을 사용하는 경우 일정한 삽입 및 삭제 시간이 이미 있습니다 (관련 Hash : How does it work internally? 게시물 참조). O (c) 검색 시간에 대한 유일한 예외는 컨테이너의 크기를 조정하기로 결정한 경우입니다.이 경우 연결된 목록 추가에 관계없이 오버 헤드가 추가되었습니다. 두 개의 주소 지정 체계가 있으면 작업 속도가 느려집니다 (버그가있는 것은 말할 것도 없습니다).

죄송합니다. 이것은 메모리 누수를 지적하지는 않지만 많은 메모리 누수/버그는 stl/boost 컨테이너를 사용하지 않아서 발생합니다.먼저 살펴보십시오.

Answer 6

C++ 맵의 값을 복사 할 수 있어야하고 원시 포인터가있는 구조로 인해 복사 의미를 올바르게 처리해야하므로 신중해야합니다.

복사 의미를 걱정할 필요가없는 std :: list를 사용하면 훨씬 편리합니다.

변경할 수없는 경우 std :: map은 포인터를 관리해야하므로 맵에서 포인터를 관리해야하지만 적어도 std::map<int, Cell*>은 좀 더 관리하기 쉽습니다.

아마도 std::map<int, shared_ptr<Cell> >을 사용할 수 있습니다. 지금은 아마도 가장 쉬운 방법 일 것입니다.

당신은 또한 당신의 휴대 객체 자체 내에서 shared_ptr을 사용하는 경우에는 순환 참조를 조심해야합니다, 그리고 그것은 shared_ptr'd되고있어 휴대가 알 당신은 enable_shared_from_this

내 마지막 지점에서 파생 수있을 것입니다 list는 사용할 올바른 컬렉션 유형입니다. 때로는 LRU 캐시 상황에서 액세스 된 요소를 목록의 끝으로 빨리 이동하려는 경우에 사용하는 것이 좋습니다. 그러나 그것은 소수의 경우이며 여기서는 아마도 적용되지 않습니다. 원하는 대체 컬렉션을 생각해보십시오. map< int, set<char> > 아마도? 또는 map< int, vector<char> >?

목록에 약간의 문자를 저장하는 데 많은 오버 헤드가 있습니다.