C++ #12
알고리즘(Algorithms)
알고리즘의 개념
- 알고리즘이란 컨테이너에 적용할 수 있는 기능들을 체계적으로 정리해놓은 함수들을 말한다.
- 알고리즘에 속한 함수는 일반적이기 때문에, 특정 컨테이너에 종속된 것이 아니라 모든 컨테이너에 사용할 수 있도록 되어있다.
- 알고리즘 함수들은 특정 컨테이너의 멤버함수가 아닌 일반 전역함수로 작성되어 있다.
find 알고리즘 함수
- 컨테이너에 특정 값이 존재하는지 찾는 함수이다. 원형은 다음과 같다.
template <class InputIterator, class T>
InputIterator find(
InputIterator first,
InputIterator last,
const T & value
}- 벡터나 리스트와 같은 컨테이너에서 모두 사용할 수 있는 함수이다.
- first와 last 사이에 value값이 있는지 검사하고, 찾고자 하는 값이 있다면 해당 위치의 반복자가 리턴된다.
find_if 알고리즘 함수
- 사용자가 지정한 단항함수 객체 F로 비교한다. 원형은 다음과 같다.
template <class InputIterator, class T>
InputIterator find_if(
InputIterator first,
InputIterator last,
UniFred F
}- 구간 내에 매 요소에 대해 F 함수를 호출하여 true가 리턴되는 요소를 검색한다.
- find 함수는 ==로 완전히 같은 요소만 비교하는데 비해 find_if는 조건을 직접 점검할 수 있으므로 훨씬 더 일반화된 검색이 가능하다.
for_each 알고리즘 함수
- 지정 구간을 반복하면서 지정한 작업을 수행한다. 원형은 다음과 같다.
UniOp for_each)
InputIterator first,
InputIterator last,
UniOp op
}- 전 구간을 순회하면서 op 함수 객체를 호출한다.
- for_each는 루프를 돌리는 역할만 하므로 구체적인 동작을 하는 함수 객체가 반드시 필요하다.
copy 알고리즘 함수
- 컨테이너의 범위값을 대상이 되는 컨테이너에 복사하는 함수이다. 원형은 다음과 같다.
template <class InputIterator, class OutputIterator>
OputputIterator copy(
InputIterator first,
InputIterator last,
OutputIterator result
}- first와 last는 복사하고자 하는 컨테이너 반복자의 범위를 나타내고, 모든 요소를 result 반복자 위치 이후에 복사한다.
- 복사 목적지의 시작 위치는 result 반복자 하나로만 지정되며 result 이후에 first~last만큼의 기억장소가 확보되어야한다.
sort 함수
- 컨테이너에 저장된 데이터들을 정렬하고자 할 때 사용하는 알고리즘 함수이다. 원형은 다음과 같다.
template <class RandomAcessIterator, class Compare>
void sort(
RandomAcessIterator first,
RandomAcessIterator last,
}- 범위는 first부터 last 사이의 모든 데이터이고 오름차순으로 정렬한다.
- 내림차순 정렬은 함수의 세 번째 전달인자로
greator<int> ()를 추가한다. - 내림차순 기능을 위해
#include<functional>을 추가한다.
해시
hash_map이란
- 정렬 연관 컨테이너에서 map에 관하여 배운 적이 있다.
- STL에서는 관련하여 hash_map을 지원한다. 하지만 표준은 아니다.
- map과의 차이점은 hash라는 자료구조를 사용함으로써 검색 속도가 빠르다는 점이다.
hash_map의 사용 형태
- 헤더 파일
#include <hash_map>
using namespace stdext;- 변수, 반복자 타입
hash_map <key 자료형, value 자료형> 변수명
hash_map <key 자료형, value 자료형> ::iterator 변수명
hash_map <key 자료형, value 자료형> ::reverse_iterator 변수명
hash_map <key 자료형, value 자료형> ::size_type 변수명싱글톤(Singleton) 패턴
디자인 패턴을 통한 구조 개선
디자인 패턴이란
- 코드를 효율적으로 개선한 노하우들이 결국 하나의 패턴으로 자리잡는다.
- 나의 노하우가 이미 디자인패턴이였던 경우가 있을 수 있다.
- 코드를 디자인 패턴에 억지로 맞추지 마라.
싱글톤 패턴이란
- 싱글톤 패턴이란 특정 클래스의 인스턴스(=객체)를 1개만 생성하도록 제한하고, 이를 공유하는 방법이다.
- 생성자를 private로 하고, 자기 자신을 바든 함수를 만들어서 자기 자신의 객체를 반환하는 클래스이다.
싱글톤 패턴의 필요성
- 프로그램 내에 특정 클래스 내에서 하나의 객체만 생성하고자 할 때 사용한다.
- 환경 설정 객체와 같이 공통으로 사용해야 하는 모듈에서 사용한다.
#include<iostream>
using namespace std;
class SingletonClass
{
private:
static SingletonClass instance;
SingletonClass() {};
~SingletonClass() {};
public:
static SingletonClass& getInstance()
{
return instance;
}
void ShowMessage()
{
cout << "Singleton Pattern" << endl;
}
};
SingletonClass SingletonClass::instance;
void main()
{
SingletonClass::getInstance().ShowMessage();
}출력결과
Singleton Pattern
싱글톤 패턴 설계
일반적인 싱글톤 패턴의 설계 (정적 싱글톤)
- 정적 싱글톤의 문제점
- static 클래스 멤버변수는 프로그램 시작 시 초기화되므로 해당 클래스 여부와 상관없이 생성
- 다른 전역 객체의 생성자에서 해당 멤버를 참조하고 싶을 때 문제가 발생할 수도 있다.
예를 들어 싱글톤 클래스의 instance가 생성되기 전에 다른 전역 객체에서 instance를 참조하게 되면 문제가 발생한다. - C++은 전역 객체들의 생성 순서에 대해서는 명확하게 정의되어 있지 않기 때문이다.
SingletonClass::getInstance().ShowMessage();- 해결 방법
객체의 생성 시점을 조절.
늦은 초기화 기법을 사용, 즉 인스터스를 얻어오는 함수 내에서 인스턴스를 생성.
동적 싱글톤 패턴의 문제점
- new 연산자를 통해 동적으로 생성한 객체에 대해 소멸을 보장받지 못한다.
- 그로 인해 메모리 누수가 생긴다.
- 이 문제를 해결하기 위해 프로그램 종료 직전 소멸 루틴을 직접 호출해 주도록 한다.
#include<iostream>
using namespace std;
// 동적 싱글톤
class SingletonClass
{
private:
int total;
static SingletonClass* instance;
SingletonClass()
{
total = 0;
};
~SingletonClass() {};
public:
static SingletonClass* getInstance()
{
if (!instance)
{
instance = new SingletonClass();
}
return instance;
// 만들어진 객체가 없다면 만들고, 이미 있다면 있는 객체를 리턴
}
void ShowMessage()
{
cout << "Singleton Pattern" << endl;
}
void AddValue(int value)
{
total = total + value;
}
int getTotalValue()
{
return total;
}
};
SingletonClass* SingletonClass::instance = NULL;
class Temp
{
public:
Temp()
{
SingletonClass::getInstance()->ShowMessage();
}
};
void main()
{
SingletonClass* ins1 = SingletonClass::getInstance();
SingletonClass* ins2 = SingletonClass::getInstance();
SingletonClass* ins3 = SingletonClass::getInstance();
ins1->AddValue(10);
cout << "total : " << ins1->getTotalValue() << endl;
ins2->AddValue(10);
cout << "total : " << ins1->getTotalValue() << endl;
ins3->AddValue(10);
cout << "total : " << ins1->getTotalValue() << endl;
}출력결과
total : 10
total : 20
total : 30
알고 쓰자!