동적으로 정렬된 STL 컨테이너
https://stackoverflow.com/questions/67426
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
저는 STL을 처음 접했기 때문에 동적으로 정렬할 수 있는 컨테이너가 있는지 궁금합니다.현재 내 생각은 다양한 정렬 알고리즘과 함께 벡터를 사용하는 것이지만 정렬된 벡터에 항목을 삽입하는 (아마도) 선형 복잡성을 고려할 때 더 적절한 선택이 있는지 확실하지 않습니다.
"동적으로" 명확하게 하기 위해 런타임에 정렬 순서를 수정할 수 있는 컨테이너를 찾고 있습니다.오름차순으로 정렬한 다음 나중에 내림차순으로 다시 정렬합니다.
해결책
단일 값을 오름차순 및 내림차순으로 정렬한다는 것을 알고 있다면 set이 친구입니다.반대 방향으로 "정렬"하려면 역방향 반복자를 사용하세요.
개체가 복잡하고 개체 내의 구성원 필드를 기반으로 다양한 방법으로 정렬하려는 경우 벡터 및 정렬을 사용하는 것이 더 나을 것입니다.삽입을 모두 한 번에 수행한 다음 정렬을 한 번 호출하십시오.이것이 가능하지 않다면 대규모 객체 컬렉션의 경우 deque가 벡터보다 더 나은 옵션일 수 있습니다.
제 생각에는 당신이 관심이 있다면 저것 최적화 수준에서는 실제 데이터를 사용하여 코드를 프로파일링하는 것이 더 좋습니다.(아마도 여기 있는 사람이 줄 수 있는 최고의 조언은 다음과 같습니다.블루문에서 한 번만 수행하는 경우 각 삽입 후에 sort를 호출하는 것은 중요하지 않을 수 있습니다.)
다른 팁
std::map을 보고 싶을 것입니다.
std::map<keyType, valueType>
맵은 keyType에 제공된 < 연산자를 기준으로 정렬됩니다.
또는
std::set<valueType>
또한 템플릿 인수의 < 연산자를 기준으로 정렬되지만 중복 요소는 허용되지 않습니다.
있다
std::multiset<valueType>
이는 std::set과 동일한 작업을 수행하지만 동일한 요소를 허용합니다.
자세한 내용은 Josuttis의 "The C++ Standard Library"를 적극 권장합니다.이는 std 라이브러리에 대한 가장 포괄적인 개요로, 매우 읽기 쉽고, 모호한 정보와 그다지 모호하지 않은 정보로 가득 차 있습니다.
또한 26개 중 17개에서 언급했듯이 Meyers의 Effective Stl도 읽어볼 가치가 있습니다.
당신이 원하는 것 같네요 다중 인덱스 컨테이너.이를 통해 컨테이너를 생성하고 컨테이너에 포함된 항목을 탐색할 수 있는 다양한 방법을 컨테이너에 알릴 수 있습니다.그런 다음 컨테이너는 여러 항목 목록을 유지하며 해당 목록은 삽입/삭제할 때마다 업데이트됩니다.
정말로 컨테이너를 다시 정렬하고 싶다면 std::sort 어떤 기능이든 std::deque, std::vector, 또는 간단한 C 스타일 배열도 가능합니다.이 함수는 선택적인 세 번째 인수를 사용하여 내용을 정렬하는 방법을 결정합니다.
그만큼 stl 그러한 컨테이너를 제공하지 않습니다.다음 중 하나를 통해 자신만의 것을 정의할 수 있습니다. set/multiset 또는 vector, 그러나 다음 중 하나를 호출하여 정렬 기능이 변경될 때마다 다시 정렬해야 합니다. sort (한 vector) 또는 새 컬렉션을 생성하여(예: set/multiset).
증가하는 정렬 순서에서 감소하는 정렬 순서로 변경하려는 경우 다음을 호출하여 컨테이너에서 역방향 반복기를 사용할 수 있습니다. rbegin() 그리고 rend() 대신에 begin() 그리고 end().둘 다 vector 그리고 set/multiset 뒤집을 수 있는 용기이므로 어느 쪽이든 작동합니다.
std::set 기본적으로 정렬된 컨테이너입니다.
반드시 세트/맵을 사용해야 합니다.hazzen이 말했듯이 O(log n) 삽입/찾기를 얻습니다.정렬된 벡터로는 이것을 얻을 수 없습니다.이진 검색을 사용하여 O(log n) 찾기를 얻을 수 있지만 항목을 삽입(또는 삭제)하면 벡터의 기존 항목이 모두 이동될 수 있으므로 삽입은 O(n)입니다.
그렇게 간단하지 않습니다.내 경험상 삽입/삭제는 찾기보다 덜 자주 사용됩니다.정렬된 벡터의 장점은 메모리 사용량이 적고 캐시 친화적이라는 것입니다.STL 맵과 호환되는 버전이 있는 경우(이전에 링크한 것과 같은) 쉽게 전환하고 모든 상황에 최적의 컨테이너를 사용할 수 있습니다.
이론적으로는 연관 컨테이너(set, multiset, map, multimap)가 최상의 솔루션이어야 합니다.
실제로는 넣는 요소의 평균 개수에 따라 달라집니다.요소가 100개 미만인 경우 다음과 같은 이유로 벡터가 가장 좋은 솔루션일 수 있습니다.- 지속적인 할당 량을 피하십시오 - 데이터 로컬로 인해 캐시 친화적 인 캐시 친화적 인 캐시 이점은 아마도 지속적인 정렬을 능가 할 것입니다.분명히 이는 얼마나 많은 삽입-삭제를 수행해야 하는지에 따라 달라집니다.프레임 단위로 삽입/삭제를 하시겠습니까?
더 일반적으로:성능이 중요한 응용 프로그램에 대해 이야기하고 있습니까?
너무 일찍 최적화하지 마세요...
대답은 언제나 그렇듯이 상황에 따라 다릅니다.
set 그리고 multiset 항목을 정렬하는 데 적합하지만 일반적으로 균형 잡힌 추가, 제거 및 가져오기 세트에 최적화되어 있습니다.남자다운 조회 작업이 있는 경우 정렬된 vector 더 적절할 수 있으며 다음을 사용하십시오. lower_bound 요소를 조회합니다.
또한 런타임 시 다른 순서로 정렬해야 한다는 두 번째 요구 사항은 실제로 다음을 의미합니다. set 그리고 multiset 조건자는 런타임에 수정될 수 없기 때문에 적절하지 않습니다.
그러므로 나는 정렬된 벡터를 추천하고 싶습니다.하지만 동일한 조건자를 전달하는 것을 기억하세요. lower_bound 결과가 정의되지 않고 잘못된 조건자를 전달하면 잘못된 가능성이 높기 때문에 이전 정렬에 전달한 것입니다.
집합 및 다중 집합은 기본 이진 트리를 사용합니다.자신의 용도에 맞게 <= 연산자를 정의할 수 있습니다.이러한 컨테이너는 자체적으로 정렬되어 있으므로 정렬 매개변수를 전환하는 경우 최선의 선택이 아닐 수 있습니다.상당히 많이 사용하려는 경우에는 벡터와 목록이 가장 좋습니다.일반적으로 목록에는 자체 정렬(일반적으로 병합 정렬)이 있으며 벡터에 대해 stl 이진 검색 알고리즘을 사용할 수 있습니다.삽입이 지배적이라면 목록이 벡터보다 성능이 뛰어납니다.
STL 맵과 세트는 모두 정렬된 컨테이너입니다.
두 번째로 Doug T의 책 추천입니다. Josuttis STL 책은 제가 본 학습서이자 참고서 중 최고입니다.
효과적인 STL 또한 STL의 내부 세부 사항과 해야 할 것과 하지 말아야 할 것을 배우기 위한 훌륭한 책입니다.
"STL 호환" 정렬 벡터에 대해서는 A를 참조하세요.Alexandrescu의 AssocVector 로키.
