C++ 0x는 boost 및 기타 많은 장소에서 사용 가능한 unordered_set을 소개합니다. 내가 이해하는 것은 unordered_set은 O(1) 조회 복잡도를 가진 해시 테이블이라는 것입니다. 반면에 set은 검색의 복잡성이 log(n) 인 나무 일뿐입니다. unordered_set 대신 set을 사용하는 이유는 무엇입니까? 즉 set에 대한 필요성이 더 이상 있습니까?왜 unordered_set 대신 set을 사용합니까?
집합의 항목을 반복하고 싶은 사람은 순서가 중요합니다.
당신의 답은 제가 누락 된 것이라고 생각합니다 :) – AraK
삽입 순서에 따라 주문했는지 또는 실제 비교에 따르면 '< >'연산자를 사용하고 있습니까? – SomethingSomething
기본적으로 std :: less를 사용하여 정렬됩니다. 이것을 무시하고 자신 만의 비교 연산자를 제공 할 수 있습니다. http://www.cplusplus.com/reference/set/set/ – moonshadow
손을 떼면 다른 형식으로 변환하려는 경우 관계가있는 것이 편리하다고 말할 수 있습니다.
하나는 액세스가 더 빠르지 만 생성 또는 액세스 할 때 사용되는 인덱스 또는 메모리를 만드는 시간은 더 길 수도 있습니다.
+1 Big Oh 표기법은 상수 요소를 숨기며 일반적인 문제 크기의 경우 가장 중요한 상수 요소입니다. –
해시 테이블에서 트리를 선호 할 때마다.
예를 들어 해시 테이블은 최악의 경우 "O (n)"입니다. O (1)은 평균적인 경우입니다. 나무는 최악의 경우 "O (로그)"입니다.
/균형 잡힌/나무 가장 최악의 경우 O (ln n)입니다 .O (n) 나무 (본질적으로 링크 된 목록)로 끝낼 수 있습니다. – strager
합리적으로 지능적인 해시 함수를 작성할 수 있다면 거의 항상 O (1) 해시 테이블 해시 함수를 쓸 수 없다면, "순서대로"순서대로 반복 할 필요가 있다면 트리를 사용해야합니다. O (n) 최악의 성능 "을 두려워하기 때문에 나무를 사용하면 안됩니다. –
stager : pedantic, 예. 그러나 우리는 일반적으로 ** balanced binary search tree **로 구현되는 C++의 집합에 대해 말합니다. 복잡성에 대해 이야기하기 위해 실제 작업을 지정해야합니다. 이러한 맥락에서 우리가 조회에 대해 말하는 것이 분명합니다. –
일을 정렬하려면, unordered_set 대신 set을 사용하십시오. unordered_set은 저장된 순서가 중요하지 않을 때 set에 사용됩니다.
std :: set은 Standard C++의 일부이며 unordered_set이 아니기 때문에. C++ 0x 은 표준이 아니며 부스트도 아닙니다. 우리 중 많은 사람들에게 이식성이 필수적이며 이는 표준을 고수한다는 것을 의미합니다.
내가 그를 올바르게 이해한다면, 그는 사람들이 왜 아직도 사용하고 있는지 묻지 않을 것이다. 그는 C++ 0x에 대해 알리고 있습니다. –
아마도. 나는 모두가 해시 테이블과 나무를 알고 있다고 생각했다 다른 문제. –
글쎄, 그건 표준 _now_ (몇 년 밖에 걸리지 않았다) –
순차 세트는 몇 가지 방법으로 자신의 O (1) 평균 액세스 시간을 지불해야 :
set는 같은 수의 원소를 저장하기 위해 다음 unordered_set을 적은 메모리를 사용합니다. 요소의 소수를 들어set의 조회는 unordered_set에서 조회 비해빠를 수 있습니다. 많은 작업이 빠르게 평균 경우에 unordered_set에 있습니다set에 대한 (예를 insert에 대한)가 보장됩니다.set은 요소를 정렬합니다.은 순서대로 액세스하려는 경우 유용합니다.<, <=, > 및 >=와 다른 set의를 비교할 수 있습니다. unordered_set은 이러한 작업을 지원하지 않아도됩니다.+1, 모두 우수한 포인트. 사람들은 해시 테이블에 O (1) * 평균 - 케이스 * 액세스 시간이 있다는 사실을 간과하는 경향이 있습니다. 이는 때때로 상당한 지연이있을 수 있음을 의미합니다. 이러한 구분은 실시간 시스템에서 중요 할 수 있습니다. –
좋은 점은 여기 있지만 (http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp) unordered_sets를 비교할 수 있다고 명시되어 있습니다. – Michiel
"적은 수의 요소"를 정의하십시오. –
스위프 알고리즘을 고려하십시오. 이러한 알고리즘은 해시 테이블과 완전히 실패하지만 균형 잡힌 나무로 아름답게 작동합니다. Sweepline 알고리즘의 구체적인 예를 들어서 Fortune의 알고리즘을 고려하십시오.http://en.wikipedia.org/wiki/Fortune%27s_algorithm
나는 그런 질문이 주어진다면 너무 복잡하다고 생각한다. (나는 그것을 봐야했다) – hectorpal
이미 언급 된 다른 것 외에 한 가지 더. unordered_set에 요소를 삽입 할 때 예상되는 상각 된 복잡성은 O (1)이며, 해시 테이블을 재구성해야하므로 (버킷 수를 변경해야 함) 은이됩니다. '좋은'해시 함수로도 가능합니다. 벡터에 요소를 삽입하는 것과 같이 기본 배열을 다시 할당해야하기 때문에 항상 O (n)을 취합니다.
집합에 삽입 할 때 항상 최대 O (log n)가 필요합니다. 이는 일부 응용 프로그램에서 바람직 할 수 있습니다.
실례, 정렬 된 부동산에 관한 몰래 한 가지 더 가치 :
당신이 컨테이너에, 예를 들어 데이터의 범위 하려면 : 당신은 시간 저장이 설정을, 그리고 당신이 2013 시간을 원하는 -01-01에서 2014-01-01.
unordered_set 불가능합니다.
은 물론,이 예제는 지도 및 unordered_map도 사이에 사용 경우에 더 설득력이있을 것이다. 누군가가 unordered_ 쓰기 너무 게으른 경우
나무에 대한 요구가 더 이상 존재한다. –
나는 첫 줄에서 분명히 진술했다고 생각한다. 이것은 어리석은 질문이다. 나는 뭔가를 놓쳤다. 그리고 나는 대답을 얻는다. – AraK
진짜 이유는 사물들이 흑백처럼 보이지 않는다는 것이다. 사이에 많은 회색과 다른 색이 있습니다. 이러한 컨테이너는 도구라는 것을 기억해야합니다. 때로는 성능이 중요하지 않으며 편의성이 훨씬 의미가 있습니다. 모든 사람들이 가장 효율적인 솔루션을 찾으면 우리는 처음에는 C++ (파이썬은 말할 것도 있음)를 사용하지 않고 계속해서 기계어로 코드를 작성하고 최적화합니다. – zehelvion