각 유용한 함수들 [CPP]

Example에서 그냥 의미있는 것들만 남김

 

 

1. binary_search()

https://en.cppreference.com/w/cpp/algorithm/binary_search

 

int main()
{
    std::vector<int> haystack {1, 3, 4, 5, 9};
    std::vector<int> needles {1, 2, 3};
 
    for (auto needle : needles) {
        std::cout << "Searching for " << needle << '\n';
        if (std::binary_search(haystack.begin(), haystack.end(), needle)) {
            std::cout << "Found " << needle << '\n';
        } else {
            std::cout << "no dice!\n";
        }
    }
}

 

output

Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3

 

 

---

2. search()

https://en.cppreference.com/w/cpp/algorithm/search

 

 

template <typename Container>

bool in_quote(const Container& cont, const std::string& s)
{
    return std::search(cont.begin(), cont.end(), s.begin(), s.end()) != cont.end();
}

 
int main()
{
    std::string str = "why waste time learning, when ignorance is instantaneous?";
    // str.find() can be used as well
    std::cout << std::boolalpha << in_quote(str, "learning") << '\n'
                                << in_quote(str, "lemming")  << '\n';
 
    std::vector<char> vec(str.begin(), str.end());
    std::cout << std::boolalpha << in_quote(vec, "learning") << '\n'
                                << in_quote(vec, "lemming")  << '\n';
 
    // The C++17 overload demo:
    std::string in = "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
                     " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
    std::string needle = "pisci";
    auto it = std::search(in.begin(), in.end(),
                   std::boyer_moore_searcher(
                      needle.begin(), needle.end()));
    if(it != in.end())
        std::cout << "The string " << needle << " found at offset "
                  << it - in.begin() << '\n';
    else
        std::cout << "The string " << needle << " not found\n";
}

 

 

output

true
false
true
false
The string pisci found at offset 43

 

 

---

 

2가지 search를 알아봤다.

컨테이너 인에서 원소를 찾는 것은 같다.

 

그러나 명심할 것은

이진 탐색은 **정렬된 컨테이너에서 가능하다는 것 이다.

 

즉, 조건이 있다.

 

유용하게 쓸 수 있지만 잘 쓰도록 하자.

 

---

 

3. upper_bound(), lower_bound()

https://en.cppreference.com/w/cpp/algorithm/upper_bound

 

 

해당 원소보다 큰 원소가 시작하는 부분 또는 작은 원소가 시작하는 부분의 iterator를 반환

없다면 해당 범위의 마지막 iterator 반환

 

 

---

 

4. partition()

범위 (first 부터 last 전 까지) 내의 원소들에 대해 p 가 참인 원소들이 p 가 거짓인 원소들 앞에 올 수 있도록 재배치 합니다. 

정렬과 비슷하다.

bool type의 함수가 주어져야 재배치가 가능하다.

 

 

true, false, false, true, true ... 

을 아래와 같이 순서대로 바꾼다. 

 

true, true, true, true , false, false, false ....

 

이어서 partition_copy()가 쓰이곤 한다.

partition한 것을 배열로 나누는 것이다.

 

 
int main()
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,10};
    int true_arr [5] = {0};
    int false_arr [5] = {0};
 
    std::partition_copy(std::begin(arr), std::end(arr), std::begin(true_arr),std::begin(false_arr),
                        [] (int i) {return i > 5;});
 
    std::cout << "true_arr: ";
    for (int x : true_arr) {
        std::cout << x << ' ';
    }
    std::cout << '\n'; 
 
    std::cout << "false_arr: ";
    for (int x : false_arr) {
        std::cout << x << ' ';
    }
    std::cout << '\n'; 
 
    return 0;

 

output

true_arr: 6 7 8 9 10
false_arr: 1 2 3 4 5

 

 

 

---

 

 

sort, stable_sort, partial_sort에 대해서는 뭐 그냥 알아보면된다.

 

 

---

 

nth_element(), accumulate() 

n번째로 작은수를 구하는 함수와 누적합을 구하는 함수다.

 

추가적으로 더 공부하고 싶으면 아래 것들을 찾아보자

transform()

reduce() (C++ 17)