숫자를 나타내는 다소 큰 개체 집합이 있고 사용자 지정 순서에 따라 이러한 숫자를 선택하고 싶습니다. 이 순서는 표현의 유형 (일부 숫자는 간격으로 표시됨), 그것의 통합 성 및 궁극적으로 그 값과 같은 몇 가지 기준을 포함합니다. 이 숫자는 프로그램 (공유 포인터)에서 공유되며 이에 대해 할 수있는 일이 없습니다.로컬로 정렬 된 집합 또는 우선 순위 큐 구현?
그러나 요소 속성은 언제든지 주문 내용이 변경되어 컨테이너에이를 알릴 수 없으므로 변경 될 수 있습니다. 예를 들어, 일부 작업에서는 간격으로 표시되는 숫자를 세분화해야하며이 세분화 중에 정확한 값을 찾을 수 있습니다. 이로써, 수는 간격 표현에서 합리적인 수로, 가능하면 정수로 바뀝니다. 이 변경 사항은 공유 인스턴스로 인해 즉시 컨테이너의 번호로 전파되고 순서가 파손됩니다 (어떤 번호가 변경되었는지도 알지 못합니다). 이것은 완전히 std::set을 나눈다.
그래서 내가 갖고 싶은 것은 정렬하려고하는 컨테이너이지만 이것에 의존하지 않습니다. 작업에서 잘못된 순서가 발견 될 때마다이 순서를 로컬에서 수정해야합니다. 예를 들어 insert은 (이진 검색을 사용하여) 요소를 삽입하고 현재 요소 (w.r.t. 이웃)의 순서가 올바른지 항상 확인합니다.
나는 "나에게 가장 작은 요소를 제공"하고 "나에게 작은 요소를 제공"하고 find 또는 remove 선형 복잡성이 것이 유일한 것이라고 받아 들일 것 : 난 단지로 front, insert 및 remove_front 필요 특히 효율적입니다.
이와 같은 작업을 수행하는 구현이 있습니까? 어떻게 구현하나요? <algorithm>에서
std::make_heap
std::pop_heap
std::push_heap
: 당신이 표준 라이브러리 알고리즘을 찾고 있다면
집합 내에서 요소가 얼마나 자주 변경되는지 모르겠습니다. 내 질문 : 어떤 작업이 가장 자주 발생합니까? – cageman