벡터 컨테이너

타입 T를 원소를 갖는 컨테이너, Array 컨테이너와 같지만, 더 많은 원소를 수용할수 있도록 크기가 자동으로 커진다.

벡터 컨테이너 생성

1
2
3
4
5
6
std::vector<double> values;
// 원소가 하나도 없고, 원소를 위해 할당된 공간이 없는 상태.
// 첫번재 데이터를 추가할때 자동으로 할당된다.

values.reserve(20); 
// 20개까지 저장할수 있는 메모리 할당

reserve() 호출시 할당된 메모리가 증가했다면, 시작 반복자, 끝 반복자 처럼 이미 생성한 반복자들은 무효화 되므로, 반복자는 다시 생성해야된다.

컨테이너를 늘리는 과정에서 기존 원소들이 새로운 메모리 위치로 복사되거나 이동될수 있다.
동적으로 컨테이너 크기가 확장 축소가 되지만, Reallocation 비용이 너무 크다.
Capacity 확장하면서 메모리 위치가 복사되거나, 이동될때, 그만큼 복사생성후, 기존 원소들은 파괴해야된다.

벡터 컨테이너의 원소 삭제

auto iter = data.erase(std::begin(data) + 1)은 두번째 원소를 삭제하는것이고, iter는 삭제한 원소의 다음을 가르키게된다. remove() 함수는 범위에서 지정한 값과 일치하는 원소들을 제거하난데, 제거 한만큼 뒤의 인덱스를 옮겨야되는 단점으로 인해 삽입, 삭제가 빈번하면 성능이 좋지않다.

벡터 컨테이너 특징

  1. 중간에 데이터 삽입, 삭제가 용이하지않음.
  2. 랜덤 접근이 가능하다.

벡터는 언제 사용해야 효율적?

  1. 저장할 데이터 수가 가변적
  2. 중간에 데이터 삽입이나 삭제가 없다 -> 하지만 표본데이터가 적을때는 괜찮다.
  3. 저장할 데이터 갯수가 적거나 많은 경우, 빈번하게 검색하지 않는 경우
  4. 데이터 접근이 랜덤으로 이룰때

Deque 컨테이너

양쪽을 삽입 및 삭제가 가능한 컨테이너이다. 스택과 큐의 장점을 모은것이라고 봐도 된다.

벡터는 뒤에서만 삽입 삭제를 해야 성능이 좋지만 순차열의 시작이나 끝에 객체들을 효율적으로 추가하거나 삭제할수 있다는 점에서는 벡터보단 낫다.

DB의 트랜젝션 처리나 슈퍼마켓에서 계산대 열을 시뮬레이션을 할때는 deque가 좋다.

Deque 컨테이너 특징

  1. 크기가 가변적
  2. 앞과 뒤 삽입과 삭제가 좋음.
  3. 중간에 데이터 삽입, 삭제가 용이하지 않음.
  4. 랜덤 접근이 가능하다.

Deque는 언제 사용해야 효율적?

  1. 앞과 뒤에서만 삽입, 삭제를 한다.
  2. 저장할 데이터 갯수가 가변적이다.
  3. 검색을 거의 하지않는다.
  4. 데이터 접근을 랜덤하게 할때

Deque와 Vector를 비교할때, deque는 앞과 뒤에서 삽입 삭제 성능이 vector 보다 좋고, 나머지 기능은 vector보다 성능이 좋지 않다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <deque>
#include <string>
#include <iterator>
using namespace std;

int main()
{
	deque<string> names;

	cout << "Enter first name seperated by space. Enter Ctrl + Z on a new line to end:\n";
	copy(std::istream_iterator <string> {std::cin}, std::istream_iterator <string> {}, std::front_inserter(names));

	cout << "\nIn reverse order , the names you entered are: \n";
	copy(begin(names), end(names), std::ostream_iterator<string> {cout, " "});

	cout << endl;

}

List 컨테이너

벡터나 덱 컨테이너에 비교해서 순차열의 어느 위치라도 상수 시간에 원소 삽입, 삭제가 가능하고, 중간위치에도 삽입, 삭제가 빠르다는 장점이 있다.

하지만 순차열에서 특정 위치에 있는 원소에 바로 접근할수가 없다. auto iter = list.begin() + 4 같은 연산은 랜덤엑세스가 가능해야 사용가능하다.

위의 연산을 하고자한다면 그만큼 루프를 돌거나 advance() 전역 함수를 이용해서 반복자를 증가시킨다.

컨테이너 생성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
list<string> word;

// 원소 지정 생성
list<string> word{20};

// 원소 지정하고 값을 채워서 생성
list<double> values(50, 3.141592); // 만약 초기화 리스트를 사용했다면 50, 3.141592 두개의 값만 가진다.

// 리스트는 복사생성자를 가지고 있는것을 이용해서 
list<double> save_values {values};

// 시작 반복, 끝 반복의 범위를 지정해서 초기화도 가능
list<double> samples {++cbegin(values), --cend(values)};  // const 반복자
// list이기 때문에, begin과 end가 반환하는 반복자는 양방향이므로 정숫값을 더하거나, 뺄수가 없다.
// 위치를 수정하는 방법은 증가연산(++), 감소연산(--)를 사용하는것.

// 위는 2번째부터 끝에서 2번째까지 돌면서 초기화한다.

윈소 추가하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// push_back, push front 함수가 있긴하지만, 복사한다는 단점이 있다.
// emplace_back, emplace_front 함수가 있는데 RValue 참조 매개변수 버전이다.

// insert 함수 맴버를 이용해 리스트 내부에 원소를 추가할수 있다.
list<int> data(10, 55);
data.insert(++begin(data), 66); // 두번째 원소를 66으로 삽입

// data 
// 55 66 55 55 55 55 55 55 55 55 55
auto iter = begin(data);
std::advance(iter, 9); // iter을 9만큼 루프돌려서 증감.
data.insert(iter, 3, 88); // 10번째 위치에 88의 복제번을 3개 삽입한다.
// 55 66 55 55 55 55 55 55 55 88 88 88 55 55

vector<int> numbers(10 ,5);
data.insert(--(--end(data)), cbegin(numbers), cend(numbers));
// data 리스트의 끝에서 2번 뒤인 위치에서 벡터 numbers 시작부터 벡터 end까지 삽입한다.
// 55 66 55 55 55 55 55 55 55 88 88 88 5 5 5 5 5 5 5 5 5 5 55 55

// insert -> emplace 
// push_back -> emplace_back
// pusk_front -> emplace_front를 사용하자

RValue and LValue 설명

원소 제거

list.clear(), list.erase() 함수 맴버는 다른 순차열과 같이 동작한다. 결과도 같다. list.remove() 맴버는 인수와 일치하는 원소들을 제거한다.

remove_if() 함수 맴버는 단항 조건자를 사용한다. 단항 조건자는 원소 타입이나 원소 타입의 const 참조를 인수로 받고 bool 값을 반환.

1
numbers.remove_if([](int n) {return n%2 == 0;}); //짝수 제거, 함수객체도 사용가능하다.

원소 정렬

algorithm 헤더에 있는 sort 함수 템플릿을 쓰려면 랜덤엑세스 반복자가 필요하다. 리스트 컨테이너에는 랜덤 엑세스 반복자가 없고, 양방향 반복자가 있으므로, 리스트에 있는 원소들에게 sort() 알고리즘을 적용할수 없다.

하지만 list 컨테이너 내부에 함수가 별도로 제공되고 있다. list의 컨테이너의 sort() 함수는 이항 조건을 인수로 받는다.

예를 들면 names.sort(std::greator<string>()) functional 헤더에 정의된 greator를 사용하였다. 내림차순

1
2
3
4
5
6
7
8
9
10
11
12
13
class my_greater
{
  public:
  	bool operator()(const string& s1, const string& s2) // 이니셜이 같은 문자열을 길이로 정렬
    {
        if(s1[0] == s2[0])
            return s1.length() > s2.length(); // 이니셜이 같다면 내림차순
        
        return s1 > s2;
    }
}

names.sort(my_greater()); // 람다 함수도 가능하다.