여러분, 우리는 지금까지 파이썬 itertools와 more-itertools의 다양한 기능을 C++20/23 문법으로 흉내 내는 방법을 살펴보며, 파이썬스러운 추상화를 C++에서 어떻게 구현할 수 있는지 탐구해왔습니다. 이번 글에서는 unique_everseen, unique_justseen, 그리고 powerset를 C++로 옮겨보며, 더욱 풍부한 반복 패턴을 구현하는 방법을 알아보겠습니다.
먼저 파이썬에서 이들 API를 간단히 살펴볼게요.
from more_itertools import unique_everseen, unique_justseen
from itertools import chain, combinations
# unique_everseen(iterable)
# 지금까지 본 적 없는 원소만 내보냄 (한 번 본 원소는 무시)
data = [1,2,1,3,2,4]
for x in unique_everseen(data):
print(x, end=' ')
# 출력: 1 2 3 4
print()
# unique_justseen(iterable)
# 연속 중복 원소를 하나로 압축
data2 = [1,1,2,2,2,3,3,4,4,4]
for x in unique_justseen(data2):
print(x, end=' ')
# 출력: 1 2 3 4
print()
# powerset(iterable)
# 모든 부분집합(멱집합)을 반환
def powerset(iterable):
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
for subset in powerset([1,2,3]):
print(subset)
# ()
# (1,)
# (2,)
# (3,)
# (1,2)
# (1,3)
# (2,3)
# (1,2,3)
이제 이를 C++에서 구현해봅시다.
1. unique_everseen 구현 (기본 형태)
unique_everseen(iterable)는 새로운 원소를 발견할 때만 출력하고, 이미 본 원소는 스킵합니다. 이를 위해 지금까지 본 원소를 저장하는 집합이 필요합니다.
#include <unordered_set>
template<typename Container>
class unique_everseen_view {
public:
unique_everseen_view(Container& c) : c_(c) {}
class iterator {
public:
using base_it = decltype(std::begin(std::declval<Container&>()));
iterator(base_it current, base_it end)
: current_(current), end_(end) {
advance_to_valid();
}
iterator& operator++() {
if (current_ != end_) ++current_;
advance_to_valid();
return *this;
}
bool operator!=(const iterator& other) const {
return current_ != other.current_;
}
auto operator*() const {
return *current_;
}
private:
void advance_to_valid() {
while (current_ != end_) {
if (seen_.find(*current_) == seen_.end()) {
seen_.insert(*current_);
break;
} else {
++current_;
}
}
}
base_it current_, end_;
std::unordered_set<typename Container::value_type> seen_;
};
auto begin() {
return iterator(std::begin(c_), std::end(c_));
}
auto end() {
return iterator(std::end(c_), std::end(c_));
}
private:
Container& c_;
};
template<typename Container>
auto unique_everseen_func(Container& c) {
return unique_everseen_view<Container>(c);
}
사용 예제:
std::vector<int> data = {1,2,1,3,2,4};
for (auto x : unique_everseen_func(data)) {
std::cout << x << " "; // 1 2 3 4
}
std::cout << "\n";
2. unique_justseen 구현 (기본 형태)
unique_justseen(iterable)는 연속된 동일 원소를 하나로 압축합니다. 바로 이전 원소와 다를 때만 출력하면 됩니다.
template<typename Container>
class unique_justseen_view {
public:
unique_justseen_view(Container& c) : c_(c) {}
class filter_iterator {
public:
using base_it = decltype(std::begin(std::declval<Container&>()));
filter_iterator(base_it current, base_it end)
: current_(current), end_(end), first_(true) {
advance_to_valid();
}
filter_iterator& operator++() {
if (current_ != end_) {
prev_ = *current_;
++current_;
advance_to_valid();
}
return *this;
}
bool operator!=(const filter_iterator& other) const {
return current_ != other.current_;
}
auto operator*() const {
return *current_;
}
private:
void advance_to_valid() {
while (current_ != end_) {
auto val = *current_;
if (first_ || val != prev_) {
// 새로운 값 발견
break;
} else {
++current_;
}
}
first_ = false;
}
base_it current_, end_;
typename Container::value_type prev_;
bool first_;
};
auto begin() {
return filter_iterator(std::begin(c_), std::end(c_));
}
auto end() {
return filter_iterator(std::end(c_), std::end(c_));
}
private:
Container& c_;
};
template<typename Container>
auto unique_justseen_func(Container& c) {
return unique_justseen_view<Container>(c);
}
사용 예제:
std::vector<int> data2 = {1,1,2,2,2,3,3,4,4,4};
for (auto x : unique_justseen_func(data2)) {
std::cout << x << " "; // 1 2 3 4
}
std::cout << "\n";
3. powerset 구현 (기본 형태)
powerset(iterable)은 모든 부분집합을 반환하는 함수로, 비트마스크를 이용해 구현할 수 있습니다.
#include <cmath>
template<typename Container>
class powerset_view {
public:
powerset_view(Container& c) : c_(c) {
sz_ = std::distance(std::begin(c_), std::end(c_));
}
class iterator {
public:
using base_it = decltype(std::begin(std::declval<Container&>()));
iterator(base_it start, std::size_t sz, std::size_t idx)
: start_(start), sz_(sz), idx_(idx) {}
iterator& operator++() {
++idx_;
return *this;
}
bool operator!=(const iterator& other) const {
return idx_ != other.idx_;
}
auto operator*() const {
std::vector<typename Container::value_type> subset;
auto it = start_;
for (std::size_t i = 0; i < sz_; ++i) {
if (idx_ & (1ULL << i)) {
subset.push_back(*it);
}
++it;
}
return subset;
}
private:
base_it start_;
std::size_t sz_;
std::size_t idx_;
};
auto begin() {
return iterator(std::begin(c_), sz_, 0);
}
auto end() {
return iterator(std::begin(c_), sz_, (1ULL << sz_));
}
private:
Container& c_;
std::size_t sz_;
};
template<typename Container>
auto powerset_func(Container& c) {
return powerset_view<Container>(c);
}
사용 예제:
std::vector<int> arr = {1,2,3};
for (auto subset : powerset_func(arr)) {
std::cout << "(";
for (auto x : subset) std::cout << x << ",";
std::cout << ")\n";
}
정교한(또는 확장된) 구현: C++20 Ranges와 Concepts 활용
- unique_everseen: Concepts를 활용해 hash 가능하거나 equality 비교 가능한 타입을 제약.
- unique_justseen: 연속 중복 제거는 Ranges 파이프 등과 결합해 파이프라인 형식으로 쉽게 조립 가능.
- powerset: Concepts로 컨테이너 타입 제약 가능. Ranges와 결합해 data | powerset_func() 형태.
성능과 메모리 측면
- unique_everseen: 모든 본 원소를 저장하므로 메모리 사용 증가. 하지만 한 번 본 원소는 즉시 필터링.
- unique_justseen: O(1) 추가 메모리, 유효한 성능으로 연속 중복 제거.
- powerset: 2^n 부분집합 생성. 대규모 데이터에선 매우 비싸지만, lazy하게 필요할 때마다 vector 할당.
관련 링크 및 리소스
- C++ 표준 문서:
- more-itertools:
- itertools:
- itertools.combinations
- powerset 구현 예제는 itertools 문서 참조
마무리
이번 글에서는 unique_everseen, unique_justseen, 그리고 powerset를 C++20/23 스타일로 구현해보았습니다. 점점 더 다양한 파이썬 함수들을 C++로 옮기는 과정을 통해, 현대 C++이 제공하는 lazy evaluation과 고차 함수형 패턴의 가능성을 재확인했습니다. 이제 여러분도 이런 패턴을 활용해 더욱 우아하고 “파이썬스러운” C++ 코드를 작성해보시길 바랍니다.
반응형