STL #1 Vector

 

STL

Standard Template Library

 

 

벡터의 등장 배경

-기본자료구조인 배열은 크기가 고정이고 한번 만들어진 순간 모든게 결정된다. 넣고싶은 원소가 많아져도 크기를 중간에 늘릴 수 없어서 새로 할당하고 다시 값을 복사해야한다.

 

 

-동적배열

using namespace std;

#include <vector>

 

vector<int> v;

v.push_back(1);

v.push_back(2);

v.push_back(3);

const int size = v.size();

for(int i=0; i<size; i++)

 cout<<v[i]<<endl;

 

vector의 동작원리

❓배열은 어떻게 유동적으로 사용가능한가?

❓capacity는 얼마나 크게 잡아야하나?

❓기존의 데이터는 어떻게 처리할지?

 

1)메모리를 여유분을 두고 할당한다. (size보다 큰 capacity)

-capacity는 얼마나 크게 잡아야하나?

size:실제 사용 데이터 개수

capacity:여유분을 포함한 용량 개수

 

#include <vector>
using namespace std;

vector<int> v;
for(int i=0; i<1000; i++)
{
    v.push_back(100);
    cout<<v.size()<<" "<<v.capacity()<<endl; 
}
//1 2 3 4 6 6 9 9 9 13 13 13 13 19, ... ,28

대략 이전 capacity에 따라서 1.5배 정도 늘린다는것을 확인했다. 컴파일러에 따라서 규칙이 다르다.

 

2)여유분까지 꽉 찼으면 메모리를 증설한다. (capacity를 알아서 늘린다.)

동적배열 할당하는 것으로 만들어보면

int* arr = new int[100];

delete arr;

arr = new int[1000];

이런원리!

추가영역을 뒤에 이어서 할당하는 방법도 있지만 동적배열도 배열이므로 연속적인 메모리가 할당되어야한다는 조건이 붙는다. 뒤에 추가를 원하는 크기로 할당하려하면 이미 쓰고있는 메모리도 있을 수 있으므로 아예 다른 지역에다가 더 원하는 큰 영역으로 이사한다. 그런데 원래있던 데이터가 크면 이사하는 비용이 크므로 capacity를 미리 크게 가지고 있는게 중요하다. 어떻게 capacity를 정할것인가 정책도 그렇고.

 

벡터를 사용하기 전에 필요한 양을 한다면 capacity의 윤곽을 잡아줄 수 있다.

v.reserve(1000); //이 때 size는 늘어나지 않는다.

 

size를 조절하는 여러가지 방법

v.resize(1000); //이 때 capacity도 함께 1000으로 늘어난다.

그런데 이후에 v.push_back()하면 1001부터 들어간다.

이미 할당받은 영역이므로 v[i]로 접근해 값을 넣어야한다.

 

💥왜 vector를 사용할 때 reserve로 초반에 여유분을 잡아주냐면 capacity가 변할때 마다 기존에 있던 데이터복사가 이루어져 비용이 드므로 처음부터 reserve를 통해 잡아주면 복사하는 부분을 생략해 효율적이다.

 

그런데 언어마다 다르지만 C++에선 한 번 capacity가 커진 후에 값을 지워서 size가 작아진다해도 다시 줄어들지 않는다. 

v.clear(); //값을 다 날려벌이는 함수.

cout<<v.size()<<" "<<v.capacity();

 

만약 capacity()를 줄이고 싶으면 swap을 통해 가능하다.

vector<int>().swap(v);

swap을 통해 이름없는 벡터가 v의 정보를 가지게 되고 v가 앞의 벡터의 정보를 갖게된다. 또 임시벡터여서 다음 행에서 바로 사라지게된다. 

cout<<v.size()<<" "<<v.capacity(); //0 0

그러나 실제로 capacity가 늘어난 경우는 후에 쓰일 가능성이 있으므로 굳이 사용하지는 않는다.

 

이밖에도 자주 활용되는

v.pop_back(); //만약 push_back했던것의 반대로 뒤에서부터 빼내고 싶으면 

v.back(); //뒤의 값 보고 싶다면

v.front(); //앞의 값을 보고 싶다면

vector<int> v(100); //선언 후 100으로 resize효과

vector<int> v1(100,0);//10개의 크기를 0으로 초기화한다. 

vector<int> v2 = v; //v를 복사하는 효과

 

 

반복자 iterator

 

컨테이너( 데이터를 저장하는 객체, 자료구조)가 가지고 있는 반복자(iterator)는 포인터와 유사한 개념. 컨테이너의 원소(데이터)를 가리키고 다음/이전 원소로 이동가능하게 한다.

포인터와 반복자의 차이는?

vector<int> v(10);

for(vector<int>::size_type i=0 ; i<v.size() ; i++) //v.size()는 unsigned int이므로  
{
    v[i]=i;
}

// iterator vs. pointer
vector<int>::iterator it;
int* ptr;

it = v.begin();
ptr = &v[0];

cout<<(*it)<<' '<<(*ptr)<<endl; //0 0 iterator는 클래스이지만 *를 지원하게끔 연산자 오버로딩
cout<<it<<' '<<ptr<<endl; //같은 주소값을 가지고 있고, it는 ptr을 가지고 있어 랩핑한 값이다.(이외에도 벡터정보가 담겨있다.)

// 데이터 이동하는 문법 모두 지원한다.
it++;
++it;
--it;
it+=2;
ptr++;
++ptr;


vector<int>::iterator itBegin = v.begin();
vector<int>::iterator itEnd = v.end(); // 유효한 범위의 다음을 가리킨다. 쓰레기값~!

for(vector<int>::iterator iter = v.begin(); iter!=v.end(); ++iter) // vector<int>::iterator를 C++ 11부터 auto로 가능하다 
{
    cout<<(*iter)<<endl;
}

int* ptrBegin = &v[0]; // v.begin()._Ptr;
int* ptrEnd = ptrBegin+10;// v.end()._Ptr;
for(int* ptr= ptrBegin; ptr!=ptrEnd;++ptr)
{
    cout<<(*ptr)<<endl;
}

 

*for문하다가 나왔는데 ++iter와 iter++에서 ++iter가 효능이 아주조금 더 좋다고 알려져있다. 그 이유는 ++iter는 실제값을 ++연산 후 참조값으로 반환하는 반면 iter++는 임시적으로 복사한 다음에 ++하고 복사한 다음에 복사한 값을 전달하므로 쪼끔 더 오래걸릴 수 있다.

 

다를건 없지만 
iterator는 벡터 뿐만 아니라 다른 컨테이너에도 공통적으로 있는 개념이라 STL한정 같은형태이며
다른 컨테이너는 v[i]와 같은 인덱스 접근이 안 될 수도있다.

사실 포인터와 iterator를 사용하는것은 그냥 선택의 여부다.

 

// const iterator
// const pointer처럼 데이터를 수정하지 않고 read,write만 할 때 사용할수 있다.
vector<int>::const_iterator cit1=v.cbegin();
*cit=100; //불가능


// 역방향 반복자
for(vector<int>::reverse_iterator rit=v.rbegin(); it!=v.rend(); ++rit)
{
    cout<<(*rit)<<endl; // 9 8 7,...,0
}

중간/처음/끝 삽입/삭제와 임의접근

vector는 동적 배열 기반으로 되어있다.(동적으로 커지는 배열) , 원소가 하나의 메모리 블록에 연속하게 저장된다.

-데이터를 쉽게 사용하기 위해서 꼭 메모리 블록을 연속적으로 사용한다구!!

-중간 삽입 삭제는 값의 삽입하거나 삭제할 위치를 기준으로 뒤의 모든 값들이 복사가 이르어지므로 중간 삽입 삭제는 비효율적이다.👎

-처음에 값 데이터 삽입 삭제도 위와 마찬가지로 마찬가지다.👎

-희망적으로 끝에 삽입 삭제는 이동이나 복사가 없기 때문에 효율적이다.👍

그래서 v.push_back(T); v.pop_back(T); 은 있지만 v.push_front같은것은 없다~!

 

임의 접근 영어로 random access.

임의 접근하기 위해서 n번째 데이터에 접근하기 위해서 배열 문법을 이용해 v[n-1]으로 접근할 수 있다.

이것도 메모리 블록이 연속적으로 이루어져 있어서 가능한것이다.

 

그럼에도 불구하고 중간에 삽입과 삭제가 일어날 수 있다. 사용하는 방법 v.insert(). iterator를 이용한다.

vecotr<int> v(10);
//v.reserve(1000)

for(int i=0;i<(int)v.size();i++)
{
    v[i]=i;
}

vector<int>::iterator insertIt = v.insert(v.begin() + 2 , 5); // 두번째 데이터에 5를 삽입
vector<int>::iterator eraseIt = v.erase(v.begin() + 2); // 두번째 데이터 삭제
vector<int>::iterator eraseIt2 = v.erase(v.begin()+2, v.begin()+4); // 범위로 삭제하기 등

중간삽입 삭제를 위해 v.insert()와 v.erase()를 사용하는데 iterator값을 반환한다.

만약 위의 예처럼 이미 10의 capacity가 다 찬 상태에서 insert가 되면 아예 데이터가 다른곳에 저장되고 싹 날라간다.

주석을 풀고 v.reserve(1000)으로 하여 capacity를 충분히 확보한 상태에서 insert하면 삽입한 위치를 정확히 반환하고 있다(5를 가리킨다.) 또 거꾸로 erase(v.begin() +2)를 하면 앞으로 당겨지고 2를 가리키고 있다.

이 상태에서 erase를 한번 더 하면 eraseIt2는 아래와 같이 4를 가리키게 된다.

이때 뒤의 숫자들은 유효범위 밖으로 처리되어 굳이 지워지지 않고있다. 

 

그런데 만약 벡터를 쭉 스캔하면서 특정 데이터가 있으면 삭제하고 싶을때 아래와 같은 구조로 생각할수도 있다.

for(vector<int>::iterator it= v.begin();it!=v.end();++it)
{
    int data = *it;
    if(data==3) 
    {
        v.erase(it); // 크래쉬~!
        // it = v.erase(it);
    }
}

그런데 이렇게 하면 크래쉬가 나는데 it는 가리키는 값 정보 뿐만 아니라 다른 정보(속하는 벡터 정보)도 가지고 있다. v.erase(it); 하는 순간 it의 정보가 NULL이 돼서 컨테이너의 정보도 모두 날아가고 더이상 속하는 컨테이너가 없는 상태에서 유효하지 않은데++it가 불가능하기 때문이다. 따라서 딱 하나만 지우려면은 v.erase(it); 후에 break;을 하던가 계속 순회하고 싶다면 v.erase(it) 한 결과 값을 다시 it에 저장해줘야한다. 그런데 이렇게하면 지워지고 난 후 가리키고 있는 값은 체크하지 못하고 ++it되어서 넘어가므로 아래와 같이 하는게 정확하다.

for(vector<int>::iterator it= v.begin();it!=v.end();)
{
    int data = *it;
    if(data==3) 
        it = v.erase(it);
    else
        ++it;
}

 

같은 의미로 만약 for문 안에서 v.clear()를 쓸 일이 있다면 꼭 break;를 써주기로하자!~

Vector의 구현