표준 라이브러리 정렬 알고리즘 (예 : std :: sort)이 정렬을 위해 힙 메모리를 사용하는지 궁금합니다.std :: sort 알고리즘 메모리 사용
정렬 알고리즘이나 표준 라이브러리 알고리즘에서 일반적으로 사용되는 종류 (힙, 스택)와 임시 메모리의 양을 확인하는 방법은 무엇입니까?
제어 된 메모리 사용이 중요한 임베디드 환경에 표준 라이브러리 알고리즘 중 일부를 소개하는 것이 배경입니다. (특히 힙은 사용되지 않습니다).
미리 감사드립니다.
표준 라이브러리 알고리즘이 사용할 수있는 메모리는 표준에서 요구하는 것이 아니므로 일반적으로 원하는대로 구현할 수 있습니다. 여기에는 힙 메모리 할당이 포함됩니다.
특정 구현이 원하는 보장을 제공하는지 확인할 수는 있지만 구현이 알고리즘을 구현하는 방법을 제어 할 수는 없습니다.
그러나:
배경은 내가 제어 메모리 사용량이 매우 중요하다있는 임베디드 환경에 표준 라이브러리 알고리즘의 일부를 소개하는 생각이다. (특히 힙은 사용되지 않습니다).
이의 알고리즘이 표준에 의해 정의 된대로 그들이 어떻게해야 무엇을 할 수 있는지 확인해야합니다 구현. 즉, 대상 환경을 지원하는 C++ 컴파일러를 사용하는 경우 해당 대상 플랫폼에서 올바른 작업을 수행해야하지만이를 달성해야합니다.
특히 : 플랫폼에 힙이없는 경우이를 지원하는 모든 힙을 사용하면 안됩니다.
'std :: sort' *는 내가 아는 한'bad_alloc'을 던지지 않을지도 모르기 때문에 실제로 힙을 사용하지 않을 수도 있습니다? (당신의 코드가 아니라면) (그리고 예, 병적으로, 무의미한 힙 할당과 오류를 무시하는 캐치) – Yakk
std :: sort의 경우 일반적으로 편집기를 사용하여 < algorithm >의 소스 코드를 볼 수 있습니다. 정확히 무엇을하고 있는지 확인하십시오. Visual Studio의 경우 std :: sort는 빠른 정렬, 힙 정렬 (빠른 정렬의 O (n^2) 최악의 시간 복잡성을 방지하는 데 사용됨) 및 삽입 정렬을 모두 사용합니다. , 그래서 힙에서 메모리를 명백히 할당 할 필요가 없다. std :: stable_sort()는 병합 정렬의 변형이며 임시 버퍼 (원래 배열의 크기의 1/2)를 할당합니다. 빠른 정렬의 VS 구현은 스택 공간 복잡성을 O (log2 (n))로 제한합니다. – rcgldr
@Yakk 표준 라이브러리 구현은 내가 생각하기에 비 던지기 할당을 사용할 수 있으며 OS에 의해 종료되는 것은 표준적인 의미에서 예외가 아닙니다. 그러나, 나는 이것이 내 대답의 두 번째 부분에 해당한다고 생각한다.'std :: sort'는 정렬하고 throw하지 않아야한다. –
일반 응답 또는 "보장"이 있는지 나는 모른다. 그러나 문제가 중요하다면 일반적인 대답은 어쨌든 충분하지 않을 수 있습니다. 사용중인 플랫폼에서 std :: sort 및 특정 구현에 대한 대답이 필요합니다. 많은 std (특히 템플릿)가 C++ 헤더에 완전히 구현되어 있기 때문에 운이 좋을 수도 있습니다. 이 경우 실제로 구현을보고 걱정하는 모든 것을 검증하지 못하게하는 것이 아닙니다. – TheUndeadFish
최근 표준 초안을 탐색했습니다. 나는'sort'가 힙을 사용할 수 없다는 것을 전혀 보지 못했고 단지'swap '이 지원되는 것에 대한 요구 사항만을 보았습니다. swap을 통해 파고 들며, 힙이 스왑 중에 임시 변수를 저장하는 데 사용되는지 여부에 대한 세부 사항은 다시 없습니다. – user4581301
@ user4581301 표준은 "heap"과 "stack"이라는 개념조차 가지고 있지 않기 때문에 "where"메모리가 할당된다는 보장은 다소 놀랄 것입니다. –