21. Algorithms and Maps

21.1. Standard library algorithms

표준 라이브러리에는 여러 알고리즘이 있다.

21.2. The simplest algorithm: find()

가장 간단하면서 유용한 알고리즘은 find()로, 컨테이너의 시작 반복자와 끝 반복자 구간에서 원소를 찾는 것이다.

template<std::input_iterator In, std::equality_comparable T>
In find(In first, In last, const T& val) {
 // find the first element in [first,last) that equals val
    for (In p = first; p!=last; ++p)
 {
        if (*p == val) return p;
    }
    return last;
}

21.2.1. Some generic uses

find()는 제네릭하다. std::input_iterator 조건을 만족하는 반복자와 std::equality_comparable 조건을 만족하는 데이터 타입에 대해서는 항상 쓸 수 있다.

21.3. The general search: find_if()

특정 조건을 만족하는 원소를 찾는 알고리즘은 find_if()이다.

template<std::input_iterator In, std::predicate Pred>
In find_if(In first, In last, Pred pred)
 {
    while (first!=last && !pred(*first)) ++first;
    return first;
}

21.4. Function objects

std::predicate 조건을 만족하는 함수 오브젝트를 만들어서 넘길 수는 없을까? 다음과 같이 할 수 있다. 이는 operator()로 호출된다.

class Larger_than {
          int v;
public:
          Larger_than(int vv) : v(vv) { }                             // store the argument
          bool operator()(int x) const { return x>v; }    // compare
};

일반적인 함수 오브젝트는 이런 식으로 구현된다.

class F {                   // abstract example of a function object
          S s;                // state
public:
          F(const S& ss) :s(ss) { /* establish initial state */ }
          T operator() (const S& ss) const
          {
                    // do something with ss to s
                    // return a value of type T (T is often void, bool, or S)
          }

          const S& state() const { return s; }          // reveal state
          void reset(const S& ss) { s = ss; }            // reset state
};

이는 함수 자체를 넘겨주는 것보다 훨씬 효율적인 코드를 생성한다.

21.4.2. Predicates on class members

이런 식으로 클래스에 대해 클래스 멤버에 대한 비교 함수를 만들 수 있다.

struct Record {
          string name;                // standard string for ease of use
          char addr[24];            // old style to match database layout
          // . . .
};

// different comparisons for Record objects:

struct Cmp_by_name {
          bool operator()(const Record& a, const Record& b) const
                    { return a.name < b.name; }
};

struct Cmp_by_addr {
          bool operator()(const Record& a, const Record& b) const
                    { return strncmp(a.addr, b.addr, 24) < 0; }          // !!!
};

// . . .
sort(vr.begin(), vr.end(), Cmp_by_name());           // sort by name
// . . .
sort(vr.begin(), vr.end(), Cmp_by_addr());            // sort by addr
// . . .

21.4.3. Lambda expressions

아니면 람다식을 이용해 이렇게 쓸 수도 있다.

// . . .
sort(vr.begin(), vr.end(),                 // sort by name
          [](const Record& a, const Record& b)
                   { return a.name < b.name; }
);
// . . .
sort(vr.begin(), vr.end(),                 // sort by addr
          [](const Record& a, const Record& b)
                    { return strncmp(a.addr, b.addr, 24) < 0; }
);
// . . .

21.5. Numerical algorithms

여러 산술 알고리즘도 존재한다.

21.5.1. Accumulate

누적 알고리즘으로 accumulate()가 있다. 이런 식으로 정의된다.

template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;

template<std::input_iterator In, Arithmetic T>
T accumulate(In first, In last, T init)
{
          while (first!=last) {
                    init = init + *first;
                    ++first;
          }
          return init;
}

void g(int* p, int n)
{
          int s1 = std::accumulate(p, p+n, 0);                    // sum into an int
          long sl = std::accumulate(p, p+n, long{0});      // sum the ints into a long
          double s2 = std::accumulate(p, p+n, 0.0);        // sum the ints into a double
}

마지막 인자는 초기화된 초기값이어야 한다. 아래와 같이 쓰면 안 된다.

void f(std::vector<double>& vd, int* p, int n)
{
          double s1 = 0;
          s1 = std::accumulate(vd.begin(), vd.end(), s1);
          int s2 = std::accumulate(vd.begin(), vd.end(), s2);          // oops
          float s3 = 0;
          std::accumulate(vd.begin(), vd.end(), s3);                        // oops
}

21.5.2. Generalizing accumulate()

누적 함수를 덧셈이 아니라 다른 함수로도 일반화할 수 있다.

template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;

template<std::input_iterator In, Arithmetic T, std::invocable<In::value_type, T> BinOp>
T accumulate(In first, In last, T init, BinOp op)
{
          while (first!=last) {
                    init = op(init, *first);
                    ++first;
          }
          return init;
}

std::vector<double> a = { 1.1, 2.2, 3.3, 4.4 };
std::cout << std::accumulate(a.begin(),a.end(), 1.0, std::multiplies<double>());

21.5.3. Inner product

내적 함수도 있다.

template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;

template<std::input_iterator In, std::input_iterator In2, Arithmetic T>
T inner_product(In first, In last, In2 first2, T init)
          // note: this is the way we multiply two vectors (yielding a scalar)
{
          while(first!=last) {
                    init = init + (*first) * (*first2);         // multiply pairs of elements
                    ++first;
                    ++first2;
          }
          return init;
}

// calculate the Dow Jones Industrial index:
std::vector<double> dow_price = {           // share price for each company
          81.86, 34.69, 54.45,
          // . . .
};

std::list<double> dow_weight = {              // weight in index for each company
          5.8549, 2.4808, 3.8940,
          // . . .
};

double dji_index = std::inner_product(     // multiply (weight,value) pairs and add
                    dow_price.begin(), dow_price.end(),
                    dow_weight.begin(),
                    0.0);

std::cout << "DJI value " << dji_index << '\n';

주의할 점은 구간 반복자를 3개만 받는다는 점이다. 2번째의 구간의 길이는 1번째의 구간의 길이 이상이어야 하며 아니면 런타임 에러가 난다.

21.5.4. Generalizing inner_product()

내적 함수도 일반화할 수 있다.

template <typename T>
concept Arithmetic = std::is_arithmetic_v<T>;

template<std::input_iterator In, std::input_iterator In2, Arithmetic T, std::invocable<In::value_type, T> BinOp, std::invocable<In2::value_type, T> BinOp2>
T inner_product(In first, In last, In2 first2, T init, BinOp op, BinOp2 op2)
{
          while(first!=last) {
                    init = op(init, op2(*first, *first2));
                    ++first;
                    ++first2;
          }
          return init;
}

21.6. Associative containers

std::map, std::unordered_map 등을 연관 컨테이너라 한다. 레드-블랙 트리나 해시 테이블 등으로 구현된다.

21.6.1. map

std::map은 다음과 같이 쓴다.

int main()
{
          std::map<std::string,int> words;         // keep (word,frequency) pairs

          for (std::string s; cin>>s; )
                    ++words[s];                   // note: words is subscripted by a string

          for (const auto& [word, freq] : words)
                    std::cout << word << ": " << freq << '\n';
}

21.6.2. map overview

std::map은 보통 균형 이진 트리로 구현된다.

21.6.3. Another map example

std::map은 operator[]의 키를 명시적으로 쓸 때 유용하다. 또한, 로그 시간 내에 정렬 유지/탐색/삽입/삭제를 보장한다는 특성을 가진다.

21.6.4. unordered_map

std::unordered_map은 로그 시간이 아닌 상수 시간에 삽입/삭제/탐색을 하나, 정렬이 유지되지는 않는다. 보통 해시 테이블로 구현된다.

21.6.5. set

std::set은 키, 값의 쌍 대신 키만 저장하는 std::map이다. operator[]는 당연히 없다.

21.7. Copying

복사 알고리즘도 있다.

21.7.1. Copy

std::copy는 다음과 같이 정의된다.

template<std::input_iterator In, std::output_iterator Out>
Out copy(In first, In last, Out res)
{
          while (first!=last) {
                    *res = *first;        // copy element
                    ++res;
                    ++first;
          }
          return res;
}

21.7.2. Stream iterators

입출력 스트림으로부터도 반복자를 정의할 수 있다.

int main()
{
          std::string from, to;
          std::cin >> from >> to;                 // get source and target file names

          std::ifstream is {from};                  // open input stream
          std::ofstream os {to};                    // open output stream

          std::istream_iterator<std::string> ii {is};                // make input iterator for stream
          std::istream_iterator<std::string> eos;                  // input sentinel
          std::ostream_iterator<std::string> oo {os,"\n"}; // make output iterator for stream

          std::vector<std::string> b {ii,eos};                         // b is a vector initialized from input
          std::sort(b.begin() ,b.end());                           // sort the buffer
          std::copy(b.begin() ,b.end() ,oo);                 // copy buffer to output

}

다음과 같은 코드는 쓰지 말자. 버퍼 오버플로우가 날 수 있다.

std::vector<std::string> b(max_size);          // don’t guess about the amount of input!
std::copy(ii,eos,b.begin());

21.7.3. Using a set to keep order

순서를 유지하기 위해 std::set을 쓰면 간단하다.

21.7.4. copy_if

조건을 만족하는 경우에만 복사하는 알고리즘은 std::copy_if이다.

template<std::input_iterator In, std::output_iterator Out, std::predicate Pred>
Out copy_if(In first, In last, Out res, Pred p)
          // copy elements that fulfill the predicate
{
          while (first!=last) {
                    if (p(*first)) *res++ = *first;
                    ++first;
          }
          return res;
}

21.8. Sorting and searching

정렬 알고리즘은 다음과 같다.

template<std::random_access_iterator Ran>
void sort(Ran first, Ran last);

template<std::random_access_iterator Ran, std::less_than_comparable<Cmp, Ran::value_type>>
void sort(Ran first, Ran last, Cmp cmp);

정렬된 경우엔 std::binary_search()로 이진 탐색을 할 수 있다. 이는 로그 시간이며, 반드시 정렬되어 있다는 조건이 필요하다.

21.9. Container algorithms

컨테이너에 대한 알고리즘은 다음과 같이 쓸 수 있다.

std::vector<int> v {1, 3, 2, 5, 4};
std::ranges::sort(v);

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중