1. find, count 함수
C++에는 set이라는 컨테이너가 있는데, set에는 여러 멤버 함수 중에서 용도가 비슷한 find와 count라는 함수가 있다. 존재 여부 자체를 파악하는 의미에서 두 함수는 굉장히 비슷하지만, 두 함수는 각 리턴 값이 다른 것을 볼 수 있다.
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처럼 임의의 위치에 바로 접근이 가능한 Iterator는 RandomAccessIterator라고 하는데, RandomAccessIterator는 BidirectionalIterator를 상속받아서 구현되어 있다.
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