STL(Standard Template Library)
프로그래밍할 때 필요한 자료구조/알고리즘들을
템플릿으로 제공하는 라이브러리
컨테이너(Container) : 데이터를 저장하는 객체(자료구조 Data Structure)
- vector(동적 배열)
- vector의 동작원리 (size / capacity)
- 중간 삽입/삭제
- 처음/끝 삽입/삭제
- 임의 접근
- 배열
- 단점 : 크기가 유동적이지 못함
동적배열이란
일단 사용하기위해서 #include <vector> 가필요
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
const int size = v.size();
for (int i = 0; i < size; i++)
{
cout << v[i] << endl;
}
return 0;
}
이런식으로 사용 할 수 있음, 이때 v.을 찍으면 여러가지 사용하는게 나옴
매우매우 중요한 개념-> 어떤 마법을 부렸길래 배열을 '유동적으로' 사용한것인가?
- (여유분을 두고) 메모리를 할당한다.
- 여유분까지 꽉 찼으면, 메모리를 증설한다.
Q1. 여유분은 얼만큼이 적당할까?
Q2. 증설을 얼만큼 해야할까?
Q3. 기존의 데이터를 어떻게 처리할까?
size(실제 사용 데이터 개수) 1 2 3 4 5 ….
capacity(여유분을 포함한 총 용량 개수) 1 2 3 4 6 9 13 19 28 42 63..
ㄴ 약 1.5배씩 증가(컴파일러에 따라 다름) 내용이 줄더라도 용량이 줄지않음
이렇게 증가가 아니라 처음부터 용량 지정할 수 도 있음
v.reserve(1000); //크기를 그냥 처음부터 1000으로 지정
capacity가 부족할경우 1.5배씩 복사해주는데 미리 여유분을 지정해두면 복사하는것이 생략되기때문에 효율적임
실제 사용 크기를 처음부터 지정할수도 있음
v.resize(1000); // 사용량 1000
v.clear(); // v vector안에 내용을 지움 지우더라도 capacity 가 줄어들지 않음
그렇다면 내용을 지웠을때 capacity도 줄이려면?
v.clear();
vector<int>().swap(v);
swap을 통해서 빈공간과 교체해줘 없애버림
v.pop_back(); //마지막에 있는데이터 꺼내기
v.back(); // 마지막에 있는 데이터 꺼내기
v.front()//맨 앞에 있는 데이터 꺼내기
vector<int> v(1000); // 생성자에서 크기 설정 가능
vector<int> v(1000, 0); // 특정 초기값들을 0으로 설정
vector<int> v2 = v; // 복사도 가능
반복자(Iterator) : 포인터와 유사한 개념. 컨테이너의 원소(데이터)를 가리키고, 다음, 이전 원소로 이동가능
int main()
{
vector<int> v(10);
for (int i = 0; i < static_cast<unsigned int>(v.size()); i++)
{
v[i] = i;
}
vector<int>::iterator it; //벡터의 데이터를 가리킴(포인터는 주인이없지만 iterator는 vector라는 주인이 있음)
int* ptr; //포인터와 같이 예시를 들것임
it = v.begin();
ptr = &v[0];
cout << (*it) << endl; // 데이터에 접근하는 방식은 포인터와 비슷하다
cout << *ptr << endl;
it++; //이렇게 포인터처럼 다음주소로 이동 가능
++it;
it--;
--it;
it += 2;
it = it - 2;
ptr++;
++ptr;
ptr--;
--ptr;
ptr += 2;
ptr = ptr - 2;
vector<int>::iterator itBegin = v.begin();
vector<int>::iterator itEnd = v.end(); //끝을 판별할때 사용
return 0;
}
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
cout << *it << endl;
}
이런식으로 for문을 돌릴수도 있음, ++it 를 사용하는게 아주조금이나마 성능이 좋음(내부를 보면 참조형태로 리턴하기 때문)
포인터로 해보자면
int* ptrBegin = &v[0]; // v.begin()._Ptr;
int* ptrEnd = ptrBegin + 10; // v.end()._Ptr;
for (int* ptr = ptrBegin; ptr != ptrEnd; ++ptr)
{
cout << *ptr << endl;
}
이렇게 할 수 있음
itorator가 더 복잡해보이는데?
- iterator는 vector뿐 아니라, 다른 컨테이너에도 공통적으로 있는 개념
- 다른 컨테이너는 v[i]와 같은 인덱스 접근이 안 될 수도 있음
vector<int>::const_iterator cit1 = v.cbegin(); // 수정하지 않고 읽기만 할 경우
//*cit1 = 100;//불가능
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) // ++을 할때마다 반대로
{
cout << *it << endl;
}
그런데 const_iterator나 reverse_iterator는 많이 사용되지는 않음
댓글