도순씨의 코딩일지

C++ :: STL 정렬된 범위 알고리즘 본문

𝐏𝐑𝐎𝐆𝐑𝐀𝐌𝐌𝐈𝐍𝐆/𝐂++

C++ :: STL 정렬된 범위 알고리즘

도순씨 2020. 9. 27. 00:00

🌼 정렬된 범위 알고리즘

정렬된 범위 알고리즘(sorted range algorithm)은 정렬된 구간에서만 동작하는 알고리즘입니다. 따라서 순차열이 반드시 정렬이 돼어 있어야 한다는 조건이 붙습니다. 

 

먼저 이진탐색 예제를 살펴봅시다.

 

⭐️ binary_search() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v;
 
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    if(binary_search(v.begin(), v.end(), 20))
        cout << "20 원소가 존재합니다." << endl;
    else
        cout << "20 원소가 존재하지 않습니다." << endl;
 
    return 0;
}
 cs

 

⭐️ binary_search() 알고리즘 실행결과

1
20 원소가 존재합니다.
 cs

 

다음 예제는 두 원소의 차가 3보다 크다면 다음 위치의 원소로 정렬하고 검색하는 예제입니다.

 

⭐️ 조건자 버전 binary_search() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool Pred(int left, int right){
    return 3 < right - left;
}
 
int main(void){
    vector<int> v;
 
    v.push_back(40);
    v.push_back(46);
    v.push_back(12);
    v.push_back(80);
    v.push_back(10);
    v.push_back(47);
    v.push_back(30);
    v.push_back(55);
    v.push_back(90);
    v.push_back(53);
 
    cout << "[v 원본] : ";
    for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
        cout << v[i] << " ";
    cout << endl;
 
    sort(v.begin(), v.end(), Pred);
    cout << "[v: 정렬]: ";
    for(vector<int> :: size_type i = 0 ; i < v.size() ; ++i)
        cout << v[i] << " ";
    cout << endl;
 
    if(binary_search(v.begin(), v.end(), 32, Pred))
        cout << "32 원소가 존재합니다." << endl;
    else
        cout << "32 원소가 존재하지 않습니다.";
 
    if(binary_search(v.begin(), v.end(), 35, Pred))
        cout << "35 원소가 존재합니다." << endl;
    else
        cout << "35 원소가 존재하지 않습니다.";
 
    return 0;
}
 cs

 

⭐️ 조건자 버전 binary_search() 알고리즘 실행예제

1
2
3
4
[v 원본] : 40 46 12 80 10 47 30 55 90 53 
[v: 정렬]: 12 10 30 40 46 47 55 53 80 90 
32 원소가 존재합니다.
35 원소가 존재하지 않습니다.
 cs

 

다음 예제는 v2와 v3의 원소가 v1에 포함되는 판단하는 includes() 예제입니다.

 

⭐️ include() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void ){
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
 
    vector<int> v2;
    v2.push_back(10);
    v2.push_back(20);
    v2.push_back(40);
 
    vector<int> v3;
    v3.push_back(10);
    v3.push_back(20);
    v3.push_back(60);
 
    if(includes(v1.begin(), v1.end(), v2.begin(), v2.end()))
        cout << "v2는 v1의 부분 집합" << endl;
    else
        cout << "v2는 v1의 부분 집합 아님" << endl;
 
    if(includes(v1.begin(), v1.end(), v3.begin(), v3.end()))
        cout << "v3는 v1의 부분 집합" << endl;
    else
        cout << "v3은 v1의 부분 집합 아님" << endl;
 
    sort(v1.begin(), v1.end(), greater<int>());
    sort(v2.begin(), v2.end(), greater<int>());
 
    if(includes(v1.begin(), v1.end(), v2.begin(), v2.end(), greater<int>()))
        cout << "greater 정렬 순차열 : v2는 v1의 부분 집합" << endl;
 
    return 0;
}
 cs

 

⭐️ include() 알고리즘 실행결과

1
2
3
v2는 v1의 부분 집합
v3은 v1의 부분 집합 아님
greater 정렬 순차열 : v2는 v1의 부분 집합
 cs

 

다음은 순차열에서 30원소의 순차열을 찾는 lower_bound(), upper_ bound() 예제입니다.

 

⭐️ lower_bound(), upper_bound() 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(30);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    vector<int> :: iterator iter_lower, iter_upper;
 
    iter_lower = lower_bound(v.begin(), v.end(), 30);
    iter_upper = upper_bound(v.begin(), v.end(), 30);
 
    cout << "30 원소의 순차열 [iter_lower, iter_upper): ";
    for(vector<int>::iterator iter = iter_lower ; iter != iter_upper ; ++iter)
        cout << *iter << " ";
    cout << endl;
 
    return 0;
}
 cs

 

⭐️ lower_bound(), upper_bound() 예제 실행결과

1
30 원소의 순차열 [iter_lower, iter_upper): 30 30 30 
 cs

 

equal_range() 는 순차열에서 찾는 원소 반복자 쌍(구간)을 얻도록 해줍니다.

 

⭐️ equal_range() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(30);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
 
    pair<vector<int>::iterator, vector<int> :: iterator> iter_pair;
 
    iter_pair = equal_range(v.begin(), v.end(), 30);
 
    cout << "30 원소의 순차열 [iter_pair.first, iter_pair.second) : ";
    for(vector<int> :: iterator iter = iter_pair.first ; iter != iter_pair.second ; ++iter)
        cout << *iter << " ";
    cout << endl;
 
    return 0;
}
 cs

 

⭐️ equal_range() 알고리즘

1
30 원소의 순차열 [iter_pair.first, iter_pair.second) : 30 30 30 
 cs

 

다음으로 정렬된 두 순차열의 하나의 목적지 순차열로 만드는 merge() 함수를 살펴봅시다.

 

⭐️ merge() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
 
    vector<int> v2;
    v2.push_back(20);
    v2.push_back(30);
    v2.push_back(60);
 
    vector<int> v3(10);
 
    cout << "v1 : ";
    for(vector<int> :: size_type i = 0 ; i < v1.size() ; ++i)
        cout << v1[i] << " ";
    cout << endl;
 
    cout << "v2 : ";
    for(vector<int> :: size_type i = 0 ; i < v2.size() ; ++i)
        cout << v2[i] << " ";
    cout << endl;
 
    cout << "v3 : ";
    for(vector<int> :: size_type i = 0 ; i < v3.size() ; ++i)
        cout << v3[i] << " ";
    cout << endl;
 
    vector<int>::iterator iter_end;
    iter_end = merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
 
    cout << "v1 : ";
    for(vector<int> :: size_type i = 0 ; i < v1.size() ; ++i)
        cout << v1[i] << " ";
    cout << endl;
 
    cout << "v2 : ";
    for(vector<int> :: size_type i = 0 ; i < v2.size() ; ++i)
        cout << v2[i] << " ";
    cout << endl;
 
    cout << "v3 : ";
    for(vector<int> :: size_type i = 0 ; i < v3.size() ; ++i)
        cout << v3[i] << " ";
    cout << endl;
 
    return 0;
}
 cs

 

⭐️ merge() 알고리즘 실행결과

1
2
3
4
5
6
v1 : 10 20 30 40 50 
v2 : 20 30 60 
v3 : 0 0 0 0 0 0 0 0 0 0 
v1 : 10 20 30 40 50 
v2 : 20 30 60 
v3 : 10 20 20 30 30 40 50 60 0 0 
 cs

 

set_union() 은 두 순차열의 합집합을 출력합니다.

 

⭐️ set_union() 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void){
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    v1.push_back(50);
 
    vector<int> v2;
    v2.push_back(20);
    v2.push_back(30);
    v2.push_back(60);
 
    vector<int> v3(10);
    vector<int> :: iterator iter_end;
 
    iter_end = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    cout << "[v3.begin(), iter_end) : ";
    for(vector<int>::iterator iter = v3.begin(); iter != iter_end ; ++iter)
        cout << *iter << " ";
    cout << endl;
 
    cout << "v3 : ";
    for(vector<int>::size_type i = 0 ; i < v3.size() ; ++i)
        cout << v3[i] << " ";
    cout << endl;
}
 cs

 

⭐️ set_union() 알고리즘 실행결과

1
2
[v3.begin(), iter_end) : 10 20 30 40 50 60 
v3 : 10 20 30 40 50 60 0 0 0 0 
 cs

 

📚 출처

공동환(2012), 뇌를 자극하는 C++ STL, 한빛미디어.

'𝐏𝐑𝐎𝐆𝐑𝐀𝐌𝐌𝐈𝐍𝐆 > 𝐂++' 카테고리의 다른 글

C++ :: STL 함수 객체(1)  (0) 2020.11.01
C++ :: STL 수치 알고리즘  (0) 2020.09.28
C++ :: STL 변경 알고리즘 & 정렬 알고리즘  (0) 2020.09.25
C++ :: STL 원소를 수정하는 알고리즘 & 제거 알고리즘  (0) 2020.09.24
C++ :: STL 원소를 수정하지 않는 알고리즘  (0) 2020.09.23
'𝐏𝐑𝐎𝐆𝐑𝐀𝐌𝐌𝐈𝐍𝐆/𝐂++' Related Articles more
Comments