C++에서 특정 세트의 요소에 특정 범위의 요소가 있는지 확인하는 방법

Question

std::set에 범위의 요소가 포함되어 있는지 확인해야합니다. 예를 들어 집합이 set<int>{1, 2, 4, 7, 8}이고 int 간격이 [3, 5] (양쪽 끝점 포함) 인 경우 집합에 요소가 있는지 알아야합니다. 이 경우 true를 반환합니다. 그러나 간격이 [5, 6]이면 false를 반환합니다. 간격은 [4, 4] 일 수 있지만 [5, 3]이 아닐 수 있습니다.

나는 set::lower_bound을 사용할 수있는 것처럼 보이지만 이것이 올바른 접근법인지는 확실하지 않습니다. 나는 또한 복잡성을 가능한 한 낮게 유지하기를 원한다. lower_bound을 사용하면 로그가 정확하다고 생각합니까?

Answer 1

lower_bound과 upper_bound을 함께 사용할 수 있습니다.

이

bool contains_elements_in_range = s.lower_bound(3) != s.upper_bound(5); 

당신은 (upper_bound 또는 lower_bound)를 사용하는 기능 전환에 의해 양쪽 끝에 범위가 포함 또는 독점 할 수 있습니다 다음과 같이 3과 5 사이의 요소에 대한 테스트 귀하의 예는, 포함, 기록 할 수있다 : 설정이 정렬 그리고 당신은 이분법 검색을 필요로 정렬 된 범위의 요소를 찾을 필요가 있기 때문에

s.upper_bound(2) != s.upper_bound(5); // Tests (2, 5] 
s.lower_bound(3) != s.lower_bound(6); // Tests [3, 6) 
s.upper_bound(2) != s.lower_bound(6); // Tests (2, 6) 

대수 시간은이에 대한 달성 할 수있는 최고입니다.

Answer 2

std::set을 사용할 것이라는 확신이 들면 lower_bound 방법을 사용하는 것이 좋습니다. 말하자면 로그 시간 복잡성이 있습니다.

그러나 수행하려는 작업에 따라 정렬 된 std::vector 및 독립형 std::lower_bound 알고리즘 (std::lower_bound(v.begin(), v.end(), 3))을 사용하면 프로그램의 전반적인 성능이 향상 될 수 있습니다. 이것은 또한 로그 함수이지만 상수는 더 낮습니다. (단점은 물론 std::vector에 요소를 삽입하고 정렬을 유지하는 것이 일반적으로 요소를 std::set에 삽입하는 것보다 훨씬 비쌉니다.)