40.1 벡터
40.1.1 벡터
벡터는 동일 타입의 자료 집합인 시퀀스 컨테이너 대표이다. 템플릿 기반이므로 임의 타입을 요소로 가질 수 있으며 요소의 개수에 따라 자동으로 메모리를 관리한다. 임의 타입의 동적 배열
벡터의 내구적인 구성 원리는 C의 정적 배열과 거의 유사, 특성과 장단점도 배열과 동일
요소들의 크기가 똑같고 인접한 위치에 이웃하여 배치되어, 메모리를 적게 차지하며 임의 위치를 빠른 속도로 액세스 가능
삽입, 삭제 속도가 느리다
벡터의 선언문
template <class Type, class Allocator = allocator<Type> > class vector
Type은 벡터에 저장되는 요소의 타입이며 벡터는 이 타입의 집합을 관리
Allocator는 내부적인 메모리관리에 사용되는 할당기인데 디폴트가 제공되므로 생략 가능
컨테이너 조작을 위해 사용되는 타입
|
타입 |
설명 |
|
value_type |
컨테이너의 요소 타입이다. |
|
(const_) pointer |
요소를 가리키는 포인터 타입이다. 이하 4개의 타입은 상수 버전도 제공 |
|
(const_) reference |
요소의 레퍼런스 타입이다. |
|
(const_) iteraotr |
요소의 레퍼런스를 가리키는 반복자 타입이다. |
|
(const_) reverse_iterator |
역방향 반복자 타입이다. |
|
difference_type |
두 반복자의 차를 표현하는 타입이다. 통상 int이다 |
|
size_type |
크기를 표현하는 타입이다. 통산 unsigned이다. |
어떤 컨테이너 C의 요소 타입을 알고 싶다면 C에 정의 되어 있는 value_type을 참조
벡터의 생성자
|
explicit vector() ; |
디폴트 생성자 |
|
explicit vector(size_type n, const T& v = T()) ; |
벡터의 초기 크기를 지정하며 T타입의 초기값을 지정 속도를 높이기 위해 첫번째 요소만 생성한 후 나머지 n-1개의 요소는 복사 생성자를 호출하여 생성 |
|
vector(const vector& x) ; |
복사생성자 다른 벡터로부터 똑같은 벡터를 만들어 낸다. 내부에서는 아마도 깊은 복사를 할 것이다. |
|
vector(const_iterator first, const_iterator last) ; |
반복자가 지정한 구간의 요소들을 가지는 새로운 벡터를 생성, 이때 반복자는 꼭 벡터의 반복자가 아니더라도 상관없다. 정적 배열이나 리스트의 반복자를 전달할 수도 있어 다른 컨테이너로부터 벡터를 초기화 할 수 있음 |
- 예제 vectorcon
|
#include <iostream> #include <string> #include <vector> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==>" ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type> (cout," ")) ; cout << endl ; }
void main ( void ) { vector<string> v1; dump("v1", v1) ; vector<double> v2(10); dump("v2", v2) ; vector<int> v3(10,7); dump("v3", v3) ; vector<int> v4(v3); dump("v4", v4) ; int ar[] = { 1,2,3,4,5,6,7,8,9 } ; vector<int> v5(&ar[2], &ar[5]); dump("v5", v5) ; } |
v1은 디폴트 생성자로 인수없이 선언, 빈 벡터 생성
v2는 크기 10의 실수형 벡터이되 초기값을 주지 않았으므로 실수의 디폴트값인 0.0으로 초기화
v3는 정수형의 벡터이되 크긴느 10이고 초기값 7을 주었으므로 7이 열개 들어 있는 상태로 생성
v4는 v3를 복사해서 만들어 졌으므로 완전히 똑같은 모양
v5는 반복자 구간을 받아들이는 생성자로 다른 컨테이너의 구간으로부터 초기값을 받아온다.
벡터는 요소 저장을 위한 메모리를 자동으로 관리한다. 요소가 삽입 될 때는 벡터 크기를 신축적으로 늘리고 벡터가 파괴될 때 할당한 메모리도 알아서 정리한다. 그래서 별도로 벡터 정리 코드를 작성할 필요가 없다. 가끔은 개발자가 직접 개입하여 크기를 관리해야 할 필요도 있다.
벡터의 메모리 관리 함수들은 string의 관리 함수들과 거의 유사하다.
|
함수 |
설명 |
|
size |
요소 개수를 조사한다. |
|
max_size |
벡터가 관리할 수 있는 최대 요소 개수를 조사한다. |
|
capacity |
할당된 요소 개수를 구한다. |
|
resize(n) |
크기를 변경한다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지하며 새로 할당된 요소는 0으로 초기화 된다. |
|
reserve(n) |
최소한의 크기를 지정하며 메모리를 미리 할당해 놓는다. 새 크기가 더 클 경우 벡터의 원래 내용은 유지한다. 새로 할당된 요소는 초기화되지 않는다. |
|
clear(n) |
모든 요소를 삭제한다. |
|
empty |
비어 있는지 조사한다. |
- 예제 vectormem
|
#include <iostream> #include <vector> using namespace std ;
void main ( void ) { vector<int> vi ;
printf("max_size = %d\n", vi.max_size()) ; printf("size = %d, capacity = %d\n", vi.size(), vi.capacity()) ; vi.push_back(123) ; vi.push_back(456) ; printf("size = %d, capacity = %d\n", vi.size(), vi.capacity()) ; vi.resize(10) ; printf("size = %d, capacity = %d\n", vi.size(), vi.capacity()) ; vi.reserve(20) ; printf("size = %d, capacity = %d\n", vi.size(), vi.capacity()) ; } |
빈 벡터를 만들면 크기 0 으로 생성되며 요소를 두 개 추가하면 크기가 2로 늘어난다. resize는 지정한 크기로 요소 수를 늘리며 새로 생겨난 요소는 타입의 디폴트값으로 초기화되는데 vi는 정수형 벡터이므로 int()값인 0으로 초기화
capacity는 할당되어 있는 메모리양인데 이 크긴느 size보다 크거나 같다. 벡터는 메모리가 부족할 경우 현재 용량의 2배식 메모리를 늘려 나가며 앞으로 추가될 요소를 고려하여 약간의 여유분을 미리 할당해 놓는다. capacity() - size()는 할당된 메모리에서 실제 사용한 양의 차이이며 별도의 재할당 없이도 이만큼 더 저장 할 수 있다.
reserve는 미리 메모리를 할당해 놓는 함수인데 재할당의 불이익과 반복자 무효화를 피하기 위해 가끔 이 함수가 꼭 필요하다.
미리 필요한 메모리양을 안다면 자동으로 메모리를 늘리도록 내버려 두지 말고 reserve로 필요한 메모리를 미리 확보해 놓는 것이 유리하다.
clear는 벡터 비우기
empty는 비어있는지 점검
40.1.2 삽입과 삭제
각 컨테이너별로 내부적인 구조가 다르기 대문에 삽입, 삭제 함수는 컨테이너의 멤버 함수로 제공됨.
벡터의 삽입, 삭제 함수
void push_back( const T& x ) ;
void pop_back() ;
push_back은 벡터 끝에 새 요소 x를 추가하고 필요할 경우 메모리 관리까지 한다. 용량이 부족할 경우 재할당을 해서라도 x를 추가하므로 마으놓고 호출할 수 잇다. pop_back은 반대로 벡터의 끝 요소를 삭제한다. 앞뒤의 요소를 읽을 때는 front, back 멤버 함수를 사용하는데 이 함수는 T형의 레퍼런스를 리턴하므로 양끝의 멤버를 읽거나 쓸 수 있다.
벡터는 중간이나 처음에 삽입, 삭제하는 것은 요소의 인접성을 유지하기 위해 뒤족 요소를 이동시켜야 하므로 무척 느리다. 만약 꼭 벡터의 중간에 요소를 삽입 하고 싶다면 insert함수를 사용한다. 벡터에 대해 push_front(V)를 하려면 insert(begin(0, V)를 호출하면 된다.
insert함수 원형
iterator insert(itertor it, const T& x = T()) ;
void insert(iterator it, size_type n, const T& x) ;
void insert(iterator it, const_iterator first, const_iterator last) ;
첫번째 인수 : 삽입 위치를 나타내는 벡터 내의 반복자
나머지 인수로 삽입 대상을 지정하는데 요소 하나, 같은 값 여러 개, 다른 반복자 구간을 삽입 할 수 있다.
insert는 삽입하기 전에 메모리가 부족할 경우 재할당하여 늘리고 it 이후의 요소를 뒤쪽으로 이동시킴
요소를 삭제할 때는 erase 함수 사용
erase함수 원형
iterator erase(iterator it) ;
iterator erase(iterator first, iterator last) ;
- 예제 vectorinsdel
|
#include <iostream> #include <vector> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12); cout << left << desc << "==>" ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout," ")) ; cout << endl ; }
void main ( void ) { const char *str = "0123456789" ; vector<char> vc(&str[0], &str[10]) ; dump ("생성 직후", vc) ; vc.push_back('A'); dump("A 추가", vc) ; vc.insert(vc.begin()+3,'b'); dump("b 삽입", vc) ; vc.pop_back(); dump("끝 요소 삭제", vc); vc.erase(vc.begin()+5, vc.begin()+8); dump("5~8삭제", vc); } |
:: 한꺼번에 삽입, 삭제하기
insert, erase 함수는 개별 요소에 대해 동작하는 버전과 같은 값 여러 개, 도는 구간에 대해 동작하는 버전이 중복 정의 되어 있는데 복수 개의 값을 삽입, 삭제 할 때는 가급적이면 한꺼번에 삽입, 삭제하는 것이 좋다.
- 예제 insdelmulti
|
#include <iostream> #include <vector> using namespace std ;
template<typename C> void dump(const char *desc, C c) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")) ; cout << endl ; }
void main ( void ) { vector<char> vc1 ; for ( int i = 0 ; i < 10 ; i++ ) { vc1.insert(vc1.begin(),'z') ; } dump("개별 추가", vc1) ;
vector<char> vc2 ; vc2.insert(vc2.begin(), 10, 'z') ; dump("한꺼번에 추가", vc2) ; } |
데이터가 늘어날수록 삽입, 삭제는 구간 지정하여 한꺼번에 하는 것이 좋다.
:: 다른 컨테이너와 요소 교환하기
- 예제 insertFromother
|
#include <iostream> #include <vector> #include <list> #include <algorithm> using namespace std ;
template<typename C> void dump( const char *desc, C c ) { cout.width(12) ; cout << left << desc << "==> " ; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")) ; cout << endl ; }
void main ( void ) { list<int> li ; for ( int i = 0 ; i < 100 ; i++ ) { li.push_back(i) ; }
vector<int> vi ; vi.insert(vi.begin(), find(li.begin(), li.end(), 8), find(li.begin(), li.end(), 25)) ; dump("추가 후", vi) ; } |
벡터와 리스트는 내부 구조가 완전히 다르지만 일반화된 반복자를 통해 두 컨테이너의 요소를 액세스 하므로 이런 삽입이 가능하다. 반복자가 컨테이너의 내부 구조에 상관없이 요소를 읽고 다음 위치로 이동하는 기능을 제공하므로 insert 함수는 상대편의 구조를 몰라도 *연산자와 ++만으로 반복자 구간을 읽을 수 있다.
이런 작업이 가능하다는 것이 반복자의 존재 이유이며 일반화된 STL의 강점이다.
STL이 아니라면 리스트와 벡터의 자료 교환은 이보다 훨씬 더 복잡하고 번거로울 것이다.
:: 반복자 무효화 현상
반복자는 컨테이너 내의 요소 위치를 가리키는 일종의 포인터인데 특정 요소를 가리키도록 한 번 설정하면 계속 같은 요소를 가리킨다. 그러나 컨테이너에 삽입, 삭제가 일어나면 메모리 재할당 및 이동이 발생하므로 이 때는 조사해 놓은 반복자가 무효화 될 수 있다. 즉, 반복자가 더 이상 정확한 요소를 가리키지 못하는 것이다.
삽입된 위치의 앞쪽은 무효화 될 수도 있고 그렇지 않을 수도 있는데 재할당에 의해 메모리 번지가 바뀌면 무효화될 것이고 그렇지 않다면 영향을 받지 않을 것이다. 삽입에 의해 재할당이 자주 발생하지는 않지만 모든 경우에 유효성이 보장된다고 할 수는 없으므로 삽입하면 전 반복자가 무효화된다고 보는 것이 옳다.
삭제시는 삭제 구간의 뒤쪽은 무효화되지만 앞쪽은 영향을 받지 않는다. 삭제는 삽입과는 달리 메모리 재할당이 절대로 일어나지 않으므로 앞쪽 요소는 원래 자리를 항상 그대로 유지하기 때문이다.
- 예제 invaliditerator
|
#include <iostream> #include <vector> #include <algorithm> using namespace std ;
void main ( void ) { vector<int> vi ; for ( int i = 0 ; i < 80 ; i++ ) { vi.push_back(i) ; }
vector<int>::iterator it ; it = find(vi.begin(), vi.end(), 55) ; cout << *it << endl ; //< 두개 뻑남 //< vi.insert(vi.begin(), 1234); //< vi.erase(it-1) ; vi.erase(it+1) ; cout << *it << endl ; } |
it 반복자가 55를 가리키돍 했다. *it를 출력하면 반복자가 가리키고 있는 값 55가 출력됨 이 상태에서 it+1, 즉 오른족에 있는 56을 삭제했다. 56 뒤쪽만 무효화
vi.erage ( it - 1 ) ; 바로 왼쪽 54를 지웠는데 이렇게 되면 54 이후의 요소들이 가리키는 반복자들이 전부 무효화된다. vi.insert(vi.begin(), 1234); 선두에 1234요소를 삽입했으므로 모든 요소가 뒤쪽으로 한칸씩 이동하여 무효화
Expression : vector iterator not dereferencable
|
삽입, 삭제 동작은 반복자를 무효화 할 수 있는데 무효화 규칙은 컨테이너마다 다르다. 리스트는 노드들이 메모리의 도처에 흩어져 있으며 삽입, 삭제에 의해 다른 노드들이 이동되는 것은 아니므로 반복자 무효화 현상이 훨씬 덜하다. 삽입의 경우는 전혀 무효화되지 않으며 삭제의 경우는 삭제된 반복자만 무효화된다.
STL 프로그래밍은 주로 반복자를 다루는 작업인데 조사해 놓은 반복자가 무효화되는 현상은 대단히 조심스럽게 다루어야 할 사항이다. 삽입에 의한 반복자 무효화를 최소화하려면 reserve로 메모리를 충분히 할당해 놓아 재할당이 일어나지 않도록 해야 하며 삭제시는 뒤쪽의 반복자를 다시 조사해야 한다. 그러나 조심조심 반복자를 사용하는 것보다는 컨테이너에 조금이라도 변형을 가했다면 이전에 조사해 놓은 반복자 전체를 믿지 않는 편이 더 확실하다.
40.1.3 연산자
:: 대입
벡터끼리 대입할 때는 간단하게 = 연산자 사용
대입을 받는 좌변 벡터는 우변 벡터의 크기만큼 자동으로 크기가 늘어날 것이며 우변의 모든 요소가 좌변에 대입된다.
대입 연산자는 두 벡터를 완전히 똑같이 만드는데 만약 일부 구간만 복사하고 싶다면 assign멤버 함수를 사용한다.
void assign(size_type count, const Type& val);
void assign(InIt first, InIt last);
첫 번째 버전은 val값 count개를 반복적으로 복사한다. 두번째 버전은 반복자 구간을 받아들인다.
- 예제 vectorassign
|
#include <iostream> #include <vector> #include <algorithm> using namespace std;
template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { int ari[] = {1,2,3,4,5}; vector<int> vi( &ari[0], &ari[5] );
vector<int> vi2; vi2 = vi; dump("vi2", vi2);
vector<int> vi3; vi3.assign(vi.begin()+1, vi.end()-1); dump("vi3", vi3); } |
:: 교환
swap 멤버 함수는 두 벡터의 요소들을 통째로 교환한다.
void swap(vector& Right);
벡터끼리 교환하고 싶을 땐느 다음 두 가지 방법 중 하나를 사요한다.
v1.swap(v2); // 멤버 교환
swap(v1, v2); // 알고리즘 교환
일반적인 알고리즘이 있는데도 불구하고 벡터가 특별히 swap 멤버 함수를 제공하는 이유는 일반적인 알고리즘이 요소를 직접 교환하도록 되어 있는데 비해 벡터끼리 교환할 때는 단순히 포인터만 교환하면 훨씬 더 빠르기 때문이다.
그러나 실제로 두 개의 swap함수는 완전히 동등한데 swap알고리즘 함수가 벡터에 대해 부분 특수화되어 있기 때문이다. swap은 두 개의 컨테이너를 교환하되 벡터나 리스트 등 더 빠르게 교환할 수 있는 컨테이너에 대해서는 멤버 함수 버전을 호출하도록 되어 있다.
- 예제 vectorswap
|
#include <iostream> #include <vector> #include <algorithm> using namespace std;
template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { const char str[] = "abcdefghijklmnopqrstuvwxyz"; vector<char> vc1( &str[0], &str[5] ); vector<char> vc2( &str[5], &str[19] ); dump("before vc1", vc1); dump("before vc2", vc2); vc1.swap(vc2); dump("after vc1", vc1); dump("after vc2", vc2); } |
:: 비교
벡터끼리 비교할 때는 ==, != 상등 연산자와 <. >. <=, >= 비교 연산자를 사용한다.
대소를 비교할 때는 대응되는 각 요소들을 일대일로 비교하다가 최초로 다른 요소가 발견되었으 ㄹ때 두 요소의 대소를 비교한 결과를 리턴한다. 한쪽 벡터의 길이가 더 짧아 먼저 끝을 만났다면 아직 끝나지 않은 벡터가 더 큰 것으로 판별한다.
- 예제 vectorcompare
|
#include <iostream> #include <vector> using namespace std;
void main() { const char *str = "0123456789"; vector<char> vc1( &str[0], &str[10] ); vector<char> vc2; vector<char> vc3;
vc2 = vc1; puts( vc1 == vc2 ? "같다" : "다르다" ); puts( vc1 == vc3 ? "같다" : "다르다" );
vc2.pop_back(); puts( vc1 > vc2 ? "크다" : "크지 않다"); } |
:: 요소 참조
벡터의 임의 요소를 읽을 때는 [ ]연산자를 사용하며 괄호 안에 부호 없는 정수로 첨자를 지정한다. 벡터는 임의 접근이 가능하므로 첨자 번호로 요소를 빠르게 참조할 수 있다.
[ ]연산자와 비슷하게 동작하는 at 함수도 정의되어 있는데 인수로 첨자를 지정한다. [ ]연산자는 첨자가 무조건 유효하다고 가정하는 반면 at함수는 벡터의 크기를 점검하여 무효한 첨자일 경우 out_of_range예외를 발생시킨다.
const_reference at(size_type pos) const;
reference at(size_type pos);
- 예제 indexat
|
#include <iostream> #include <vector> #include <algorithm> using namespace std;
void main() { int ari[] = {1,2,3,4,5}; vector<int> vi(&ari[0], &ari[5]); try{ // cout << vi[10] << endl; cout << vi.at(10) << endl; } catch(out_of_range e) { cout << "벡터의 범위를 벗어남" << endl; } } |
at함수가 예외를 처리하므로 안전성이 좀 더 높지만 액세스할 때마다 첨자 범위를 일일이 점검해야 하므로 느리다. 예외 처리를 위해 반드시 try, catch 블록을 구성해야 하므로 번거롭기도 하다.
이 외에 벡터의 요소를 읽는 방법에는 반복자와 *연산자를 사용하는 방법이 있다. 벡터의 반복자는 +n연산을 지원하므로 *(vi.begin()+n) 연산문으로 n번째 요소를 읽을 수 있으며 vi.end를 기준으로 뺄셈을 하면 끝에서부터 n번째 요소를 읽을 수도 있다.
40.1.4 사용자 정의 요소
벡터는 타입을 받아들이는 클래스 템플릿이므로 임의의 모든 타입을 요소로 가질 수 있다.
- 예제 Timevector
|
#include <iostream> #include <vector> using namespace std;
class Time { protected: int hour, min, sec; public: Time(int h, int m, int s) { hour=h; min=m; sec=s; } void outTime() { printf("%d:%d:%d ", hour, min, sec); } };
template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> "; for( unsigned i = 0 ; i < c.size() ; i++ ) { c[i].outTime(); } cout << endl; }
void main() { vector<Time> vt; vt.push_back(Time(1,1,1)); vt.push_back(Time(2,2,2)); dump("요소2개", vt); } |
벡터에 저장된 객체들은 벡터가 파괴될 때 같이 파괴되므로 Time객체를 별도로 파괴할 필요는 없다. 일반적인 객체는 대단히 클 수 있으므로 벡터에 직접 객체를 저장하는 것보다는 객체의 포인터를 저장하는 것이 성능상 유리하며 훨씬 더 일반적이다.
- 예제 Timeptrvector
|
#include <iostream> #include <vector> using namespace std;
class Time { protected: int hour, min, sec; public: Time(int h, int m, int s) { hour=h; min=m; sec=s; } void outTime() { printf("%d:%d:%d ", hour, min, sec); } };
template<typename C> void dump(const char *dest, C c) { cout.width(12); cout << left << dest << "==> "; for( unsigned i = 0 ; i < c.size() ; i++ ) { c[i]->outTime(); } cout << endl; }
void main() { vector<Time*> vt; vt.push_back(new Time(1,1,1)); vt.push_back(new Time(2,2,2)); dump("요소2개", vt); vector<Time*>::iterator it; for( it = vt.begin() ; it != vt.end() ; it++ ) { delete *it; } } |
벡터의 타입이 vector<Time*>로 변경되었으며 벡터에 요소를 추가할 때 Time객체가 아니라 new 연산자로 동적 생성한 Time객체의 포인터를 저장했다. vt객체는 메모리에 다음과 같이 생성될 것이다.
포인터를 가지는 벡터를 파괴할 때는 각 포인터가 가리키는 객체를 직접 파괴해야 한다. 그렇지 않으면 동적으로 생성한 객체가 파괴되지 않으므로 메모리 누수가 발생한다.
벡터에 임의의 타입을 저장할 수 있지만 그렇다고 정말 아무 타입이나 저장할 수 있는 것은 아니며 일정한 조건을 만족하는 타입만 저장할 수 있다.
- 예제 Dynamicvector
|
#include <iostream> #include <vector> #include <algorithm> using namespace std;
class Dynamic { private: char *ptr; public: Dynamic() { ptr = new char[1]; ptr[0] = 0; } Dynamic(const char *str) { ptr = new char[strlen(str)+1]; strcpy( ptr, str); } Dynamic(const Dynamic &other) { ptr = new char[strlen(other.ptr)+1]; strcpy(ptr, other.ptr); } Dynamic &operator=(const Dynamic &other) { if( this != &other ) { delete[] ptr; ptr = new char[strlen(other.ptr)+1]; strcpy(ptr, other.ptr); } return *this; } int operator ==(const Dynamic &other) const { return strcmp( ptr, other.ptr ); } int operator <(const Dynamic &other) const { return strcmp( ptr, other.ptr ); } virtual ~Dynamic() { delete[] ptr; } virtual void outDynamic() { cout << ptr << ' '; } };
template<typename C> void dump( const char *desc, C c ) { cout.width(12); cout << left << desc << "==> "; for( unsigned i = 0 ; i < c.size() ; i++ ) { c[i].outDynamic(); } cout << endl; }
void main() { vector<Dynamic> vt; Dynamic a("dog"); Dynamic b("cow"); vt.push_back(a); vt.push_back(b); dump("2개 요소", vt); } |
push_back ㅎ마수로 객체를 벡터 끝에 추가할 때 복사가 발생하며 이 때 객체의 복사 생성자가 호출된다. 만약 Dynamic이 복사 생성자를 정의하지 않으면 이 예제는 다운된다.
- 예제 Dynamicptrvector
|
#include <iostream> #include <vector> #include <algorithm> using namespace std;
class Dynamic { friend struct DynCompare; friend struct DynFind; private: char *ptr; public: Dynamic() { ptr = new char[1]; ptr[0] = 0; } Dynamic(const char *str) { ptr = new char[strlen(str)+1]; strcpy( ptr, str); } Dynamic(const Dynamic &other) { ptr = new char[strlen(other.ptr)+1]; strcpy(ptr, other.ptr); } Dynamic &operator=(const Dynamic &other) { if( this != &other ) { delete[] ptr; ptr = new char[strlen(other.ptr)+1]; strcpy(ptr, other.ptr); } return *this; } int operator ==(const Dynamic &other) const { return strcmp( ptr, other.ptr ); } int operator <(const Dynamic &other) const { return strcmp( ptr, other.ptr ); } virtual ~Dynamic() { delete[] ptr; } virtual void outDynamic() { cout << ptr << ' '; } };
template<typename C> void dump( const char *desc, C c ) { cout.width(12); cout << left << desc << "==> "; for( unsigned i = 0 ; i < c.size() ; i++ ) { c[i]->outDynamic(); } cout << endl; } struct DynCompare { bool operator()(Dynamic *a, Dynamic *b) const { return strcmp(a->ptr, b->ptr) < 0; } };
struct DynFind { bool operator()(Dynamic *c) const { return strcmp(c->ptr, "cat") == 0 ; } };
void main() { vector<Dynamic*> vt; vt.push_back(new Dynamic("dog")); vt.push_back(new Dynamic("cow")); dump("요소 2개", vt);
Dynamic d("cat"); puts(find_if(vt.begin(), vt.end(), DynFind()) == vt.end() ? "없다" : "있다"); sort(vt.begin(), vt.end(), DynCompare()); dump("정렬 후", vt);
vector<Dynamic*>::iterator it;
for( it = vt.begin() ; it != vt.end() ; it++ ) { delete *it; } } |
검색과 정렬 모두 조건자 버전의 함수를 사용했다. 예제의 DynCompare, DynFind는 전달된 포인터로부터 ptr을 읽어 이 포인터가 가리키는 곳의 내용을 비교하므로 객체의 포인터가 아니라 포인터가 가리키는 실체를 대상으로 검색 및 정렬하게 된다. 이론적으로 벡터에 포인터를 저장하는 것이 가능하기는 하지만 보다시피 여러가지로 신경써야 할 것들이 많고 불편하기 때문에 벡터에는 통상 값을 저장하는 것이 권장된다.
40.1.5 vector<bool>
벡터는 임의 타입의 요소를 저장할 수 있으므로 bool 타입의 진위형 값도 저장할 수 있다. bool은 크기가 1바이트이지만 true 또는 false를 기억ㅎ라는데 단지 1비트만 사용되므로 7비트가 낭비되는 문제가 있다.
그래서 벡터는 bool형에 대해서 특수화 되어 있으며 하나의 값을 저장하는데 비트 하나만 사용한다. 마치 C구조체의 비트필드와 유사하다.
vector<BOOL>도 가능한데 BOOL은 정수와 크기가 같으므로 무려 32배나 더 크다.
- 예제 vectorbool
|
#include <iostream> #include <vector> using namespace std;
void main() { vector<bool> vb(32);
cout << vb[10] << endl; vb[10] = true; cout << vb[10] << endl;
vector<bool>::reference r = vb[10]; cout << r << endl; r.flip(); cout << r << endl;
vector<bool>::iterator it; for( it = vb.begin() ; it != vb.end() ; it++ ) { cout << *it ; } } |
vector<bool>에 포함된 reference타입은 벡터 내의 한 요소, 그러니까 한 비트를 표현하는 클래스이다. 이 외에 비트를 뒤집는 flip, bool형으로 변환하는 캐스트 연산자, 비트를 반전하는 ~연산자, 대입 연산자 등이 정의되어 있다. vector<bool>은 표준에 포함되어 있기는 하지만 몇 가지 문제가 있고 컴파일러마다 지원 범위가 달라 가급적 사용을 자재한느 것이 좋다.
40.1.6 벡터의 활용
벡터는 크기가 자동으로 관리된다는 점에서 동적 배열과 유사하며 템플릿에 의해 요소 타입을 마음대로 선택할 수 있다는 점에서 TDArray 클래스와도 유사하다. 벡터는 표준인데다 성능도 우수하고 신뢰성이 있어 실제 프로젝트에서 활용해도 좋을 만큼 훌륭한다.
- 예제 Dynvector
|
#include <iostream> #include <vector> using namespace std;
template<typename C> void dump(const char*desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { vector<int> vi; dump("최초", vi); for( int i = 1 ; i <= 8 ; i++ ) { vi.push_back(i); } dump("8개 추가", vi); vi.insert(vi.begin()+3, 10); dump("10 삽입", vi); vi.insert(vi.begin()+3, 11); dump("11 삽입", vi); vi.insert(vi.begin()+3, 12); dump("10 삽입", vi); vi.erase(vi.begin()+7); dump("요소 7 삭제",vi); } |
같은 타입의 자료 집합을 관리해야 한다면 대부분의 경우 벡터가 탁월한 선택이 될 것이다. 그렇다고 해서 벡터가 반드시 같은 타입만 다룰 수 있는 것은 아니며 호환되는 타입의 집합을 다룰 수도 있다. 그래픽 오브젝트의 집합을 다루고 싶다면 최상위 클래스의 포인터를 저장하는 벡터를 선언하면 된다. 상속 계층의 클래스끼리는 타입 호환성이 있으므로 같은 타입으로 봐도 무방하다.
- 예제 GraphicObjectVector
|
#include <iostream> #include <algorithm> #include <vector> using namespace std;
class graphic { public: virtual void draw() { puts("그래픽 오브젝트"); } };
class line : public graphic { public: virtual void draw() { puts("선"); } };
class circle : public graphic { virtual void draw() { puts("원"); } };
class rect : public graphic { virtual void draw() { puts("사각형"); } };
void del(graphic *g) { delete g; }
void main() { vector<graphic*> vg;
vg.push_back(new graphic()); vg.push_back(new rect()); vg.push_back(new circle()); vg.push_back(new line());
vector<graphic*>::iterator it;
for( it = vg.begin() ; it != vg.end() ; it++ ) { (*it)->draw(); }
for_each(vg.begin(), vg.end(), del); } |
vector<graphic*>타입은 graphic으로부터 파생된 클래스의 집합을 다룰 수 있는 벡터이다. 크기에 무관하고 삽입, 삭제가 자유롭고 STL알고리즘의 도움을 받을 수도 있다. 단 벡터는 포인터만 관리할 뿐 포인터가 가리키는 객체까지 관리하지 않으므로 벡터가 파괴되기 전에 객체들을 직접 삭제해야 한다.
40.2 리스트와 데크
40.2.1 리스트
리스트(list) 컨테이너는 이중 연결 리스트를 템플릿으로 추상화한 버전이다. 동일한 자료의 집합을 관리한다는 용도에서는 벡터와 같고 실제로 서로 대체 가능하다.
다음은 벡터와 리스트 컨테이너의 주요 차이점인데 내부 구조가 다름으로 인해 성능이나 제공하는 기능 목록에서 약간의 차이가 있다.
- 가장 큰 차이점은 반복자의 레벨인데 벡터는 요소들이 인접해 있으므로 임의 접근이 가능하지만 리스트는 노드들이 흩어져 있으므로 양방향으로만 이동할 수 있을 뿐이다. 반복자가 +n 연산을 지원하지 않으므로 순차값으로 요소를 액세스하는 [ ]연산자를 지원하지 않으며 at함수도 지원하지 않는다. 임의 위치를 상수 시간에 액세스 할 수 없으면 반드시 순회를 해야만 원하는 요소를 찾을 수 있다. 임의 접근 반복자를 요구하는 sort나 binary_search 알고리즘은 리스트에는 사용할 수 없다.
- 각 요소들이 노드로 할당되어 링크에 의해 논리적으로 연결되어 있으므로 링크만 조작해서 삽입, 삭제를 수행할 수 있다. 요소들이 인접하지 않아도 상관없어 삽입, 삭제시에 메모리 이동을 할 필요가 없으며 위치에 상관없이 상수 시간 내에 삽입, 삭제를 할 수 있다. 이에 비해 벡터는 중간에서 삽입, 삭제할 때 요소들을 밀고 당겨야 하므로 속도가 다소 느리다. 속도 희생 없이 언제든지 크기를 늘리거나 줄일 수 있으므로 처음부터 미리 크기를 결정할 필요가 없으며 capacity, reserve도 불필요하다.
- 링크 구조로 인해 메모리 소모량은 벡터보다 훨씬 더 많다. 요소를 저장하는 노드는 무조건 동적 할당해야 하며 요소간의 순서를 기억하기 위한 링크도 별도의 메모리를 소모한다. 게다가 삽입, 삭제시마다 노드를 할당, 해제 하는 과정을 계속 반복하므로 메모리 단편화도 심해 시스템의 메모리 관리 능력에도 좋지 않은 영향을 미친다.
- 삽입 삭제에 의해 요소들이 물리적인 위치가 바뀌지 않으므로 반복자가 무효화되지 않는다. 반복자가 무효화되는 유일한 경우는 반복자가 가리키는 대상을 삭제 했을 때 뿐인데 요소가 완전히 사라졌으므로 이때는 어쩔 수 없다.
이 둘의 차이점을 요약하자면 벡터는 읽기에 강하고 리스트는 쓰기에 강한 컨테이너라고 정리할 수 있다. 읽기 속도가 중요하면 벡터를 선택하는 것이 좋고 삽입 삭제가 빈번하다면 리스트가 더 나은 선택이다.
리스트의 생성자는 4개가 제공되는데 벡터의 생성자와 원혀잉 동일하다.
explicit list();
explicit list(size_type n, const T& v = T());
list(const list& x);
list(const_iterator first, const_iterator last);
- 예제 listcon
|
#include <iostream> #include <list> using namespace std;
void main() { list<int> li; list<int>::iterator it;
li.push_back(8); li.push_back(9); li.push_front(2); li.push_front(1);
for( it = li.begin() ; it != li.end() ; it++ ) { printf("%d\n", *it); } } |
40.2.2 삽입, 삭제
삽입, 삭제 함수도 벡터와 동일하다
iterator insert(iterator it, const T& x = T());
void insert(iterator it, size_type n, cnost T& x);
void insert(iterator it, const_iterator first, const_iterator last);
iterator erase(iterator it);
iterator erase(iterator first, iterator last);
처리 속도는 벡터보다 빠른데 위치와 요소 개수에 상관없이 상수 시간 내에 삽입, 삭제 된다. 반복자가 무효화되지 않는 장점도 있다. 단, 삭제되는 노드의 반복자만 예외적으로 무효화된다.
- 예제 listinsert
|
#include <iostream> #include <list> using namespace std;
template<typename C> void dump(const char*desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { const char *str = "abcdefghij"; list<char> lc(&str[0], &str[10]); list<char>::iterator it;
dump("최초", lc); it = lc.begin(); it++; it++; it++; it++; it++; lc.insert(it, 'z'); dump("z 삽입", lc); it = lc.end(); it--; it--; it--; lc.erase(it); dump("h삭제", lc); } |
remove는 삭제할 값을 바로 지정하고 remove_if는 조건자에 맞는 요소만 삭제한다. 값을 검색한 후 삭제하므로 find와 erase를 순서대로 수행한다고 생각하면 된다.
- 예제 listremove
|
#include <iostream> #include <list> using namespace std;
template<typename C> void dump(const char*desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { const char *str = "double linked list class"; list<char> lc(&str[0], &str[strlen(str)]);
dump("최초", lc); lc.remove('i'); dump("i삭제", lc); } |
조건자 버전을 사용하면 일정한 조건을 만족하는 요소만 골라 삭제할 수도 있다.
40.2.3 링크의 재배치
리스트의 노드를 연결하는 링크는 포인터이므로 조작할 수 있는 여지가 아주 많다. 다른 컨테이너에서는 요소를 직접 이동해야 하는 작업도 리스트는 링크만 재배치하여 아주 간단하게 빠른 속도로 수행할 수 있다.
void swap(list& Right);
void reverse();
void merge(list& Right);
이 함수들은 모두 전역 알고리즘 함수로도 제공된다. 리스트가 똑같은 이름의 멤버 함수를 제공하는 이유는 링크 재배치의 장점을 활용하면 일반적인 알고리즘보다 훨씬 더 빠르게 동작하기 때문이다. 예를 들어 리스트끼리 교환하는 swap함수는 실제로 요소를 교환할 필요 없이 리스트끼리 head, tail정보만 바꾸만 간단하게 구현할 수 있다.
reverse도 요소들을 거꾸로 재배치하여 일일이 옮길 필요없이 next, prev 링크를 반대로 바꾸기만 하면 되고 리스트끼리 병합하는 merge도 마찬가지로 링크를 조작하여 한쪽 리스트를 다른 쪽의 끝과 연결하기만 하면 된다.
링크를 조작하는 가장 멋지고도 실용적인 함수는 splice이다. 두 개의 리스트를 서로 잇거나 한쪽 요소들을 뽑아서 다른쪽으로 이동시킨다.
void splice(iterator it, list& x);
void splice(iterator it, list& x, iterator first);
void splice(iterator it, list& x, iterator first, iterator last);
첫 번째 원형은 it 위치에 x리스트의 모든 요소들을 이동시킨다.
두 번째 원형은 x의 first위치에 있는 요소 하나만 it 위치로 이동시킨다.
세 번째 원형은 반복자 구간을 지정하여 일정 범위의 요소를 한꺼번에 이동시킨다
- 예제 splice
|
#include <iostream> #include <list> using namespace std;
template<typename C> void dump(const char*desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { const char *alpha = "abcdefghij"; const char *num = "12345"; list<char> la(&alpha[0], &alpha[10]); list<char> ln(&num[0], &num[5]); list<char>::iterator ita, it1, it2;
dump("알파벳", la); dump("숫자", ln);
ita = la.begin(); ita++; ita++; it1 = ln.begin(); it1++; it1++; it2 = ln.end(); it2--;
// 전체이동 // la.splice(ita, ln);
// 앞쪽 두번째만 이동 // la.splice(ita, ln, it1);
// 구간이동 la.splice(ita, ln, ln.begin(), ln.end()); dump("알파벳",la); dump("숫자",ln); } |
전체 이동시키는 splice(it, x)는 전체 구간을 이동하는 splice(it, x.begin(), x.end())와 동일한 함수라고 할 수 있다. 구간을 이동할 때는 구간의 시작과 끝 주변의 링크만을 조작하면 된다.
40.2.4 정렬
리스트는 임의 접근 반복자를 제공하지 않으므로 정ㄹ려 속도가 대단히 느린 편이다. 그래서 sort멤버 함수를 사용한다.
void sort();
void sort(BinPred op);
인수를 받지 않는 sort멤버 함수는 <연산자로 노드를 비교하여 정렬하며 조건자를 받아들이는 sort멤버 함수는 조건자의 비교 결과대로 정렬한다.
다음 멤버 함수는 연속된 중복 요소를 제거하는데 같은 이름의 전역 함수도 있지만 멤버 함수는 리스트의 링크 구조를 활용하도록 구현되어 있다.
void unique();
void unique(UniPred op);
- 예제 listsort
|
#include <iostream> #include <list> using namespace std;
template<typename C> void dump(const char*desc, C c) { cout.width(12); cout << left << desc << "==> "; copy(c.begin(), c.end(), ostream_iterator<typename C::value_type>(cout, " ")); cout << endl; }
void main() { const char str[] = "stllistcontainer"; list<char> li( &str[0], &str[sizeof(str)-1]); dump("원본", li); li.sort(); dump("sort 후", li); li.unique(); dump("unique 후", li); } |
- 예제 sortspeed
|
#include <iostream> #include <vector> #include <list> #include <algorithm> #include <ctime> using namespace std;
const unsigned num = 100000;
void main() { srand(time(NULL)); vector<int> vi; list<int> li; int i; clock_t start;
for( i = 0 ; i < num ; i++ ) { vi.push_back(rand()%100+1); li.push_back(rand()%100+1); }
cout << "키를 누르면 벡털르 정렬합니다."<< endl; getchar(); start = clock(); sort(vi.begin(), vi.end()); cout << "벡터 정렬 완료. 소요시간 = " << clock()-start << endl;
cout << "키를 누르면 리스트를 정렬합니다" << endl; getchar(); start = clock(); li.sort(); cout << "리스트 정렬 완료. 소요시간 = " << clock()-start << endl; } |
개발툴과 빌드 모드에 따라서는 속도 차이가 많이 벌어지는데 단, 디버그 모드에서는 반복자의 유효성을 점검하는 코드로 인해 공정한 비교가 되지 않으므로 릴리즈 모드에서 실행해야 한다.
40.2.5 데크
데크(Deque)는 양쪽 끝이 있는 큐이며 양 끝에서 자료를 삽입, 삭제할 수 있다. 컴파일러에 따라 데크의 구현 방식이 다르겠지만 주로 메모리 블록을 할당하여 연결해 놓고 양쪽 끝으로 추가 할당해 나가는 방식으로 구현된다. 벡터와 비슷한 특성을 가지는데 양쪽에 끝이 있으므로 앞쪽에서도 삽입, 삭제가 빠르다.
앞쪽에서도 자료의 첨삭이 가능하므로 벡터에 비해 push_front, pop_front 함수가 추가로 제공된다. 앞쪽에서의 삽입, 삭제가 벡터보다 훨씬 빠르다는 이점이 있는 대신 나머지 연산들은 벡터보다 일반적으로 느리다.
- 예제 deque
|
#include <iostream> #include <deque> using namespace std;
void main() { deque<int> dq; dq.push_back(8); dq.push_back(9); dq.push_front(2); dq.push_front(1); for( unsigned i = 0 ; i < dq.size() ; i++ ) { cout << dq[i] ; } } |
'책정리 > 혼자 연구하는 C,C++ 2' 카테고리의 다른 글
| 42장 STL 알고리즘 (0) | 2015.03.17 |
|---|---|
| 41장 연관 컨테이너 (0) | 2015.03.17 |
| 39장 반복자 (0) | 2015.03.14 |
| 38장 함수 객체 (0) | 2015.03.13 |
| 37장 STL 개요 (0) | 2015.03.12 |