2023. 12. 4. 17:23ㆍ프로그래밍 공부/OOP
17장에서는 스택과 큐 자료 구조의 자체 버전을 구성했다.
자료를 보유하기 위한 표준 구조의 대규모 모음이 존재한다.
이들은 매우 표준적이기 때문에 이러한 자료 구조의 표준 휴대용 구현체를 갖는 것이 합리적이다.
STL
STL(Standard Template Library): 자료 구조를 위한 라이브러리가 포함되어 있다.
STL에는 스택, 큐 및 기타 많은 표준 자료 구조의 구현체가 포함되어 있다.
STL의 맥락에서 논의할 때 이러한 자료 구조는
자료 모음을 보유하는 데 사용되기 때문에
보통 컨테이너 클래스라고 불린다.
이 장에서는 STL에 포함된 일부 기본 클래스의 개요를 제시한다.
STL이 매우 크기 때문에 여기에서 이를 포괄적으로 다룰 수는 없겠지만
STL의 일부 항목뿐만 아니라
일부 기본 STL 컨테이너 클래스를 사용하기 시작할 수 있도록 충분히 제시할 것이다.
STL은 Hewlett-Packard의 Alexander Stepanov와 Meng Lee에 의해 개발되었고
Stepanov, Lee 그리고 David Musser의 연구에 기반을 두고 있다.
그것은 C++ 언어로 쓰여진 라이브러리 모음이다.
STL은 핵심 C++ 언어에 속하지 않지만 C++ 표준의 일부이므로
표준에 부합하는 C++ 구현에는 STL이 포함된다.
실질적인 문제로 STL을 C++ 언어의 일부라고 생각할 수 있다.
이름에서 알 수 있듯이 STL의 클래스는 템플릿 클래스이다.
STL의 일반적인 컨테이너 클래스는
컨테이너 클래스에 저장될 자료의 형식에 대한 형식 매개 변수를 가지고 있다.
STL 컨테이너 클래스는 반복자를 광범위하게 사용한다.
반복자(iterator): 컨테이너 안의 자료를 순환시키기 쉽게 하는 객체
STL에 정의된 것처럼 반복자는 매우 일반적이며
앞으로 다룰 몇 개의 컨테이너 클래스를 순환하는 것 이상으로 사용할 수 있다.
반복자에 대한 우리의 논의는
이 장에서 논의하는 컨테이너 클래스와 함께 간단한 사용에 특화될 것이다.
이를 통해 개념이 구체적인 환경에서 생동감 있게 구현되고
STL에 대한 보다 발전된 텍스트를 쉽게 읽을 수 있는 충분한 이해를 얻을 수 있다.
STL은 또한 검색 및 정렬과 같은 많은 중요한 일반 알고리즘의 구현을 포함한다.
알고리즘은 템플릿 함수로 구현된다.
컨테이너 클래스에 대해 논의한 후, 이러한 알고리즘 구현 중 일부를 설명할 것이다.
19.1 반복자
이 글을 읽기 전에 10장에서 포인터와 배열을 읽고 7장의 7.3절에서 벡터를 다루어야 한다.
벡터는 STL의 컨테이너 템플릿 클래스 중 하나이다.
반복자는 포인터를 일반화한 것이다.
반복자는 벡터와 함께 반복자를 사용하는 방법을 보여준다.
19.2절에서 소개하는 다른 컨테이너 템플릿 클래스도 반복자를 사용하는 방법과 동일하다.
따라서 이 섹션에서 반복자에 대해 배우는 모든 것은
벡터에만 적용되는 것이 아니라 넓은 범위의 컨테이너에 적용된다.
이는 STL 철학의 기본 원리 중 하나를 반영한다.
반복자 사용에 대한 의미론, 이름 지정 및 구문은 서로 다른 컨테이너 형식에서 균일해야 한다.
반복자 기본사항
반복자는 포인터를 일반화하는 것으로,
실제로는 포인터를 사용하여 구현하기도 하지만
반복자의 추상화는 구현의 세부 사항을 남겨주고
컨테이너 클래스 간에 동일한 반복자에 대한 인터페이스를 균일하게 제공하도록 설계되었다.
각 자료 형식이 고유한 포인터 형식을 가지고 있는 것처럼
컨테이너 클래스도 고유한 반복자 형식을 가지고 있다.
그러나 특정 자료 형식의 동적 변수에 대해
모든 포인터 형식이 본질적으로 동일하게 동작하는 것처럼
각 반복자 형식도 동일하게 동작하지만
각 반복자 형식도 고유한 컨테이너 유식과 함께만 사용된다.
반복자는 포인터가 아니지만,
그것을 생각해서 마치 사용하는 것처럼 사용한다면 크게 틀리지는 않을 것이다.
반복자 변수는 포인터 변수처럼 컨테이너의 한 자료 엔트리에 위치한다.
반복자 객체에 적용되는 다음과 같은 오버로딩 연산자를 사용하여 반복자를 조작한다:
■ 접두사 및 접미사 증가 연산자(++) - 반복자를 다음 자료 항목으로 전진시킨다.
■ 접두사 및 접미사 감소 연산자(--) - 반복자를 이전 자료 항목으로 이동한다.
■ 동일한 연산자와 동일하지 않은 연산자(== 및 !=) - 두 반복자가 동일한 자료 위치를 가리키는지 여부를 검정한다.
■ 역참조 연산자(*) - p가 반복자 변수인 경우 *p는 p에 있는 자료에 접근할 수 있다.
이 접근은 읽기만 할 수도 있고 쓰기만 할 수도 있으며
특정 컨테이너 클래스에 따라 자료의 읽기와 변경을 모두 허용할 수도 있다.
모든 반복자들이 이 연산자들을 모두 가지는 것은 아니다.
그러나 벡터 템플릿 클래스는 반복자들이 이 연산자들을 모두 가지고 있는 컨테이너의 한 예이다.
컨테이너 클래스에는 반복자 프로세스를 시작하는 멤버 함수가 있다.
결국 새로운 반복자 변수가 컨테이너의 어떤 자료를 가리키며 위치하는 것이 아니다.
vector 템플릿 클래스를 포함한 많은 컨테이너 클래스에는
자료 구조의 특수 자료 요소를 가리키는 반복자 객체(반복자 값)를 반환하는
다음과 같은 멤버 함수가 있다:
■ c. begin( ): 컨테이너 c의 "첫 번째" 자료 항목을 가리키는 컨테이너 c의 반복자를 반환한다.
■ c.end( ): 반복자가 컨테이너 c의 마지막 자료 항목을 넘었을 때 테스트하는 데 사용할 수 있는 것을 반환한다.
17장에서 설명한 종류의 연결 리스트에서
포인터가 마지막 노드를 넘었는지 여부를 테스트하는 데 사용할 때
반복자 c.end( )는 NULL과 완전히 유사하다.
따라서 반복자 c.end( )는 자료 항목에 있는 것이 아니라
엔드 마커 또는 센티넬의 일종인 반복자이다.
센티넬(sentinel): 오류나 문제를 감지하는 프로그램
많은 컨테이너 클래스의 경우
다음과 같이 컨테이너 객체 c의 모든 요소를 순환하는 반복문을 작성할 수 있다:
//p는 컨테이너 객체 c에 대한 형식의 반복자 변수이다.
for (p = c.begin( ); p != c.end( ); p++)
process *p//*p는 현재 자료 항목이다.
그것이 큰 그림이다.
이제 벡터 템플릿 컨테이너 클래스의 구체적인 설정에서 자세한 내용을 살펴보겠다.
디스플레이 19.1은 벡터 템플릿 클래스와 함께 반복자를 사용하는 것을 보여준다.
STL의 각 컨테이너 형식은 기본적으로 동일한 방식으로 사용되지만
고유한 반복자 형식이 있음을 기억하자.
int형 벡터에 대해 원하는 반복자는 아래의 형식이다.
std::vector<int>::iterator
또 다른 컨테이너 클래스는 list 템플릿 클래스이다.
int형 list에 대한 반복자는 아래의 형식이다.
std::list<int>::iterator
디스플레이 19.1의 프로그램에서 int형의 벡터에 대한 반복자에 적용되도록 형식 이름 iterator를 전문화한다.
디스플레이 19.1에서 원하는 형식 이름 iterator는 템플릿 클래스 vector에 정의되어 있습니다.
따라서 템플릿 클래스 vector를 int형으로 전문화하고
vector<int>에 대한 반복자 형식을 원한다면 아래의 형식을 원한다
vector<int>::iterator;
디스플레이 19.1 벡터와 함께 사용되는 반복자
//Program to demonstrate STL iterators.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main( )
{
vector< int> container;
for ( int i = 1; i <= 4; i++)
container.push_back(i);
cout << "Here is what is in the container:\n";
vector< int>::iterator p;
for (p = container.begin( ); p != container.end( ); p++)
cout << *p << " ";
cout << endl;
cout << "Setting entries to 0:\n";
for (p = container.begin( ); p != container.end( ); p++)
*p = 0;
cout << "Container now contains:\n";
for (p = container.begin( ); p != container.end( ); p++)
cout << *p << " ";
cout << endl;
return 0;
}
샘플 대화 상자
Here is what is in the container:
1 2 3 4
Setting entries to 0:
Container now contains:
0 0 0 0
vecgtor(또는 임의의 컨테이너 클래스)와 함께 반복자의 기본적인 사용은
디스플레이 19.1의 다음 행으로 설명된다:
vector<int>::iterator p;
for (p = container.begin( ); p != container.end( ); p++)
cout << *p << " ";
container는 형식 vector<int>이고
형식 iterator는 실제로 std::vector<int>::iterator를 의미한다는 것을 기억하자.
벡터 v는 그 자료 요소들의 선형 배열로 생각할 수 있다.
첫 번째 자료 요소 v[0], 두 번째 자료 요소 v[1] 등이 있다.
반복자 p는 이들 요소 중 하나에 위치할 수 있는 객체이다
(또는 이들 요소 중 하나를 가리킨다).
반복자는 자신의 위치를 한 원소에서 다른 원소로 이동시킬 수 있다.
만약 p가 v[7]에 위치한다면 p++는 v[8]에 위치하도록 p를 이동시킨다.
이렇게 함으로써 반복자는 첫 원소에서 마지막 원소로 벡터를 이동할 수 있지만,
첫 원소를 찾아야 하고 마지막 원소를 언제 보았는지 알아야 힌다.
연산자 = =를 사용하면
반복자가 다른 반복자와 같은 위치에 있는지 알 수 있다.
따라서 만약 반복자가 첫 번째, 마지막 또는 다른 요소를 가리키고 있다면
다른 반복자를 테스트하여 그것이 첫 번째, 마지막 또는 다른 요소에 있는지 확인할 수 있다.
p1과 p2가 두 개의 반복실험인 경우, 비교
p1 == p2
는 p1과 p2가 같은 원소에 위치할 때만 참이다.
(이는 포인터와 유사하다.
p1과 p2가 포인터라면 이 비교는 같은 것을 가리킨다면 참일 것이다.)
평소처럼!=는 = =의 음수일 뿐이므로
p1 != p2
p1과 p2가 같은 원소에 위치하지 않을 때 참이다.
begin()
멤버 함수 begin( ): 컨테이너의 첫 번째 원소에 반복자를 배치하는 데 사용된다.
벡터와 다른 많은 컨테이너 클래스의 경우,
멤버 함수 begin( )은 첫 번째 원소에 위치한 반복자를 반환한다.
(벡터 v의 경우 첫 번째 원소는 v[0]이다.) 따라서,
vector<int>::iterator p = v.begin( );
반복자 변수 p를 첫 번째 원소에 위치한 반복기로 초기화한다.
따라서 벡터 v의 모든 원소를 방문하기 위한 for문의 기본은 다음과 같다
vector<int>::iterator p;
for (p = v.begin( ); Boolean_Expression; p++)
Action_At_Location p;
원하는 정지 조건은
p = v.end( )
end()
멤버 함수 end(): 반복자가 마지막 요소를 통과했는지 확인할 수 있는 보초값(sentinel)을 반환한다.
만약 p가 마지막 요소에 위치한다면,
p++ 이후에 테스트 p = v.end( )는 false에서 true로 바뀐다.
따라서 올바른 Boolean_Expression은 다음 중지 조건의 음수이다:
vector<int>::iterator p;
for (p = v.begin( ); p != v.end( ); p++)
Action_At_Location p;
p!= v.end( )는
p의 위치가 마지막 요소를 지나 앞으로 나아갈 때까지
true에서 false로 바뀌지 않다.
따라서 v.end( )는 어떤 요소에도 위치하지 않다.
v.end( ) 값은 보초병 역할을 하는 특별한 값이다.
반복자는 아니지만 ==와 !=를 사용하여
v.end( )를 반복자와 비교할 수 있다.
v.end( ) 값은
17장에서 설명한 종류의 연결 리스트의 끝을 표시하는 데 사용되는
NULL 값과 유사하다.
디스플레이 19.1의 for문에 대해 다음은 container라는 이름의 벡터와 동일한 기법을 사용하다:
vector<int>::iterator p;
for (p = container.begin( ); p != container.end( ); p++)
cout << *p << " ";
반복자 p의 위치에서 수행되는 동작은
cout << *p << ">;
STL 컨테이너 반복자에 대해
역참조 연산자 *가 오버로딩되어 *p는 위치 p에서 요소를 생성한다.
특히 벡터 컨테이너의 경우 *p는 반복자 p에 위치한 요소를 생성한다.
따라서 앞의 cout문은 반복자 p에 위치한 요소를 출력하므로
전체 for문은 벡터 컨테이너의 모든 요소를 출력한다.
역참조 연산자 *p는 항상 반복자 p에 위치한 요소를 생성한다.
어떤 상황에서는 *p가 읽기 전용 접근을 생성하므로 요소를 변경할 수 없다.
다른 상황에서는 요소에 접근할 수 있고 요소를 변경할 수 있다.
벡터의 경우 *p는 p에 위치한 요소를 변경할 수 있다.
디스플레이 19.1의 for문에 대해 다음과 같이 표시된다:
for (p = container.begin( ); p != container.end( ); p++)
*p = 0;
벡터 컨테이너의 모든 요소를 순환하고 모든 요소를 0으로 변경한다.
함정: 컴파일러 문제
일부 컴파일러는 반복자 선언에 문제가 있다.
반복자를 선언하는 방법은 다양하다.
예를 들어, 우리는 다음을 사용해왔다:
using std::vector;
. . .
vector<char>::iterator p;
또는 다음을 사용할 수 있다:
using std::vector< char>::iterator;
. . .
iterator p;
다음을 사용할 수도 있지만 그다지 좋지는 않다:
using namespace std;
. . .
vector<char>::iterator p;
다른 유사한 변형이 있다.
당신의 컴파일러는 이 대안들 중 어느 하나만 받아들여야 한다.
그러나 우리는 몇몇 컴파일러들이 이 대안들 중 일부만 받아들일 것임을 발견했다.
만약 한 가지 양식이 당신의 컴파일러와 함께 작동하지 않는다면, 다른 양식을 시도해 보자.
반복자
반복자(iterator): 컨테이너 안의 요소들에 접근하기 위해 컨테이너와 함께 사용할 수 있는 객체
반복자는 포인터의 개념을 일반화한 것이다.
연산자 = =, !=, ++, - 는 반복자에 대해 포인터에 대해 동작하는 것과 동일하게 동작한다.
반복자가 컨테이너 안의 모든 요소들을 순환하는 방법의 기본 개요는 다음과 같다:
STL_container<datatype>::iterator p;
for (p = container.begin( ); p != container.end( ); p++)
Process_Element_At_Location p;
STL_container: 컨테이너 클래스의 이름(예: vector)
datatype: 컨테이너에 저장할 항목의 자료 형식
멤버 함수 begin( ): 첫 번째 요소에 위치한 반복자를 반환한다.
멤버 함수 end( ): 컨테이너의 마지막 요소를 지나 한 위치에 있는 센티넬 값의 역할을 하는 값을 반환한다.
역참조
역참조 연산자인 *p를 반복자 p에 적용할 때 반복자 p에 위치한 요소가 생성된다.
어떤 상황에서는 *p가 읽기 전용 접근을 생성하므로 요소를 변경할 수 없다.
다른 상황에서는 요소에 접근할 수 있고 요소를 변경할 수 있다.
반복자의 종류
컨테이너마다 다른 종류의 반복자가 있다.
반복자는 작동하는 연산의 종류에 따라 분류된다.
벡터 반복자는 가장 일반적인 형태로, 즉 모든 연산이 벡터 반복자와 함께 작동한다.
따라서 우리는 반복자를 설명하기 위해 벡터 컨테이너를 사용할 것이다.
이 경우 우리는 감소와 임의 접근의 반복자 연산을 설명하기 위해 벡터를 사용한다.
디스플레이 19.2는 container라는 이름의 벡터 객체와 반복자 p를 사용하는 다른 프로그램을 보여준다.
감소 연산자는 디스플레이 19.2의 29행에 사용된다.
예상대로 p--는 반복자 p를 이전 위치로 이동시킨다.
감소 연산자 – –는 증가 연산자 ++와 유사하지만 반복자를 반대 방향으로 이동한다.
증가 및 감소 연산자는 접두사 (++p) 또는 후위사 (p++) 표기법에서 사용할 수 있다.
p를 변경하는 것 외에 값도 반환한다.
반환되는 값의 세부 사항은 int 변수에 대한 증가 및 감소 연산자의 경우와 완전히 유사하다.
접두사(prefix) 표기법: 먼저 변수를 변경한 다음 변경된 값을 반환한다.
후위사(postfix) 표기법: 변수를 변경하기 전에 값을 반환한다.
우리는 증가 및 감소 연산자를 값을 반환하는 표현으로 사용하지 않고 변수 값을 변경하는 데만 사용한다.
표시 19.2의 다음 행은 벡터 반복자를 사용하면
container와 같은 벡터의 요소에 임의 접근할 수 있다는 사실을 보여준다:
vector<char>::iterator p = container.begin( );
cout << "The third entry is " << container[2] << endl;
cout << "The third entry is " << p[2] << endl;
cout << "The third entry is " << *(p + 2) << endl;
임의 접근
임의 접근(random access): 한 단계에서 특정 요소로 직접 이동할 수 있음
우리는 이미 container[2]를 벡터에 대한 임의 접근의 형태로 사용한 적이 있다.
이것은 단순히 배열과 벡터에 표준적인 대괄호 연산자이다.
새로운 것은 이와 같은 대괄호 표기법을 반복자와 함께 사용할 수 있다는 것이다.
p[2]라는 표현은 2로 인덱스된 원소에 접근하는 방법이다.
p[2]와 *(p+2)의 표현은 완전히 동일하다.
포인터 산술(10장 참조)에 비유하면, (p+2)는 p를 넘어 두 자리의 위치를 지정하다.
이전 코드에서 p는 첫 번째(인덱스 0) 위치에 있으므로, (p+2)는 세 번째(인덱스 2) 위치에 있다.
식 (p + 2)는 반복자를 반환한다.
식 * (p + 2)는 반복자를 역참조한다.
물론 2를 다른 음이 아닌 정수로 대체하여 다른 요소에 대한 포인터를 얻을 수 있다.
디스플레이 19.2 양방향 및 임의 접근 반복자 사용
//Program to demonstrate bidirectional and random-access iterators.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main()
{
vector< char> container;
container.push_back('A');
container.push_back('B');
container.push_back('C');
container.push_back('D');
for ( int i = 0; i < 4; i++)
cout << "container[" << i << "] == "
<< container[i] << endl;
vector< char>::iterator p = container.begin();
cout << "The third entry is " << container[2] << endl;
cout << "The third entry is " << p[2] << endl;
cout << "The third entry is " << *(p + 2) << endl;
cout << "Back to container[0].\n";
p = container.begin( );
cout << "which has value " << *p << endl;
cout << "Two steps forward and one step back:\n";
p++;
cout << *p << endl;
p++;
cout << *p << endl;
p--;
cout << *p << endl;
return 0;
}container[2], p[2], *(p + 2)
같은 것에 대한 세 가지 다른 표기법.
container[2]
이 표기법은 벡터와 배열에 특화되어 있다.
p[2], *(p + 2)
이 두 가지는 모든 임의 접근 반복자에서 작동한다.
p--;
모든 양방향 반복자에 사용할 수 있다.
샘플 대화 상자
container[0] == A
container[1] == B
container[2] == C
container[3] == D
The third entry is C
The third entry is C
The third entry is C
Back to container[0].
which has value A
Two steps forward and one step back:
B
C
B
반복자 변수 p에 있는 반복자의 값은 p[2]도 (p + 2)도 변하지 않다.
식 (p + 2)는 다른 반복자를 다른 위치로 되돌려 놓지만, p는 원래 있던 곳으로 남는다.
뒤에 있는 p[2]에서도 비슷한 일이 일어난다.
또한 p[2]와 (p + 2)의 의미는 p에 있는 반복자의 위치에 따라 달라진다.
예를 들어, (p + 2)는 p의 위치를 벗어난 두 위치를 의미한다.
예를 들어,
디스플레이 19.2에서 이전에 논의된 코드가 다음과 같이 대체되었다고 가정한다(추가된 p++):
vector<char>::iterator p = container.begin( );
p++;
cout << "The third entry is " << container[2] << endl;
cout << "The third entry is " << p[2] << endl;
cout << "The third entry is " << *(p + 2) << endl;
이 세 가지 코트의 출력은 더 이상
The third entry is C
The third entry is C
The third entry is C
대신에
The third entry is C
The third entry is D
The third entry is D
p++는 위치 0에서 위치 1로 p 이동하므로
(p+2)는 위치 2가 아니라 위치 3에서 반복자가 된다.
따라서 *(p+2)와 p[2]는 container[2]가 아니라 container[3]에 해당한다.
이제 우리는 반복자가 어떻게 분류되는지 이해하기 위해
반복자에서 작동하는 방법에 대해 충분히 알고 있다.
반복자의 주요 종류는 다음과 같다.
전달(forward) 반복자 : ++는 반복자에서 작동한다.
양방향(bidirectional) 반복자 : ++ 및 – – 모두 반복자에서 작동한다.
임의 접근(random-access) 반복자: ++, – –, 및 임의 접근은 모두 반복자와 함께 작동한다.
모든 임의 접근 반복자는 양방향 반복자이고 모든 양방향 반복자는 순방향 반복자이다.
나중에 알게 되겠지만 템플릿 컨테이너 클래스마다 반복자의 종류가 다르다.
vector 템플릿 클래스의 반복자는 임의 접근 반복자이다.
전달 반복자, 양방향 반복자 및 임의 접근 반복자라는 이름은
형식 이름이 아니라 반복자의 종류를 가리킨다.
실제 형식 이름은 std::vector<int>::iterator와 같은 것이며, 이 경우 임의 접근 반복자이다.
반복자의 종류
컨테이너마다 다른 종류의 반복자가 있다. 다음은 주요한 종류의 반복자이다.
전달 반복자: ++는 반복자에서 작동한다.
양방향 반복자: ++ 및 – 모두 반복자에서 작동하다.
임의 접근 반복자: ++, –, 임의 접근은 모두 반복자와 함께 작동하다.
상수 및 가변 반복자
순방향 반복자, 양방향 반복자, 임의 접근 반복자의 카테고리는
각각 반복 연산자가 반복자를 사용하여 동작하는 방식에 따라
constant와 mutable의 두 가지 카테고리로 세분된다.
상수 반복자(constant iterator)
상수 반복자를 사용하면
반복 연산자는 요소의 읽기 전용 버전을 생성한다.
상수 반복자 p를 사용하면 *p를 사용하여 변수에 할당하거나 화면에 출력할 수 있지만,
예를 들어 *p에 할당하여 컨테이너의 요소를 변경할 수는 없다.
돌연변이 반복자(mutable iterator)
돌연변이 반복자 p를 사용하면
*p에 값이 할당될 수 있으므로 컨테이너의 해당 요소가 변경된다.
다른 방법으로, 돌연변이 반복자 p를 사용하면 *p는 l 값을 반환한다.
벡터 반복자는 디스플레이 19.1의 다음 행과 같이 돌연변이이다:
cout << "Setting entries to 0:\n";
for (p = container.begin( ); p != container.end( ); p++)
*p = 0;
컨테이너에 상수 반복자만 있으면 컨테이너에 대해 상수 반복자를 얻을 수 없다.
그러나 컨테이너에 돌연변이 반복자가 있고
컨테이너에 상수 반복자가 필요하다면 이를 가질 수 있다.
코드가 컨테이너의 요소를 변경하지 않도록 하려면
일종의 오류 검사 장치로 상수 반복자를 사용해야 한다.
예시)
다음은 container라는 벡터 컨테이너에 대해 상수 반복자를 생성한다:
std::vector<char>::const_iterator p = container.begin( );
또는
using std::vector< char>::const_iterator;
const_iterator p = container.begin( );
p가 이러한 방식으로 선언되면 다음과 같은 오류 메시지가 표시된다:
*p = 'Z';
예시)
vector<char>::iterator p;
를
vector<char>::const_iterator p;
로 대체한 경우
디스플레이 19.2가 정확히 동일하게 작동한다
그러나 디스플레이 19.1의 프로그램의 다음 행 때문에
디스플레이 19.1에서는 유사한 변경이 작동하지 않다:
*p = 0;
const_iterator는 형식 이름인 반면,
상수 반복자(constant iterator)는 형식 반복자의 이름이다.
그러나 const_iterator라는 형식의 모든 반복자는 상수 반복자가 된다.
상수 반복자
상수 반복자: 해당 위치에서 요소를 변경할 수 없는 반복자
역방향 반복자
때로는 컨테이너의 요소를 역순으로 순환하고 싶어한다.
양방향 반복자가 있는 컨테이너가 있는 경우 다음을 시도해 볼 수 있다:
vector<int>::iterator p;
for (p = container.end( ); p != container.begin( ); p--)
cout << *p << " ";
이 코드는 컴파일되며 일부 시스템에서 이러한 작업을 수행할 수 있지만 근본적으로 잘못된 점이 있다.
container.end() - 일반 반복자가 아니라 sentinel일 뿐이다.
container.begin() - sentinel이 아니다.
역방향 반복자
다행히도 원하는 것을 쉽게 할 수 있는 방법이 있다.
양방향 반복자가 있는 컨테이너에는
역방향 반복자로 알려진 일종의 반복자를 사용하여
모든 것을 되돌릴 수 있는 방법이 있다.
다음은 잘 작동할 것이다:
vector<int>::reverse_iterator rp;
for (rp = container.rbegin( ); rp != container.rend( ); rp++)
cout << *rp << " ";
멤버 함수 rbegin( ): 마지막 요소에 위치한 반복자를 반환한다.
멤버 함수 rd( ): 원소의 "끝"을 역순으로 표시하는 보초병(sentinel)을 반환한다.
reverse_iterator 형식의 반복자의 경우 증가 연산자인 ++가 원소를 통해 뒤로 이동한다.
즉, --와 ++의 의미는 서로 바뀐다.
디스플레이 19.3의 프로그램은 역 반복자를 보여준다.
reverse_iterator 형식에는 const_ reverse_iterator라는 일정한 버전도 있다.
역방향 반복자(reverse iterator)
역방향 반복자는 양방향 반복자가 있는 컨테이너의 모든 요소를 순환하는 데 사용될 수 있다.
요소들은 역순으로 방문된다.
일반적인 방식은 다음과 같다:
STL_container<datatype>::reverse_iterator rp;
for (rp = c.rbegin( ); rp != c.rend( ); rp++)
Process_At_Location p;
객체 c는 양방향 반복자가 있는 컨테이너 클래스이다.
reverse_iterator를 사용할 때는 선언문 같은 것을 사용해야 한다.
예를 들어, c가 vector<int>라면 다음과 같은 것으로 충분하다:
vector<int>::reverse_iterator rp;
디스플레이 19.3 역방향 반복자
//Program to demonstrate a reverse iterator.
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
int main( )
{
vector< char> container;
container.push_back('A');
container.push_back('B');
container.push_back('C');
cout << "Forward:\n";
vector< char>::iterator p;
for (p = container.begin( ); p != container.end( ); p++)
cout << *p << " ";
cout << endl;
cout << "Reverse:\n";
vector< char>::reverse_iterator rp;
for (rp = container.rbegin( ); rp != container.rend( ); rp++)
cout << *rp << " ";
cout << endl;
return 0;
}
샘플 대화 상자
Forward:
A B C
Reverse:
C B A
다른 종류의 반복자
이 책에서는 다루지 않을 다른 종류의 반복자가 있다.
우리는 당신이 만날 수 있는 두 종류의 반복자를 간단히 언급할 것이다.
입력 반복자: 기본적으로 입력 스트림과 함께 사용할 수 있는 순방향 반복자
출력 반복자: 기본적으로 출력 스트림과 함께 사용할 수 있는 순방향 반복자
더 자세한 내용은 더 고급 참조 자료를 참조해야 할 것이다.
19.2 컨테이너
STL의 컨테이너 클래스(container class): 자료를 보유하기 위한 서로 다른 종류의 구조체 ex) 리스트, 큐, 스택 등
각각은 저장할 특정 형식의 자료에 대한 매개변수를 가진 템플릿 클래스이다.
예를 들어, 리스트를 int, double, string,아무 클래스 또는 너가 원하는 struct 형식의 리스트로 지정할 수 있다.
각각의 컨테이너 템플릿 클래스는
자료를 추가하고 컨테이너에서 자료를 제거하기 위한
고유의 특수화된 접근자 및 설정자를 가질 수 있다.
서로 다른 컨테이너 클래스는 서로 다른 종류의 반복자를 가질 수 있다.
예를 들어 하나의 컨테이너 클래스는 양방향 반복자를 가질 수 있지만
다른 컨테이너 클래스는 순반향 반복자만 가질 수 있다.
그러나 이들이 정의될 때마다
반복자 연산자와 멤버 함수 begin( ) 및 end( )는
모든 STL 컨테이너 클래스에 대해 동일한 의미를 갖는다.
순차적인 컨테이너
순차 컨테이너는 자료 항목을 리스트로 정리하여 첫 번째 요소, 다음 요소 등을 마지막 요소까지 포함한다.
17장에서 설명한 연결 리스트는
일종의 순차 컨테이너의 예이며, 단일 연결 리스트라고 부르기도 한다.
단일 연결 리스트(singly linked list): 한 위치에서 다른 위치로 연결되는 링크가 하나밖에 없다.
STL은 이러한 단일 연결 리스트에 해당하는 컨테이너를 가지고 있지 않지만,
일부 구현예에서는 일반적으로 slist라는 이름으로 단일 연결된 리스트를 구현한다.
STL의 일부인 가장 간단한 리스트는 이중 연결 리스트(doubly linked list)이며,
이는 list라는 이름의 템플릿 클래스이다.
이러한 두 종류의 리스트의 차이점은
디스플레이 19.4에 나타나 있으며, 17.1절에 자세히 설명되어 있다.
slist와 list
디스플레이 19.4의 리스트에는 3개의 정수 값 1, 2, 3이 순서대로 포함된다.
두 리스트의 종류는 slist<int>와 list<int>이다.
또한 화면에는 begin( )과end( )을 반복하는 위치가 표시된다.
아직 어떻게 정수를 리스트에 입력할 수 있는지 알려주지 않았다.
디스플레이 19.4에서는
17장에서 설명한 형태의 노드와 포인터로
단일 연결 리스트와 이중 연결 리스트를 그렸다.
STL 클래스 list과 비표준 클래스 slist는
이러한 방식으로 구현될 수도 있고, 그렇지 않을 수도 있다.
그러나 STL 템플릿 클래스를 사용할 때는 이러한 구현 세부 정보로부터 보호된다.
따라서 단순히 자료(노드가 될 수도 있고 아닐 수도 있음)와 반복자(포인터가 아닌)의 위치만 생각하면 된다.
디스플레이 19.4의 화살표가 ++(아래쪽)와 –-(위쪽)의 방향을 나타내는 것이라고 생각하면 된다.
우리는 순차적 컨테이너에 대한 컨텍스트를 제공하기 위해 템플릿 클래스 slist를 제시했다.
이것은 17장에서 설명한 내용과 일치하며
대부분의 프로그래머들이 연결 리스트를 언급할 때 가장 먼저 떠올리는 것이다.
그러나 템플릿 클래스 slist는 표준이 아니므로 더 이상 논의하지는 않겠다.
구현에서 템플릿 클래스 slist를 제공하고 사용하고자 하는 경우
세부 사항은 list에 대해 설명하는 것과 유사하지만
감소 연산자 –-(전치 및 후치)는 slist에 대해 정의되지 않았다.
디스플레이 19.4 두 종류의 리스트
slist: 단일 연결 리스트
++ 정의됨; -- 정의되지 않음
list: 이중 연결 리스트
++ 및 -- 모두 정의됨
slist는 STL의 일부가 아니며 항상 구현되지 않을 수 있다.
list는 STL의 일부이다.
//여기부터
STL 템플릿 클래스 list를 사용하는 간단한 프로그램은 디스플레이 19.5에 제공된다.
함수 push_back: 리스트 끝에 요소를 추가한다.
list 템플릿 클래스에 대해 역참조 연산자는 읽기 및 자료 변경을 위한 접근 권한을 부여한다.
또한 list 템플릿 클래스와 STL의 모든 템플릿 클래스 및 반복자를 사용하여
모든 정의가 std 네임스페이스에 배치된다.
만약 우리가 list와 list<int>를 각각 vector와 vector<int>로 바꾼다면,
디스플레이 19.5는 정확히 똑같이 컴파일되어 실행될 것이다.
이러한 사용의 통일성은 STL 구문의 핵심적인 부분이다.
그러나 벡터와 리스트 컨테이너 사이에는 차이점이 있다.
주요 차이점 중 하나는 벡터 컨테이너에 임의 접근 반복자가 있는 반면,
리스트에는 양방향 반복자만 있다는 것이다.
예를 들어, 디스플레이 19.2부터 시작하면 다음을 사용한다
임의 접근하여 vector와 vector<char>가 발생하는 모든 것을
각각 list와 list<char>로 바꾼 후
프로그램을 컴파일하면 컴파일러 오류가 발생한다.
(container[i] 또는 container[2]가 포함된 문장을 삭제해도 오류 메시지가 나타난다.)
STL의 기본 순차 컨테이너 템플릿 클래스는 디스플레이 19.6에 나열되어 있다.
스택 및 큐와 같은 다른 컨테이너는
"컨테이너 어댑터 stack과 queue"라는 서브섹션에서
논의된 기술을 사용하여 이들로부터 얻을 수 있다
순차 컨테이너 클래스의 일부 멤버 함수의 샘플은 디스플레이 19.7에 제공된다.
이 모든 시퀀스 템플릿 클래스에는 재사용을 위해 저장을 반환하는 소멸자가 있다.
데크
데크(deque): "d-queue" 또는 "deck"로 발음되며 "double ended queue"의 약자이다
데크는 일종의 슈퍼 큐이다.
큐를 사용하면 자료 시퀀스의 한쪽 끝에서 자료를 추가하고 다른 쪽 끝에서 자료를 제거할 수 있다.
데크를 사용하면 양쪽 끝에서 자료를 추가하고 양쪽 끝에서 자료를 제거할 수 있다.
템플릿 클래스 deque는 저장된 자료 형식에 대한 매개 변수가 있는 데크의 템플릿 클래스이다.
순차 컨테이너
순차 컨테이너: 자료 항목을 리스트로 정렬하여 첫 번째 요소, 다음 요소 등을 마지막 요소까지 포함한다.
앞에서 설명한 순차 컨테이너 템플릿 클래스는 slist, list, vector, 그리고 deque이다.
디스플레이 19.5 list 템플릿 클래스 이용하기
//Program to demonstrate the STL template class list.
#include <iostream>
#include <list>
using std::cout;
using std::endl;
using std::list;
int main( )
{
list<int> listObject;
for (int i = 1; i <= 3; i++)
listObject.push_back(i);
cout << "List contains:\n"
list<int>::iterator iter;
for (iter = listObject.begin( ); iter != listObject.end( ); iter++)
cout << *iter << " ";
cout << endl;
cout << "Setting all entries to 0:\n"
for (iter = listObject.begin( ); iter != listObject.end( ); iter++)
*iter = 0;
cout << "List now contains:\n"
for (iter = listObject.begin( ); iter != listObject.end( ); iter++)
cout << *iter << " ";
cout << endl;
return 0;
}
샘플 대화 상자
List contains:
1 2 3
Setting all entries to 0:
List now contains:
0 0 0
디스플레이 19.6 STL 기본 순차적 컨테이너
| 템플릿 클래스 이름 | 반복자 형식 이름 | 반복자 종류 | 라이브러리 헤더 파일 |
| slist (경고: 리스트는 STL에 속하지 않습니다.) | slist<T>::iterator slist<T>::const_iterator |
Mutable 순방향 Constant 순방향 |
<slist> (구현에 따라 다르며 사용할 수 없을 수도 있다.) |
| list | list<T>::iterator list<T>::const_iterator list<T>::reverse_iterator list<T>::const_reverse_ iterator |
Mutable 양방향 Constant 양방향 Mutable 양방향 Constant 양방향 |
<list> |
| vector | vector<T>::iterator vector<T>::const_iterator vector<T>::reverse_ iterator vector<T>::const_reverse_ iterator |
Mutable 임의 접근 Constant 임의 접근 Mutable 임의 접근 Constant 임의 접근 |
<vector> |
| deque | deque<T>::iterator deque<T>::const_iterator deque<T>::reverse_ iterator deque<T>::const_reverse_ iterator |
Mutable 임의 접근 Constant 임의 접근 Mutable 임의 접근 Constant 임의 접근 |
<deque> |
디스플레이 19.7 일부 순차적 컨테이너 멤버 함수
| 멤버 함수(c는 컨테이너 객체) | 의미 |
| c.size( ) | 컨테이너의 요소 수를 반환한다. |
| c.begin( ) | 컨테이너의 첫 번째 요소에 위치한 반복자를 반환한다. |
| c.end( ) | 컨테이너의 마지막 요소보다 하나 더 먼 곳에 위치한 반복자를 반환한다. |
| c.rbegin( ) |
컨테이너의 마지막 요소에 있는 반복자를 반환한다. reverse_iterator와 함께 사용된다. slist의 멤버가 아니다.
|
| c.rend( ) | 컨테이너의 첫 번째 요소보다 하나 더 먼 곳에 있는 반복자를 반환한다. reverse_iterator와 함께 사용된다. slist의 멤버가 아니다. |
| c.push_back(Element) | Element를 시퀀스의 끝에 삽입한다. Slist의 멤버가 아니다. |
| c.push_front(Element) | Element를 시퀀스 맨 앞에 삽입한다. vector의 멤버가 아니다. |
| c.insert(Iterator,Element) | Iterator의 위치 앞에 Element의 복사본을 삽입한다. |
| c.erase(Iterator) | 위치 Iterator에서 요소를 제거한다. 바로 뒤에 있는 위치에서 반복자를 반환한다. 마지막 요소가 제거되면 c.end( )를 반환한다. |
| c.clear( ) | 컨테이너의 모든 요소를 제거하는 void 함수이다. |
| c.front( ) | 시퀀스 앞에 있는 요소에 대한 참조를 반환한다. *(c.begin())와 동일하다. |
| c1 == c2 | c1.size( ) == c2.size( )이고 c1의 각 요소가 c2의 해당 요소와 같으면 참이다. |
| c1 != c2 | !(c1 == c2) |
함정: 반복자 및 요소 제거하기
컨테이너에 요소를 추가하거나 제거하는 것은 다른 반복자에 영향을 줄 수 있다.
일반적으로, 추가하거나 삭제한 후에 반복자가 같은 요소에 위치한다는 보장은 없다.
그러나 일부 컨테이너는
반복자가 제거된 요소에 위치하는 경우를 제외하고
추가하거나 삭제하여 반복자가 이동되지 않도록 보장한다.
지금까지 살펴본 템플릿 클래스 중에서 반복자가 제거된 요소에 위치하는 경우를 제외하고는
slist와 list는 반복자가 추가 또는 삭제에 의해 이동되지 않음을 보장한다.
템플릿 클래스 vector와 deque는 그러한 보장을 제공하지 않다.
팁: 컨테이너에서의 형식 정의
STL 컨테이너 클래스에는 이러한 클래스로 프로그래밍할 때 유용한 형식 정의가 포함되어 있다.
STL 컨테이너 클래스에는
iterator, const_iterator, reverse_iterator 및 const_reverse_iterator
형식 이름이 포함될 수 있음을 이미 확인했다.
일반적으로 다른 형식 정의도 있다.
형식 value_type은 컨테이너에 저장된 요소의 형식이고,
size_type은 멤버 함수 size에 대한 반환 형식인 unsigned 정수형이다.
예를 들어 list<int>::value_type은 int의 다른 이름이다.
지금까지 논의한 템플릿 클래스는 모두 value_type과 size_type으로 정의되어 있다.
컨테이너 어댑터 스택 및 큐
컨테이너 어댑터는 다른 클래스 위에 구현된 템플릿 클래스이다.
예를 들어, 스택 템플릿 클래스는 기본적으로 디크 템플릿 클래스 위에 구현되어 있으며,
이는 스택 구현에 매립된 디크라는 것을 의미한다
모든 자료가 존재하는 곳이다.
그러나 이 구현 세부 사항은 보호되며
스택은 단순한 후입선출(Last in/First Out) 자료 구조로 간주된다.
다른 컨테이너 어댑터 클래스로는 queue와 priority_queue 템플릿 클래스가 있다.
스택과 큐에 대해서는 17장에서 설명했다.
우선순위 큐(priority queue): 각 엔트리가 큐에 추가될 때 우선순위가 부여되는 추가 속성을 가진 큐
모든 엔트리의 우선순위가 같다면,
엔트리는 큐에서 제거되는 것과 동일한 방식으로 우선순위 큐에서 제거된다.
항목의 우선순위가 다르면
우선순위가 높은 항목은 우선순위가 낮은 항목보다 먼저 제거된다.
어댑터 템플릿 클래스 위에 기본 컨테이너 클래스가 있지만
응용 프로그램에 따라 효율성이나 기타 이유로 다른 기본 컨테이너를 지정할 수 있다.
예를 들어 어떤 시퀀스 컨테이너도 stack 템플릿 클래스의 기본 컨테이너로 사용될 수 있고
vector 이외의 시퀀스 컨테이너도 queue 템플릿 클래스의 기본 컨테이너로 사용될 수 있다.
기본 자료 구조는 stack과 queue 모두에 대한 deque이다.
priority_queue의 경우 기본 컨테이너는 vector이다.
기본 컨테이너 형식에 만족한다면
컨테이너 어댑터는 다른 템플릿 컨테이너 클래스처럼 보인다.
예를 들어 기본 컨테이너를 사용하는 stack 템플릿 클래스의 형식 이름은 int형의 스택에 대한 stack<int>이다.
기본 컨테이너를 vector 템플릿 클래스로 지정하려면 stack<int, vector<int>를 형식 이름으로 사용한다.
두 > 기호 사이에는 항상 공백을 삽입해야 한다.
기본 컨테이너는 항상 사용할 것이다.
stack 템플릿 클래스에 대한 멤버 함수 및 기타 세부 정보는 디스플레이 19.8에 제공된다.
queue 템플릿 클래스에 대한 세부 정보는 디스플레이 19.9에 제공된다.
stack 템플릿 클래스를 사용하는 간단한 예는 디스플레이 19.10에 제공된다.
함정: 기반 컨테이너
기본 컨테이너를 지정할 경우
형식 표현식에 두 개의 > 기호를 사이에 공백 없이 두거나 컴파일러가 혼동될 수 있으므로 주의하자.
마지막 두 > s 사이에 공백을 두고 stack<int, vector<int>>를 사용한다.
stack<int, vector<int>>를 사용하지 말자.
디스플레이 19.8 stack 템플릿 클래스
stack 어댑터 템플릿 클래스 세부 정보
타입 이름: T 형식의 요소들의 스택에 대한 stack<T> 또는 stack<T, Sequence_Type>.
라이브러리 헤더: <stack>. <stack> 라이브러리 헤더는 std 네임스페이스에 정의한다.
정의된 형식: value_type, size_type.
반복자가 없다.
샘플 멤버 함수
| 멤버 함수 (s는 스택 객체) |
의미 |
| s.size( ) | 스택의 요소 수를 반환한다. |
| s.empty( ) | 스택이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
| s.top( ) | 스택의 맨 위 멤버에 대한 변경 가능한 참조를 반환한다. |
| s.push(Element) | 스택 상단에 Element의 복사본을 삽입한다. |
| s.pop( ) | 스택의 맨 위 요소를 제거한다. pop은 void 함수이다. 제거된 요소를 반환하지 않다. |
| s1 == s2 | s1.size( ) == s2.size( ) 및 s1의 각 요소가 참일 경우 는 s2의 해당 요소와 동일하다. 그렇지 않으면 false를 반환한다. |
stack 템플릿 클래스에는
기본 생성자, 복사 생성자, 그리고 임의의 시퀀스 클래스의 객체를 가져와 시퀀스의 요소로 스택을 초기화하는 생성자가 있다.
또한 재사용을 위해 모든 저장소를 반환하는 소멸자와 올바른 할당 연산자가 있다.
디스플레이 19.9 queue 템플릿 클래스
queue 어댑터 템플릿 클래스 세부 정보
타입 이름: T 형식의 요소들의 큐에 대한 queue < T > 또는 queue < Sequence_Type, T >.
효율성을 위해 Sequence_Type은 vector 형식이 될 수 없다.
라이브러리 헤더: <queue>. <queue> 라이브러리 헤더는 std 네임스페이스에 정의한다.
정의된 형식: value_type, size_type.
반복자가 없다.
샘플 멤버 함수
| 멤버 함수 (q는 큐 객체) |
의미 |
| q.size( ) | 큐의 요소 수를 반환한다. |
| q.empty( ) | 큐가 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
| q.front( ) | 큐의 맨 앞 멤버에 대한 변경 가능한 참조를 반환한다. |
| q.back( ) | 큐의 맨 뒤 멤버에 대한 변경 가능한 참조를 반환한다. |
| q.push(Element) | Element를 큐 뒤에 추가한다. |
| q.pop( ) | 큐의 앞쪽 요소를 제거한다. pop은 void 함수이다. 제거된 요소를 반환하지 않는다. |
| q1 == q2 | q1.size( ) == q2.size( )이고 q1의 각 요소가 q2의 해당 요소와 같으면 true이고, 그렇지 않으면 false를 반환한다. |
queue 템플릿 클래스에는
기본 생성자, 복사 생성자, 그리고 임의의 시퀀스 클래스의 객체를 가져가서 시퀀스의 요소들로 스택을 초기화하는 생성자가 있다.
그리고 재사용을 위해 모든 저장소를 반환하는 소멸자와 올바른 할당 연산자가 있다.
디스플레이 19.10 stack 템플릿 클래스를 이용한 프로그램
//Program to demonstrate use of the stack template class from the STL.
#include <iostream>
#include <stack>
using std::cin;
using std::cout;
using std::endl;
using std::stack;
int main( )
{
stack< char> s;
cout << "Enter a line of text:\n";
char next;
cin.get(next);
while (next != '\n')
{
s.push(next);
cin.get(next);
}
cout << "Written backward that is:\n";
while ( ! s.empty( ) )
{
cout << s.top( );
s.pop( );
}
cout << endl;
return 0;
}멤버 함수 pop이 하나의 요소를 제거하지만 해당 요소를 반환하지 않는다.
pop은 void 함수이다.
따라서 제거한 요소를 읽기 위해 상단을 사용해야 했다.
샘플 대화 상자
Enter a line of text:
straw
Written backward that is:
warts
연합 컨테이너 set과 map
연관 컨테이너(associate container)는 기본적으로 매우 단순한 데이터베이스이다.
이들은 struct나 다른 종류의 자료를 저장한다.
각 자료 항목에는 해당 키(key)로 알려진 연관 값(value)이 있다.
예를 들어, 자료가 직원의 기록이 있는 struct일 경우 키는 직원의 사회보장번호일 수 있다.
항목은 키를 기준으로 검색된다.
키의 종류와 저장할 자료의 종류는
서로 관계가 있을 필요가 없지만, 서로 관계가 있을 때가 많다.
아주 간단한 경우는 각 자료 항목이 자신의 키인 경우이다.
예를 들어, set에서 모든 요소는 자신의 키이다.
set
set 템플릿 클래스는 어떤 의미에서는 여러분이 상상할 수 있는 가장 간단한 컨테이너이다.
반복 없이 요소를 저장한다.
첫 번째 삽입은 요소를 세트에 배치한다.
첫 번째 이후 추가 삽입은 효과가 없으므로 요소가 두 번 이상 나타나지 않다.
각 요소는 고유의 키이다.
기본적으로 요소를 추가하거나 삭제하고 요소가 집합에 있는지 없는지 묻기만 하면 된다.
모든 STL 클래스와 마찬가지로 set 템플릿 클래스는 효율성을 목표로 작성되었다.
효율적으로 작업하기 위해 set 객체는 해당 값을 정렬된 순서로 저장한다.
요소를 저장하는 데 사용되는 순서를 다음과 같이 지정할 수 있다:
set<T, Ordering>s;
Ordering은 T 형식의 두 인수를 사용하고
bool 값을 반환하는 올바른 순서 관계여야 한다.
T는 저장된 요소의 형식이다.
순서화가 지정되지 않은 경우 순서화는 < 관계 연산자를 사용하는 것으로 가정된다.
set 템플릿 클래스에 대한 몇 가지 기본 세부 정보는 디스플레이 19.11에 제공된다.
템플릿 클래스 set의 멤버 함수 중 일부를 사용하는 방법을 보여주는 간단한 예는 디스플레이 19.12에 제공된다.
map
맵(map): 기본적으로 순서 쌍들의 집합으로 주어진 함수이다.
쌍에 표시되는 각 first 값에 대해 second 값이 많아야 쌍(first, second)가 맵에 표시됩니다.
템플릿 클래스 map은 STL에서 map 객체를 구현한다.
예를 들어, 각 문자열 이름에 고유한 번호를 할당하려면
다음과 같이 map 객체를 선언할 수 있다:
map<string,int> numberMap;
keys로 알려진 string 값의 경우 numberMap 객체는 고유한 int 값을 연결할 수 있다.
연관 배열(associative array)
맵을 생각하는 다른 방법은 연관 배열이다.
전통적인 배열 - 숫자 인덱스에서 값으로 매핑된다.
예를 들어, a[10]=5는 숫자 5를 인덱스 10에 저장한다.
연관 배열 - 선택한 자료 형식을 사용하여 자신의 인덱스를 정의할 수 있다.
예를 들어, numberMap["c++"]=5는 정수 5를 "c++" 문자열과 연결한다.
필요에 따라 insert나 find하는 방법을 사용할 수도 있지만,
편의상 [] 대괄호 연산자는 배열과 같은 표기법을 사용하여 맵에 접근할 수 있도록 정의된다.
set 객체와 마찬가지로 map 객체는 키 값에 따라 요소를 정렬하여 저장한다.
키에 대한 순서를 각괄호 < > 에서 세 번째 항목으로 지정할 수 있다.
순서를 지정하지 않으면 기본 순서가 사용된다.
사용할 수 있는 순서 제한은 set 템플릿 클래스에 허용되는 순서와 동일하다.
순서는 키 값에만 적용된다.
두 번째 형식은 모든 형식이 될 수 있으며 어떤 순서와도 관련이 있을 필요는 없다.
set 객체와 마찬가지로 map 객체에 저장된 항목의 정렬은 효율성 때문에 수행된다.
맵에서 자료를 추가하고 검색하는 가장 쉬운 방법은 [] 연산자를 사용하는 것이다.
맵 객체 m이 주어지면 m[key]라는 표현은 key와 관련된 자료 요소에 대한 참조를 반환한다.
key에 대한 항목이 맵에 존재하지 않으면 자료 요소에 대한 기본값으로 새 항목이 생성된다.
이는 맵에 새 항목을 추가하거나 기존 항목을 대체하는 데 사용할 수 있다.
예를 들어 m[key] = newData; 문은
key와 newData 사이에 새로운 연관성을 만든다.
맵 항목이 실수로 생성되지 않도록 주의해야 한다.
예를 들어 val = m[key] 문을 실행하면
key와 관련된 값을 검색할 의도로 잘못 입력했지만
맵에 아직 없는 key에 대한 값을 입력하면
기본값을 가진 key에 대한 새 항목이 생성되어 val에 할당된다.
디스플레이 19.11 set 템플릿 클래스
set 템플릿 클래스 세부 사항
형식 이름: T 형식의 요소 set에 대해 set<T> 또는 set<T, Ordering>.
Ordering은 다음 작업에 사용된다
저장을 위해 요소를 정렬한다.
Ordering이 제공되지 않으면 사용되는 Ordering은 이진 연산자 <이다.
라이브러리 헤더: <set>. <set> 라이브러리 헤더는 std 네임스페이스에 정의한다.
정의된 형식에는 value_type, size_type이 있다.
반복자: iterator, const_iterator, reverse_iterator 및 const_reverse_iterator.
모든 반복자는 양방향이며 const_를 포함하지 않는 반복자는 변형 가능하다.
begin(), end(), rbegin() 및 rend()가 예상되는 동작을 가진다.
요소를 추가하거나 삭제하는 것은 제거된 요소에 위치한 반복자를 제외하고 반복자에 영향을 주지 않다.
샘플 멤버 함수
| 멤버 함수 (s는 set 객체) |
의미 |
| s.insert(Element) | Element의 복사본을 집합에 삽입한다. Element가 이미 집합에 있으면 효과가 없다. |
| s.erase(Element) | Element를 집합에서 제거한다. Element가 집합에 없으면 효과가 없다. |
| s.find(Element) | Element 집합의 복사본에 있는 반복자를 반환한다. Element가 집합에 없으면 s.end( )가 반환된다. 반복자가 변경 가능한지 여부는 구현에 따라 달라진다. |
| s.erase(Iterator) | Iterator의 위치에서 요소를 지운다. |
| s.size( ) | 집합의 요소 수를 반환한다. |
| s.empty( ) | 집합이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
| s1 == s2 | 집합에 동일한 요소가 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
또한 set 템플릿 클래스에는 기본 생성자, 복사 생성자 및 여기에 언급되지 않은 다른 특수 생성자가 있다.
또한 재사용을 위해 모든 저장을 반환하는 소멸자와 올바른 할당 연산자가 있다.
디스플레이 19.12 set 템플릿 클래스를 사용한 프로그램
//Program to demonstrate use of the set template class.
#include <iostream>
#include <set>
using std::cout;
using std::endl;
using std::set;
int main( )
{
set<char> s;
s.insert('A');
s.insert('D');
s.insert('D');
s.insert('C');
s.insert('C');
s.insert('B');
cout << "The set contains:\n";
set< char>::const_iterator p;
for (p = s.begin( ); p != s.end( ); p++)
cout << *p << " ";
cout << endl;
cout << "Set contains 'C': ";
if (s.find('C')==s.end( ))
cout << " no " << endl;
else
cout << " yes " << endl;
cout << "Removing C.\n";
s.erase('C');
for (p = s.begin( ); p != s.end( ); p++)
cout << *p << " ";
cout << endl;
cout << "Set contains 'C': ";
if (s.find('C')==s.end( ))
cout << " no " << endl;
else
cout << " yes " << endl;
return 0;
}집합에 요소를 몇 번 추가하더라도 집합에는 해당 요소의 복사본이 하나만 포함된다.
샘플 대화 상자
The set contains:
A B C D
Set contains 'C': yes
Removing C.
A B D
Set contains 'C': no
디스플레이 19.13 map 템플릿 클래스
형식 이름 : KeyType 형식의 요소를 T 형식의 요소와 연관시키는 map에 대한 map<KeyType, T> 또는 map<KeyType, T, Ordering>.
Ordering은 효율적인 저장을 위해 요소를 키 값별로 정렬하는 데 사용된다.
Ordering이 지정되지 않은 경우 사용되는 Ordering은 이진 연산자인 <이다.
라이브러리 헤더: <map>. 정의를 std 네임스페이스에 배치한다.
정의된 형식 : 키 값의 형식에는 key_type, 매핑된 값의 형식에는 mapped_type 및 size_type을 포함한다.
(따라서 정의된 형식의 key_type은 위에서 KeyType이라고 부른 것이다.)
반복자: iterator, const_iterator, reverse_iterator 및 const_reverse_iterator.
모든 반복자들은 양방향이다.
const_를 포함하지 않는 반복자들은 일정하지도 않고 불변하지도 않지만 그 사이에 있는 것들이다.
예를 들어 만약 p가 반복자 형식이라면 키 값은 바꿀 수 있지만 T 형식의 값은 바꿀 수 없다.
적어도 처음에는 모든 반복자들을 일정한 것처럼 취급하는 것이 최선일 것이다.
begin(), end(), rbegin(), rend()가 예상되는 동작을 가진다.
요소를 추가하거나 삭제해도 요소가 제거된 위치에 있는 반복자를 제외하고 반복자에 영향을 주지 않다.
샘플 멤버 함수
| 멤버 함수 (m는 map 객체) |
의미 |
| m.insert(Element) | map에 Element를 삽입한다. Element is of type pair <KeyType, T>. type pair <iterator, boool> 값을 반환한다. 삽입이 성공하면 반환된 쌍의 두 번째 부분이 true이고 삽입된 Element에 반복자가 위치한다. |
| m.erase(Target_Key) | Target_Key 키로 요소를 제거한다. |
| m.find(Target_Key) | 요소에 위치한 반복자를 키 값 Target_Key로 반환한다. 해당 요소가 없는 경우 m.end( )를 반환한다. |
| m[Target_Key] | Target_Key와 연관된 객체에 대한 참조를 반환한다. map에 해당 객체가 이미 포함되어 있지 않으면 T 형식의 기본 객체가 삽입된다. |
| m.size( ) | map의 쌍 수를 반환한다. |
| m.empty( ) | map이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
| m1 == m2 | map에 동일한 쌍이 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다. |
map 템플릿 클래스에는 기본 생성자, 복사 생성자 및 여기에 언급되지 않은 다른 전문 생성자가 있다.
또한 재사용을 위해 모든 저장을 반환하는 소멸자와 올바른 할당 연산자가 있다.
pair
map 템플릿 클래스에 대한 몇 가지 기본적인 세부 사항은 디스플레이 19.13에 나와 있다.
이러한 세부 사항을 이해하기 위해서는 먼저 pair 템플릿 클래스에 대해 알아야 한다.
STL 템플릿 클래스 pair<T1, T2>은
첫 번째 요소가 T1이고 두 번째 요소가 T2 형식인 값의 쌍인 객체를 갖는다.
aPair가 pair<T1, T2> 형식의 객체인 경우
aPair.first는 T1 형식인 첫 번째 요소이고
aPair.second는 T2 형식인 두 번째 요소이다.
멤버 변수 첫 번째와 두 번째는 public 멤버 변수이므로
접근자나 설정자가 필요하지 않다.
pair 템플릿의 헤더 파일은 <utility>이다.
따라서 pair 템플릿 클래스를 사용하려면 파일에 다음과 같은 것이 필요하다:
#include <utility>
using std::pair;
map 템플릿 클래스는 pair 템플릿 클래스를 사용하여
키와 자료 항목 간의 연관성을 저장한다.
예를 들어, 정의가 주어지면
map<string,int> numberMap;
만약 아래의 맵을 더하면
numberMap ["c++"] = 10;
그런 다음 반복자를 사용하여 이 쌍에 접근하는 경우
iterator->first는 "c++" 키를 참조하고
iterator->second는 자료 값 10을 참조한다.
템플릿 클래스 map의 멤버 함수 중 일부를 사용하는 방법을 보여주는 간단한 예가 디스플레이 19.14에 나와 있다.
다른 네 개의 연관 컨테이너
multiset과 multimap은 기본적으로 set과 map으로 동일하지만
multiset은 요소의 반복을 허용하고
multimap은 여러 값을 각각의 키 값에 연관시킬 수 있다.
STL의 일부 구현에는 hash_set과 hash_map 클래스도 있다.
이러한 템플릿 클래스는
해시 테이블을 사용하여 구현된 것을 제외하고는
set과 map으로 기본적으로 동일하다.
해시 테이블 대신 set과 map 클래스의 대부분의 구현에는 균형 잡힌 이진 트리가 사용된다.
균형 잡힌 이진 트리에서 루트 왼쪽에 있는 노드의 수는 루트 오른쪽에 있는 노드의 수와 거의 같다.
효율성
STL 구현은 최적의 효율성을 위해 노력한다.
예를 들어, set 요소와 map 요소는
요소를 검색하는 알고리즘이 더 효율적일 수 있도록 정렬된 순서로 저장된다.
템플릿 클래스의 각 멤버 함수는 최대 실행 시간이 보장된다.
이러한 최대 실행 시간은
19.3절에서 논의한 big-O 표기법(big-O notation)이라고 하는 것을 사용하여 표현된다.
(19.3절은 또한 이미 논의한 컨테이너 멤버 함수의 일부 실행 시간이 보장된다.
이들은 "컨테이너 접근 실행 시간"라는 서브섹션에 나와 있다.)
이 장의 나머지 부분에서 설명하는 특정 함수의 최대 실행 시간이 보장된다.
디스플레이 19.14 map 템플릿 클래스를 이용한 프로그램
//Program to demonstrate use of the map template class.
#include <iostream>
#include <map>
#include <string>
using std::cout;
using std::endl;
using std::map;
using std::string;
int main( )
{
map<string, string> planets;
planets["Mercury"] = "Hot planet";
planets["Venus"] = "Atmosphere of sulfuric acid";
planets["Earth"] = "Home";
planets["Mars"] = "The Red Planet";
planets["Jupiter"] = "Largest planet in our solar system";
planets["Saturn"] = "Has rings";
planets["Uranus"] = "Tilts on its side";
planets["Neptune"] = "1500 mile-per-hour winds";
planets["Pluto"] = "Dwarf planet";
cout << "Entry for Mercury - " << planets["Mercury"]
<< endl << endl;
if (planets.find("Mercury") != planets.end( ))
cout << "Mercury is in the map." << endl;
if (planets.find("Ceres") == planets.end( ))
cout << "Ceres is not in the map." << endl << endl;
cout << "Iterating through all planets: " << endl;
map<string, string>::const_iterator iter;
for (iter = planets.begin( ); iter != planets.end( ); iter++)
{
cout << iter->first << " - " << iter->second << endl;
}
return 0;
}반복자는 키에 따라 정렬된 순서대로 map을 출력한다.
이 경우 출력물은 planet별로 알파벳 순으로 나열된다.
샘플 대화 상자
Entry for Mercury - Hot planet
Mercury is in the map.
Ceres is not in the map.
Iterating through all planets:
Earth - Home
Jupiter - Largest planet in our solar system
Mars - The Red Planet
Mercury - Hot planet
Neptune - 1500 mile-per-hour winds
Pluto - Dwarf planet
Saturn - Has rings
Uranus - Tilts on its side
Venus - Atmosphere of sulfuric acid
19.3 일반 알고리즘
이 섹션에서는 STL의 기본 함수 템플릿에 대해 설명한다.
여기에 있는 모든 것에 대한 포괄적인 설명을 제공할 수는 없지만,
STL에 포함된 것에 대한 좋은 느낌을 주고
이러한 템플릿 함수를 사용하기 위한 충분한 세부 정보를 제공하기 위해
충분히 큰 샘플을 제시할 것이다.
이런 템플릿 함수들을 제네릭 알고리즘(generic algorithms)이라고 부르기도 한다.
알고리즘(algorithm)이라는 용어를 사용하는 데는 이유가 있다.
알고리즘은 그저 어떤 작업을 수행하기 위한 명령어들의 집합이라는 것을 기억하자.
알고리즘은 C++ 같은 프로그래밍 언어를 포함하여 어떤 언어에서든 제시될 수 있다.
하지만 프로그래머들은 알고리즘이라는 단어를 사용할 때
일반적으로 영어나 의사 코드로 제공되는 덜 형식적인 프레젠테이션을 염두에 두고 있다.
그래서 흔히 함수를 정의하는 코드의 추상화라고 생각한다.
코딩의 세부 사항은 물론이고 중요한 세부 사항을 제공한다.
STL은 STL 템플릿 함수의 기본이 되는 알고리즘에 대해
특정한 세부 사항을 지정하기 때문에
이를 제네릭 알고리즘이라고 부르기도 한다.
이러한 STL 함수 템플릿은
단순히 구현자가 원하는 방식으로 값을 전달하는 것 이상의 역할을 한다.
STL의 함수 템플릿은 표준을 충족하기 위해서는
그 구현이 충족해야 하는 최소한의 요구 사항이 제공된다.
대부분의 경우 실행 시간이 보장된 상태에서 구현되어야 한다.
이것은 함수 인터페이스의 개념에 완전히 새로운 차원을 더해준다.
STL에서 인터페이스는 프로그래머에게 함수가 수행하는 기능과 사용 방법을 알려줄 뿐만 아니라
작업을 얼마나 빨리 수행할 것인지 알려준다.
어떤 경우 표준은 코딩의 정확한 세부 사항은 아니지만 사용하는 특정 알고리즘을 지정하기도 한다.
더욱이 특정 알고리즘을 지정할 때는 알려진 알고리즘의 효율성 때문에 지정한다.
핵심적인 새로운 점은 코드에 대한 효율성 보장 규격이다.
이번 장에서는
제네릭 알고리즘, 제네릭 함수, STL 함수 템플릿이라는 용어를 사용하여
동일한 의미로 사용하고자 한다.
이러한 템플릿 함수 또는 제네릭 알고리즘의 효율성을 논의하기 위한 몇 가지 용어를 사용하기 위해
먼저 알고리즘의 효율성이 일반적으로 측정되는 방법에 대한 몇 가지 배경을 제시한다.
실행 시간 및 Big-O 표기법
만약 당신이 프로그래머에게 그 혹은 그녀의 프로그램이 얼마나 빠른지를 묻는다면,
당신은 "2초"와 같은 대답을 기대할 수 있다.
그러나, 프로그램의 속도는 하나의 숫자로 주어질 수 없다.
프로그램은 일반적으로 더 작은 입력보다 더 큰 입력에 대해 더 오랜 시간이 걸릴 것이다.
당신은 숫자를 정렬하는 프로그램이
1000개의 숫자를 정렬하는 것보다 10개의 숫자를 정렬하는 데 더 적은 시간이 걸릴 것으로 예상할 수 있다.
아마도 10개의 숫자를 정렬하는 데는 2초가 걸리겠지만,
1000개의 숫자를 정렬하는 데는 10초가 걸린다.
그렇다면 어떻게 해야 할까?
프로그래머는 "당신의 프로그램은 얼마나 빠를까?"라는 질문에 답을 한다.
프로그래머는 프로그램이 여러 입력 크기에 걸리는 시간을 보여주는 값 표를 제시해야 한다.
예를 들어, 표는 그림 19.15와 같을 수 있다.
이 표는 한 번의 시간을 제시하는 것이 아니라
다양한 입력 크기에 대해 다른 시간을 제시한다.
수학적인 함수
표는 수학에서 함수(function(라고 불리는 것에 대한 설명이다.
(void가 아닌) C++ 함수가 인수를 가져다가 값을 반환하는 것처럼,
이 함수 역시 입력 크기인 인수를 가져다가
프로그램이 해당 크기의 입력을 받는 시간인 숫자를 반환한다.
이 함수를 T라고 부르면,
T (10) = 2초, T (100) = 2.1초, T (1000) = 10초, T (10,000) = 2.5분
표는 이 함수 T의 값 중 일부의 샘플일 뿐이다.
프로그램은 모든 크기의 입력에 어느 정도 시간이 걸릴 것이다.
표에 나와 있지는 않지만
T (1), T (2), ., T (101), T (102) 등에 대한 값도 있다.
임의의 양의 정수 N에 대하여,
T (N)
= 프로그램이 N개의 숫자를 정렬하는 데 걸리는 시간
= 프로그램의 실행 시간(running time)
지금까지 우리는 이 정렬 프로그램이 N개의 숫자로 이루어진 리스트에서 동일한 시간이 걸릴 것이라고 가정해왔다.
그것은 사실일 필요가 없다.
만약 리스트가 이미 정렬되었거나 거의 정렬되어 있다면
아마도 훨씬 적은 시간이 걸릴 것이다.
T(N)은
= 가장 어려운 리스트에서 걸린 시간,
= 프로그램이 가장 오래 실행되도록 만드는 N개의 숫자로 이루어진 리스트에서 걸린 시간
= 최악의 경우 실행 시간(worst-case running time)
이 장에서 우리는 알고리즘이나 어떤 코드에 대해 실행 시간을 줄 때
항상 최악의 경우 실행 시간을 의미할 것이다.
프로그램이나 알고리즘에 걸리는 시간은
종종 4N + 3, 5N + 4, 또는 N 2와 같은 공식으로 주어진다.
실행 시간 T(N)가 5N + 5이면
크기 N의 입력으로 프로그램은 5N + 5 시간 단위로 실행된다.
다음은 N개의 요소로 배열 a를 검색하여
특정 값 target이 배열에 있는지 여부를 확인하는 몇 가지 코드이다:
int i = 0;
bool found = false;
while (( i < N) && !(found))
if (a[i] == target)
found = true;
else
i++;
디스플레이 19.15 실행 시간 함수의 일부 값
| 입력 크기 | 실행 시간 |
| 10 numbers | 2 seconds |
| 100 numbers | 2.1 seconds |
| 1000 numbers | 10 seconds |
| 10,000 numbers | 2.5 minutes |
우리는 컴퓨터가 이 코드를 실행하는 데 걸리는 시간에 대한 어느 정도의 추정치를 계산하려고 한다.
우리가 어떤 컴퓨터를 사용할지 모르기 때문에
또는 여러 컴퓨터를 사용하여 다른 시간에 프로그램을 실행할 수 있기 때문에,
우리는 어떤 컴퓨터를 사용하는지에 의존하지 않는 추정치를 원한다.
연산
한 가지 가능성은 "단계"의 수를 세는 것이지만, 단계가 무엇인지 결정하는 것은 쉽지 않다.
이 상황에서 일반적으로 해야 할 일은 연산(operation)의 수를 세는 것이다.
연산이라는 용어는 단계(step)라는 용어만큼 모호하지만,
실제로 어떤 것이 연산으로 적합한지에 대해서는 적어도 어느 정도 일치하다.
C++ 코드에 대해 다음 중 하나를 적용하면 연산으로 계산된다: =, <, &, !, [], ==, ++.
컴퓨터는 이러한 연산 이외에도 다른 작업을 수행해야 하지만,
이러한 작업이 수행되는 주요 작업인 것 같고,
우리는 이들이 이 코드를 실행하는 데 필요한 대부분의 시간을 차지한다고 가정할 것이다.
사실 시간에 대한 우리의 분석은
다른 모든 작업에 전혀 시간이 걸리지 않으며,
프로그램이 실행되는 데 필요한 총 시간은
이러한 연산을 수행하는 데 필요한 시간과 같다고 가정할 것이다.
비록 이것이 완전히 사실이 아닌 이상적인 가정이지만,
이 단순화 가정은 실제로 잘 작동하며,
프로그램이나 알고리즘을 분석할 때 자주 사용된다.
단순화 가정을 하더라도,
우리는 여전히 두 가지 경우를 고려해야 한다:
target이 배열에 있는지 없는지.
1) target이 배열에 없을 때의 경우
수행되는 연산의 수는 탐색된 배열 소자의 수에 따라 달라질 것이다.
연산 =는 반복문이 실행되기 전에 두 번 수행된다.
목표값이 배열에 없다고 가정하기 때문에,
배열 소자마다 하나씩, N번 반복문이 실행될 것이다.
반복문이 실행될 때마다, 다음과 같은 연산이 수행된다: <, &, !, [], ==, ++.
이것은 N번의 반복문을 반복할 때마다 5번의 연산을 추가한다.
마지막으로, N번의 반복 후에 부울 식을 다시 체크하고 false임을 발견한다.
이것은 마지막 세 번의 연산을 추가한다 (<, &, !).
이 모든 연산을 집계하면,
target이 배열에 없을 때 총 6N+5 연산을 얻게 된다.
2) target이 배열에 있을 때, 연산의 수가 6N+5 이하가 된다는 것을
독자가 확인하는 연습문제로 남겨둘 것이다.
1), 2)에 의해
N개 원소로 이루어진 배열과 target에 대한
최악의 경우 실행 시간은 T(N) = 6N+5 연산이다.
우리는 방금 우리의 검색 코드가
작동하는 최악의 경우는 6N + 5번의 작동 시간이라고 결정했다.
그러나 작동은 나노초, 초, 분과 같이 전통적인 시간 단위가 아니다.
알고리즘이 어떤 특정 컴퓨터에 얼마나 걸리는지 알고 싶다면,
우리는 그 컴퓨터가 한 작동을 수행하는 데 얼마나 걸리는지 알아야 한다.
만약 1 나노초에 작동을 수행할 수 있다면, 그 시간은 6 N + 5 나노초가 될 것이다.
만약 1초에 작동을 수행할 수 있다면, 그 시간은 6 N + 5초가 될 것이다.
우리가 작동을 수행하는 데 10초가 걸리는 느린 컴퓨터를 사용한다면,
그 시간은 60 N + 50초가 될 것이다.
일반적으로, 컴퓨터가 한 작동을 수행하는 데 c 나노초가 걸린다면,
실제 작동 시간은 약 c (6 N + 5) 나노초가 될 것이다.
(우리는 몇 가지 단순화된 가정을 하고 있기 때문에,
따라서 그 결과가 완전히 정확한 작동 시간이 아닐 수도 있기 때문에
대략적으로 말했을 것이다.)
이것은 우리의 작동 시간이 6 N + 5라는 매우 조잡한 추정치임을 의미한다.
실행 시간을 나노초 단위로 표현하려면 사용하는 컴퓨터에 따라 달라지는 일정한 상수를 곱해야 한다.
우리가 추정한 6 N + 5는 상수 배수 내에서만 정확한다.
달리기 시간에 대한 추정은
일반적으로 big-O 표기법(big-O notation)으로 표현된다.
(O는 숫자 0이 아니라 문자 "Oh"이다.)
달리기 시간을 6 N + 5 연산으로 추정하고,
각각의 다른 연산의 정확한 달리기 시간이 무엇이든 간에,
실제 달리기 시간이 c (6 N + 5)보다 작거나 같은 상수 c가 항상 존재한다고 가정한다
이런 상황에서 우리는 코드가 O(6 N + 5) 시간에 실행된다고 말한다.
이것은 보통 "6N + 5의 big-O"라고 읽힌다.
우리는 상수 c가 무엇인지 알 필요가 없다.
사실, 컴퓨터마다 다를 것은 의심할 여지가 없지만,
우리는 어떤 합리적인 컴퓨터 시스템에도 그런 c가 하나 있다는 것을 알아야 한다.
컴퓨터가 매우 빠르다면 c는 1보다 작을 수도 있고, 예를 들어 0.001일 수도 있다.
컴퓨터가 매우 느리면 c는 매우 클 수도 있고, 예를 들어 1000일 수도 있다.
게다가, 단위를 나노초에서 초로 바꾸는 것은 단지 상수의 배수만을 수반하기 때문에,
어떤 단위의 시간도 줄 필요가 없다.
큰 O의 추정치는 상한의 추정치임을 명심해야 한다.
우리는 항상 실수의 낮은 쪽이 아니라 높은 쪽의 숫자를 취함으로써 근사치를 구한다.
또한 큰 O의 추정치를 수행할 때 우리는 수행된 작업의 수를 정확하게 계산할 필요는 없다.
우리는 상수 배수까지 정확한 추정치만 필요하다.
만약 우리의 추정치가 실수의 두 배라면 그것으로도 충분하다.
작업의 크기
앞의 6 N + 5와 같은 크기 순서의 추정치는
알고리즘에 의해 해결된 작업의 크기에 대한 매개변수를 포함한다.
예제의 경우 이 매개변수 N은 검색할 배열 요소의 수이다.
더 적은 수의 배열 요소를 검색하는 것보다
더 많은 수의 배열 요소를 검색하는 데
시간이 더 걸리는 것은 당연하다.
실행 시간 big-O 추정치는 항상 문제의 크기에 대한 함수로 표시된다.
이 장에서 모든 알고리즘은 컨테이너에 포함된 다양한 값을 포함한다.
모든 경우에 N은 해당 범위에 속하는 요소의 수이다.
다음은 big-O 추정에 대한 대안적이고 실용적인 방법이다:
지수가 가장 높은 항만 보고 상수 배수에는 관심을 기울이지 않다.
예를 들어 다음은 모두 O(N2)이다:
N2 + 2N + 1, 3N2 + 7, 100N2 + N
다음은 모두 O(N3)이다:
N3 + 5N2 + N + 1, 8N3 + 7, 100N3 + 4N + 1
이 빅 O 실행 시간 추정치들은 분명히 조잡하지만, 몇 가지 정보를 포함하고 있다.
이들은 실행 시간이 5 N + 5인지, 100N인지 구별하지 않을 것이지만,
실제로 실행 시간을 구별할 수 있게 해주어
일부 알고리즘이 다른 알고리즘보다 빠르다는 것을 확인할 수 있다.
화면 19.16의 그래프를 보고
O(N)인 함수의 그래프는 결국 0.5 N^2인 함수의 그래프보다 아래로 떨어진다.
결과는 필연적이다.
우리가 충분히 큰 N 값을 사용한다면,
O(N) 알고리즘은 항상 O(N^2) 알고리즘보다 빠르게 실행될 것이다.
비록 O(N^2) 알고리즘이 당신이 다루는 문제의 크기에 비해 O(N) 알고리즘보다 빠를 수 있지만,
프로그래머들은 실제로는 직관적으로 "크다"는
대부분의 실제 응용에서 O(N) 알고리즘이 O(N^2) 알고리즘보다 더 잘 작동한다는 것을 발견했다.
비슷한 언급은 다른 두 가지 다른 큰 O 실행 시간에도 적용된다.
일반적인 알고리즘 러닝타임에 대한 우리의 설명에 몇 가지 용어가 도움이 될 것이다.
선형 러닝타임(Linear running time): T (N) = aN + b의 러닝타임
선형 러닝타임은 항상 O (N) 러닝타임이다.
2차 러닝타임(Quadratic running time): 가장 높은 항이 N^2인 러닝타임
2차 러닝타임은 항상 O (N^2) 러닝타임이다.
우리는 또한 때때로 실행 시간 공식에 로그를 가질 것이다.
기저(base)를 바꾸는 것은 단지 상수의 배수이기 때문에,
이것들은 어떤 기저도 갖지 않고 주어진다.
만약 log N이 보인다면, 로그 밑이 N의 2라고 생각해도 틀린 것은 아니다.
로그는 매우 느리게 증가하는 함수이다.
따라서 O(log N) 실행 시간은 매우 빠르다.
많은 경우에 실행 시간 추정치가 big-O 추정치보다 더 나을 것이다.
특히, 선형 실행 시간을 지정할 때는 엄격한 상한이 되는데,
c가 여전히 지정되지는 않았지만 실행 시간은 정확히 T(N) = cN이라고 생각할 수 있다.
컨테이너 접근 실행 시간
이제 빅 O 표기법에 대해 알게 되었으므로,
19.2절에서 논의한 컨테이너 클래스에 대한 접근 함수의 일부 효율성을 표현할 수 있다.
vector의 뒤(push_back),
deque의 앞이나 뒤(push_back and push_front),
list의 임의(insert)의 삽입들은 모두 O(1)이다
(즉, 컨테이너의 크기에 무관한 실행 시간 상의 일정한 상한).
vector 또는 deque에 대한 임의의 원소의 삽입 또는 삭제는 O(N)이며,
여기서 N은 컨테이너 안의 원소들의 수이다.
set 또는 map 찾기의 경우 (find)는 O(log N)이며,
N은 컨테이너 안의 원소들의 수이다.
디스플레이 19.16 실행 시간의 비교
비수정 시퀀스 알고리즘
이 절에서는 컨테이너에서 작동하지만
컨테이너의 내용물을 어떤 식으로든 수정하지 않는 템플릿 함수를 설명한다.
제네릭 find 함수는 간단하고 전형적인 좋은 예이다.
제네릭 find 함수는 set 템플릿 클래스의 find 멤버 함수와 유사하지만 다른 find 함수이다.
제네릭 find 함수는 STL 시퀀스 컨테이너 클래스 중 어느 것에도 사용할 수 있다.
디스플레이 19.17은 클래스 vector<char>와 함께 사용되는 제너릭 find 함수의 샘플 사용을 보여준다.
디스플레이 19.17의 함수는
vector<char>를 전체적으로 list<char>로 대체하거나
vector<char>를 다른 시퀀스 컨테이너 클래스로 대체한 경우와
정확히 동일하게 동작한다.
그래서 함수들을 제너릭(generic)이라고 부르는 이유 중 하나는
find 함수의 한 가지 정의로 다양한 컨테이너를 선택할 수 있다.
디스플레이 19.17 일반적인 find 함수
//Program to demonstrate use of the generic find function.
#include <iostream>
#include <vector>
#include <algorithm>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::find;
int main( )
{
vector< char> line;
cout << "Enter a line of text:\n";
char next;
cin.get(next);
while (next != '\n';
{
line.push_back(next);
cin.get(next);
}
vector< char>::const_iterator where;
where = find(line.begin( ), line.end( ), 'e');
//where is located at the first occurrence of 'e' in v.
vector< char>::const_iterator p;
cout << "You entered the following before you"
<< "entered your first line:\n";
for (p = line.begin( ); p != where; p++)
cout << *p;
cout << endl;
cout << "You entered the following after that:\n";
for (p = where; p != line.end( ); p++)
cout << *p;
cout << endl;
cout << "End of demonstration.\n";
return 0;
}find가 원하는 것을 찾지 못하면 두 번째 인수를 반환한다.
샘플 대화 상자 1
Enter a line of text
A line of text.
You entered the following before you entered your first e:
A lin
You entered the following after that:
e of text.
End of demonstration.
샘플 대화 상자 2
Enter a line of text
I will not!
You entered the following before you entered your first e:
I will not!
You entered the following after that:
End of demonstration.
find가 찾는 항목을 찾지 못하면 line.end( )를 반환한다.
find 함수가 찾는 요소를 찾지 못하면 두 번째 반복자 인수를 반환한다.
이 인수는 디스플레이 19.17에서와 같이 end( )과 동일할 필요는 없다.
해당 디스플레이의 샘플 대화 2는 find가 검색한 내용을 찾지 못할 때의 상황을 보여준다.
find는 어떤 컨테이너에서도 작동할까? 아니다, 정확히는 아니다.
우선 반복자를 인수로 사용하고 stack과 같은 일부 컨테이너에는 반복자가 없다.
find 함수를 사용하려면 컨테이너에 반복자가 있어야 하고 요소가 저장되어야 한다
++ 연산자가 컨테이너를 통해 반복자를 이동할 수 있도록
선형 순서로 정렬하고 ==를 사용하여 요소가 유사해야 한다.
즉, 컨테이너에는 순방향 반복자
(또는 양방향 반복자와 같은 더 강한 종류의 반복자)가 있어야 한다.
제너릭 함수 템플릿을 표시할 때는
필요한 종류의 반복자 이름을 형식 매개 변수 이름으로 사용하여
반복자 형식 매개 변수를 설명한다.
list, vector 또는 기타 컨테이너 템플릿 클래스의 iterator 형식과
같은 종류의 전달 반복자에 대한 형식으로 대체되어야 한다.
양방향 반복자도 순방향 반복자이고 임의 접근 반복자도 양방향 반복자라는 점을 기억하자.
따라서 ForwardIterator라는 형식 이름은
모든 반복자 형식에서 양방향 또는 임의 접근 반복자 형식뿐만 아니라
일반 오래된 순방향 반복자 형식에서도 사용할 수 있다.
ForwardIterator를 지정할 때는
더 간단한 반복자 형식, 즉 입력 반복자 또는 출력 반복자를 사용할 수 있다.
그러나 입력 및 출력 반복자에 대해 논의하지 않았기 때문에 함수 템플릿 선언에서 언급하지 않다.
전달 반복자, 양방향 반복자, 임의 접근 반복자라는 이름은
형식 이름이 아니라 반복자의 종류를 가리킨다는 것을 기억하자.
실제 형식 이름은 std::vector<int>::iterator와 같은 것이 되는데, 이 경우에는 임의 접근 반복자가 된다.
디스플레이 19.18은 STL의 일부 비수정 일반 함수의 샘플을 제공한다.
디스플레이 19.18은 컨테이너 반복자를 논의할 때 일반적으로 사용되는 표기법을 사용한다.
범위(range): 반복자 first에서 last를 포함하지 않고 반복자 last로 이동할 때 발생하는 반복자 위치
예를 들어 for문의 경우 [first, last) 범위의 모든 요소를 출력한다:
for (iterator p = first; p != last; p++)
cout << *p << endl;
두 개의 범위가 주어졌을 때, 같은 컨테이너 안에 있을 필요는 없다.
예를 들어, search 함수의 범위 [first1, last1)과 [first2, last2)는
같은 컨테이너 안에 있을 수도 있고 다른 컨테이너 안에 있을 수도 있다.
디스플레이 19.18에는 find, search, binary_search의 세 가지 검색 함수가 있다.
함수 search는 하위 시퀀스를 검색하는 반면
함수find와 binary_search는 하나의 값을 검색한다.
단일 원소를 검색할 때
find 또는 binary_search를 사용할 것인지 어떻게 결정할까?
한 함수는 반복자를 반환하고 다른 함수는 부울 값만 반환하지만
그것이 가장 큰 차이는 아니다.
binary_search 함수는
검색할 범위를 <를 사용하여 오름차순으로 정렬하고
O(log N) 시간에 실행할 것을 요구하는 반면,
find 함수는
범위를 정렬할 필요가 없고
선형 시간만 보장한다.
원소를 순서대로 정렬한 경우 또는 정렬할 수 있는 경우
binary_search를 사용하여 훨씬 더 빠르게 찾을 수 있다.
Range [first, last)
일부 반복자 first, 종종 container.begin(),
일부 위치 last, 종종 container.end()의 이동은 매우 일반적이어서
range [first, last]라는 특별한 이름을 갖게 되었다.
예를 들어, 다음 코드는 [c.begin( ), c.end( )) 범위의 모든 요소를 출력한다.
여기서 c는 벡터와 같은 일부 컨테이너 객체이다:
for (iterator p = c.begin( ); p != c.end( ); p++)
cout << *p << endl;
binary_search 함수를 사용하면
구현 시 13장에서 설명한 binary search 알고리즘을 사용할 수 있다.
이진 탐색 알고리즘을 사용할 때 중요한 점은
매우 빠른 실행 시간인 O(log N)를 보장한다는 것이다.
만약 13장을 읽지 않고 이진 탐색에 대해 들어보지 않았다면,
요소들을 정렬해야 하는 매우 효율적인 탐색 알고리즘이라고 생각하면 된다.
이 장에서 다루는 내용과 관련된 이진 탐색에 관한 두 가지 사항은 이것뿐이다.
디스플레이 19.18 일부 수정하지 않는 일반 함수
이러한 함수들은 모두 순방향 반복자에서 작동하므로 양방향 및 임의 접근 반복자에서도 작동한다.
(어떤 경우에는 우리가 자세히 다루지 않은 다른 종류의 반복자에서도 작동한다.)
template < class ForwardIterator, class T>
ForwardIterator find(ForwardIterator first, ForwardIterator last, const T& target);
//Traverses the range [first, last) and returns an iterator located at
//the first occurrence of target. Returns second if target is not found.
//Time complexity: linear in the size of the range [first, last).
template < class ForwardIterator, class T>
int4 count(ForwardIterator first, ForwardIterator last, const T& target);
//Traverse the range [first, last) and returns the number
//of elements equal to target.
//Time complexity: linear in the size of the range [first, last).
template < class ForwardIterator1, class ForwardIterator2>
bool equal(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
//Returns true if [first1, last1) contains the same elements in the same
//order as the first last1-first1 elements starting at first2.
//Otherwise, returns false.
//Time complexity: linear in the size of the range [first, last).
template < class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
//Checks to see if [first2, last2) is a subrange of [first1, last1).
//If so, it returns an iterator located in [first1, last1) at the start
//of the first match. Returns last1 if a match is not found.
//Time complexity: quadratic in the size of the range [first1, last1).
template < class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& target);
//Precondition: The range [first, last) is sorted into ascending order
//using <.
//Uses the binary search algorithm to determine if target is in the
//range [first, last).
//Time complexity: For random-access iterators O(log N). For nonrandom-
//access iterators linear in N, where N is the size of the range [first,
//last).
수정 시퀀스 알고리즘
디스플레이 19.19는 컨테이너의 내용을 어떤 식으로든 변경하는 STL의 일부 제너릭 함수에 대한 설명을 포함한다.
컨테이너에 요소를 추가하거나 제거하는 것은 다른 반복자들에게 영향을 줄 수 있다는 것을 기억하자.
컨테이너 템플릿 클래스가 그러한 보증을 하지 않는 한,
반복자들이 추가 또는 삭제 후에 같은 요소에 위치한다는 보장은 없다.
우리가 본 템플릿 클래스 중에서 반복자가 제거된 요소에 위치하는 경우를 제외하고,
slist와 list는 반복자가 추가 또는 삭제에 의해 이동되지 않는다는 보증을 제공한다.
템플릿 클래스 vector와 deque는 그러한 보증을 제공하지 않다.
디스플레이 19.19의 함수 템플릿 중 일부는 특정 반복자의 값을 보증한다.
물론 컨테이너가 무엇이든 간에 이러한 보증을 사용할 수 있다.
디스플레이 19.19
반복자 형식 매개변수의 이름은 함수가 작동하는 반복자의 종류를 알려준다.
이것들은 최소 반복자 요구사항임을 기억하자.
예를 들어, ForwardIterator 반복자는 순방향 반복자, 양방향 반복자 및 임의 접근 반복자에서 작동한다.
template < class T>
void swap(T& variable1, T& variable2);
//Interchanges the values of variable1 and variable2.
template < class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 copy(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2);
//last2 is such that the ranges [first1, last1) and [first2, last2) are
//the same size.
//Action: Copies the elements at locations [first1, last1) to
//locations [first2, last2). Returns last2.
//Time complexity: linear in the size of the range [first1, last1).
template < class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& target);
//Removes those elements equal to target from the range [first, last).
//The size of the container is not changed. The removed values equal to
//target are moved to the end of the range [first, last). There is then
//an iterator i in this range such that all the values not equal to
//target are in [first, i). This i is returned. Time complexity: linear
//in the size of the range [first, last).
template < class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);
//Reverses the order of the elements in the range [first, last).
//Time complexity: linear in the size of the range [first, last).
template < class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);
//Uses a pseudorandom number generator to randomly reorder the elements
//in the range [first, last).
//Time complexity: linear in the size of the range [first, last).
집합 알고리즘
디스플레이 19.20은 STL에 정의된 일반 집합 연산 함수의 샘플을 보여준다.
일반 알고리즘은 컨테이너가 요소를 정렬된 순서로 저장한다고 가정한다.
컨테이너 set, map, multiset과 multimap은 요소를 정렬된 순서로 저장하므로
디스플레이 19.20의 모든 함수는 이 네 개의 템플릿 클래스 컨테이너에 적용된다.
벡터와 같은 다른 컨테이너는 요소를 정렬된 순서로 저장하지 않는다.
이러한 함수는 이러한 컨테이너와 함께 사용하면 안 된다.
요소를 정렬하도록 요구하는 이유는 알고리즘이 더 효율적일 수 있기 때문이다.
디스플레이 19.20 집합 연산
이러한 함수들은
set, map, multiset, multimap(및 다른 컨테이너)에는 작동하지만
모든 컨테이너에는 작동하지 않는다.
예를 들어, 컨테이너가 정렬되지 않는 한
vector, list 또는 deque에는 작동하지 않는다.
이러한 함수들이 작동하려면
컨테이너의 요소들이 정렬된 순서로 저장되어야 한다.
이 모든 것들은 순방향 반복자에도 작동하므로
양방향 및 임의 접근 반복자에도 작동한다.
(어떤 경우에는, 우리가 자세히 다루지 않은 다른 종류의 반복자에도 작동한다.)
template < class ForwardIterator1, class ForwardIterator2>
bool includes(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
//Returns true if every element in the range [first2, last2) also occurs
//in the range [first1, last1). Otherwise, returns false.
//Time complexity: linear in the size of [first1, last1) plus [first2,
//last2).
template < class ForwardIterator1, class ForwardIterator2, class ForwardIterator3>
void5 set_union(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator3 result);
//Creates a sorted union of the two ranges [first1, last1) and [first2,
//last2). The union is stored starting at result.
//Time complexity: linear in the size of [first1, last1) plus [first2,
//last2).
template <class ForwardIterator1, class ForwardIterator2,
class ForwardIterator3>
void5 set_intersection(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator3 result);
//Creates a sorted intersection of the two ranges [first1, last1) and
//[first2, last2). The intersection is stored starting at result.
//Time complexity: linear in the size of [first1, last1) plus [first2,
//last2).
template < class ForwardIterator1, class ForwardIterator2, class ForwardIterator3>
void5 set_difference(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator3 result);
//Creates a sorted set difference of the two ranges [first1, last1) and
//[first2, last2). The difference consists of the elements in the first
//range that are not in the second. The result is stored starting at
//result. Time complexity: linear in the size of [first1, last1) plus
//[first2, last2).
정렬 알고리즘
디스플레이 19.21은 두 가지 템플릿 함수에 대한 선언 및 설명서를 제공한다.
하나는 원소 범위를 정렬하는 것이고 하나는 정렬된 두 범위의 원소를 병합하는 것이다.
정렬 함수 정렬은 O(N log N)의 실행 시간을 보장한다.
이 책의 범위는 벗어나지만 O(N log N)보다 빠른 정렬 알고리즘을 작성할 수 없음을 보여줄 수 있다.
따라서 이 함수는 정렬 알고리즘이 일정한 배수까지 최대한 빠르다는 것을 보장한다.
디스플레이 19.21 일부 일반 정렬 알고리즘
template < class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
//Sorts the elements in the range [first, last) into ascending order.
//Time complexity: O(N log N), where N is the size of the range [first,
//last).
template < class ForwardIterator1, class ForwardIterator2,
class ForwardIterator3>
void merge(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
ForwardIterator3 result);
//Precondition: The ranges [first1, last1) and [first2, last2) are
//sorted.
//Action: Merges the two ranges into a sorted range [result, last3)
//where last3 = result + (last1 - first1) + (last2 - first2).
//Time complexity: linear in the size of the range [first1, last1 )
//plus the size of [first2, last2).정렬은 < 연산자를 사용하므로 < 연산자를 정의해야 한다.
순서 관계를 제공할 수 있는 다른 버전은 여기에 제공되지 않는다.
"정렬"은 오름차순으로 정렬된 것을 의미한다.
'프로그래밍 공부 > OOP' 카테고리의 다른 글
| 18장 예외 처리 (1) | 2023.12.03 |
|---|---|
| 17장 연계된 자료 구조(3) (0) | 2023.12.01 |
| 17장 연계된 자료 구조(2) (2) | 2023.12.01 |
| 17 연계된 자료 구조(1) (1) | 2023.12.01 |
| 16장 탬플릿 (1) | 2023.11.30 |