Search

set의 find, count 함수

Created
2021/02/25
tag
C++
set
find
count
iterator

1. find, count 함수

C++에는 set이라는 컨테이너가 있는데, set에는 여러 멤버 함수 중에서 용도가 비슷한 findcount라는 함수가 있다. 존재 여부 자체를 파악하는 의미에서 두 함수는 굉장히 비슷하지만, 두 함수는 각 리턴 값이 다른 것을 볼 수 있다.
find의 경우 리턴 타입이 BidirectionalIterator이다. 쉽게 생각해서 그냥 Iterator를 반환한다고 생각하면 되는데, find를 이용하여 특정 값을 찾지 못하면 set의 끝 인덱스 + 1을 의미하는 end를 리턴하게 된다. 반면 count의 경우 존재 여부의 리턴 타입을 BidirectionalIterator로 주는 것이 아니라 int로 주게 된다. (두 함수에 대한 시간 복잡도는 동일하다.)
두 함수의 리턴 타입이 다르기 때문에 서로 다른 방법으로 활용 가능하다. 예를 들어, Iterator컨테이너 내부의 원소들이 차지하는 메모리 공간을 참조할 수 있기 때문에 이에 대한 조작이 가능하다.
두 함수를 활용한 예시는 아래 코드와 같다.
// Student Class class Student { int id; mutable std::string name; Student (int id, std::string name) : id(id), name(name) {} } // Student Comapare Functor struct Comp { bool operator()(const Student& lhs, const Student& rhs) const { return lhs.id < rhs.id; } } std::set<Student, Comp> collection = { Student(1, "A"), Student(2, "B"), Student(3, "C"), Student(4, "D") }; std::set<Student, Comp>::iterator iter = collection.find(Student(3, "")); if (iter != collection.end()) { std::cout << iter->name << "has been changed to "; iter->name = "Change"; std::cout << iter->name << std::endl; } if (collection.count(Student(3, "")) != 0) { std::cout << iter->id << "is exist" << std::endl; }
C++

2. Iterator

1) Bidirectional vs RandomAccess

Iterator에는 여러 파생 클래스가 있는데 그 중 하나가 BidirectionalIterator이다. 이름에서 알 수 있듯이 양방향으로 이동이 가능하되 한 칸씩만 이동 가능한 Iterator이다. 이는 list의 특성과 비슷하기 때문에 포인터로 연결된 컨테이너에서 주로 이용한다.
반면 배열이나 vector, deque처럼 임의의 위치에 바로 접근이 가능한 IteratorRandomAccessIterator라고 하는데, RandomAccessIteratorBidirectionalIterator를 상속받아서 구현되어 있다.
Iterator의 상속 구조는 아래 그림으로 확인하자.

2) Container

Sequential Container

vector → continuous memory → RandomAccessIterator
list → double linked by pointer → BidirectionalIterator
deque → blocks on memory → RandomAccessIterator

Associative Container (Red-Black Tree)

set → BidirectionalIterator
map → BidirectionalIterator
multiset → BidirectionalIterator
multimap → BidirectionalIterator

Unordered Associative Container (Hash Functor)

unordered_set → ForwardIterator
unordered_map → ForwardIterator