6. c++ STL algorithm

han811·2021년 2월 10일

c++

목록 보기

6/14

1. count

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int main()
{
    string s = "hihi";
    cout << count(s.begin(), s.end(), 'i') << '\n';
    return 0;
}

위와 같이 c++의 algorithm 헤더에서 count라는 함수를 사용하면 해당 container에 있는 특정 원소의 개수를 알 수 있습니다.
사용법은 코드를 보면 쉽게 알 수 있다고 생각합니다.

2. find

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int main()
{
    string s = "hihi";
    auto it = find(s.begin(), s.end(), 'i');
    cout << s[i] << '\n';
    return 0;
}

위와 같이 c++의 algorithm 헤더에서 find라는 함수를 사용하면 해당 container에 있는 특정 원소의 처음 위치에 해당하는 iterator를 반환합니다.

3. reverse

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
    string str = "abc";
    reverse(str.begin(),str.end());
    cout << str << endl;
    return 0;
}

위와 같이 c++의 algorithm 헤더에서 reverse라는 함수를 사용하면 해당 container에 있는 원소들을 지정해준 구간에서 역순으로 바꾸어 줍니다.

4. max, min

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
    int m, n;
    m = 3;
    n = 2;
    int max_ = max(m,n);
    int min_ = min(m,n);
    cout << max_ << ' ' << min_ << '\n';
}

위와 같이 두 값의 대소 관계를 판단하여 해당하는 값을 반환해 줍니다.
기본적으로는 overwriting되어 있는 < 혹은 >를 사용하는 것 같습니다.

5. max_element, min_element

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){

int size, val;
cin >> size;
vector<int> v;
for(int i=0; i<size; i++){
cin >> val;
v.push_back(val);
}
cout << "max값: " << *max_element(v.begin(), v.end()) << endl;
cout << "min값: " << *min_element(v.begin(), v.end()) << endl;

return 0;
}

위와 같이 해당 container내에서 가장 큰 혹은 가장 작은 원소의 위치에 해당하는 iterator를 반환하여 줍니다.
c++에서 배열도 array라는 클래스 형 객체로 취급이 되어서 iterator 연산이 가능하다고 합니다.

6. sort

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> data = {9, 3, 5, 7, 8, 1, 2, 4, 6, 10};
    sort(data.begin(), data.end());
    for(int i=0; i<10; i++){
    cout << data[i] << " ";
    }
}

위와 같이 해당 container내의 원소들을 정렬하여 오름차순으로 만들어 줍니다.

7. swap, swap_ranges

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int a = 3, b = 5;
    cout << "a: " << a << ", b: " << b << endl;
    swap(a, b);
    cout << "a: " << a << ", b: " << b << endl;
    
    return 0;
}

위와 같이 swap의 경우 해당 변수에 있는 값들을 서로 바꾸어 주는 역할을 합니다.
vector에서 원소를 참조하여 각 원소에 해당하는 값들을 바꾸는 기능으로 주로 사용하면 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){

    int a[5] = {1, 2, 3, 4, 5};
    int b[5] = {6, 7, 8, 9, 10};

    swap_ranges(a, a+3, b);

    cout << "a:";
    for(int i=0; i<5; i++)
        cout << ' ' << a[i];
    
    cout << endl << "b:";
    for(int i=0; i<5; i++)
        cout << ' ' << b[i];
    cout << endl;

return 0;
}

위와 같이 swap_ranges는 특정 범위의 값들을 다른 연속된 메모리 공간의 값들과 바꾸어 주는 역할을 합니다.
vector와 같이 사용하면 유용합니다.

8. copy

#include <iostream>
#include <algorithm>
using namespace std;

int main(){

    int a[5] = {1, 2, 3, 4, 5};
    int b[5] = {6, 7, 8, 9, 10};
    copy(a+1, a+4, b+1);

    cout << "a:";
    for(int i=0; i<5; i++)
        cout << ' ' << a[i];

    cout << endl << "b:";
    for(int i=0; i<5; i++)
        cout << ' ' << b[i];

    cout << endl;

    return 0;
}

위와 같이 copy는 특정 범위의 값들을 다른 연속된 메모리 공간의 값들에 복사하여 대입해주는 역할을 합니다.
vector의 원소 복사에 유용합니다.

9. unique

include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector <int> v;
    v.push_back(1); v.push_back(1);
    v.push_back(2);
    v.push_back(3); v.push_back(3);
    v.push_back(4);
    v.push_back(5); v.push_back(5); v.push_back(5);
    v.push_back(6);

    cout << "***** 기존 벡터배열 원소 *****" << endl;
    for (const auto& n : v) cout << n << ' ';
    cout << endl;

    cout << "***** unique 함수 적용 *****" << endl;
    unique(v.begin(), v.end());
    for (const auto& n : v) cout << n << ' ';
    cout << endl;
	
    return 0;
}

위와 같이 중복되는 원소들을 뒤로 보내며 함수를 정렬해줍니다.
이를 이용하면 다음과 같이 vector의 erase를 사용하여 vector container내의 중복되는 원소들을 제거하는게 가능합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector <int> v;
    v.push_back(1); v.push_back(1);
    v.push_back(2);
    v.push_back(3); v.push_back(3);
    v.push_back(4);
    v.push_back(5); v.push_back(5); v.push_back(5);
    v.push_back(6);

    cout << "***** 기존 벡터배열 원소 *****" << endl;
    for (const auto& n : v) cout << n << ' ';
    cout << endl;

    cout << "***** erase와 unique 같이 사용하기 *****" << endl;
    v.erase(unique(v.begin(), v.end()), v.end());
    for (const auto& n : v) cout << n << ' ';
    cout << endl;
    return 0;
}

unique는 중복되어 뒤로 밀려난 원소들의 시작 원소를 가리키는 iterator를 반환합니다.
unique의 시간복잡도는 $O(N)$ 입니다.

10. next_permutation, prev_permutation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    vector<int> v(4);

    for(int i=0; i<4; i++){
        v[i] = i+1;
    }

    do{
        for(int i=0; i<4; i++){
            cout << v[i] << " ";
        }
        cout << '\n';
    }while(next_permutation(v.begin(),v.end()));
    
    
    do{
        for(int i=0; i<4; i++){
            cout << v[i] << " ";
        }
        cout << '\n';
    }while(prev_permutation(v.begin(),v.end()));

    return 0;
}

위와 같이 next_permutation를 사용하여 container 원소들을 다음 사전순의 순열을 얻을 수 있습니다.
prev_permutation은 이와 반대로 역사전순으로 다음의 순열을 얻을 수 있습니다.
vector와 함께 유용하게 사용됩니다.
이때 next_permutation은 사전순으로 다음 번에 해당하는 순열이 존재하면 true, 만약에 없으면 해당 container를 다시 오름차순으로 바꾼 후 false를 반환합니다.
prev_permutation도 마찮가지로 다음 순열이 존재하면 true 없으면 내림차순으로 정렬 후 false를 반환합니다.

11.minmax_element

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int Numbers[10] = { 50, 25, 20, 7, 15, 7, 10, 2, 1, 3 };
    pair<int*, int*> MinMaxValue = minmax_element( &Numbers[0], &Numbers[10] );

    cout << "최소 값 : " << *MinMaxValue.first << endl;
    cout << "최대 값 : " << *MinMaxValue.second << endl;

    return 0;
}

위와 같이 해당 container내에서 가장 큰 원소와 가장 작은 원소의 위치에 해당하는 iterator를 pair 형태로 반환하여 줍니다.

12. iter_swap

#include <algorithm>
#include <iostream>
#include <vector>

void print_vec(const std::vector<int>& v) {
  std::cout << "[";
  for (auto i : v) {
    std::cout << i << " ";
  }
  std::cout << "]" << std::endl;
}

int main() {
  std::vector<int> v = {1, 2, 3, 4, 5};
  print_vec(v);

  // 2 와 3 을 바꾼다.
  std::iter_swap(v.begin() + 1, v.begin() + 2);

  print_vec(v);
}

swap은 변수의 값을 바꾸는 것이라면 container의 개념에서 iterator의 값을 바꾸는 것은 iter_swap을 이용하면 됩니다.
vector에서 요긴하게 사용됩니다.

13. lower_bound, upper_bound

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	int arr[6] = { 1,2,3,4,5,6 };
	cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;

    // 결과 -> lower_bound(6) : 5
    
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6,6,6 };
	cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

    // 결과 -> lower_bound(6) : 5
    
	return 0;
}

위와 같이 lower_bound는 찾으려는 key 값보다 같거나 큰 숫자가 배열의 몇 번째에 처음 등장하는지 찾아줍니다.
사용하기전에 오름차순 정렬을 해주는 것이 좋습니다.
iterator를 반환합니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {

	vector<int> arr = { 1,2,3,4,5,6 };
	cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();

    // 결과 -> upper_bound(3) : 3
	return 0;
}

위와 같이 upper_bound는 찾으려는 key 값을 초과하는 숫자가 몇 번째에 처음 등장하는지 찾아줍니다.
마찮가지로 사용하기전에 오름차순으로 정렬해주는 것이 좋고 iterator를 반환합니다.

14. equal_range

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector<int> v = {5,10,15,20, 5,25,30};
    pair<vector<int>::iterator, vector<int>::iterator> p;
    p = equal_range(v.begin(), v.end(), 5);
    cout << *p.first << '\n';
    cout << *p.second << '\n';
    return 0;
}

위와 같이 first에는 lower_bound를 second에는 upper_bound가 들어있는 pair를 반환합니다.
가장 처음에 나타나는 값을 기준으로 반환해 줍니다.
마찮가지로 사용하기전에 오름차순으로 정렬해주는 것이 좋고 iterator의 pair를 반환합니다.

Reference

han811

이전 포스트

5. c++ STL deque

다음 포스트

6. c++ STL algorithm

c++

1. count

2. find

3. reverse

4. max, min

5. max_element, min_element

6. sort

7. swap, swap_ranges

8. copy

9. unique

10. next_permutation, prev_permutation

11.minmax_element

12. iter_swap

13. lower_bound, upper_bound

14. equal_range

Reference

5. c++ STL deque

7. c++ STL string

0개의 댓글