📌 STL??

Standard Template Library의 약자이다. STL 라이브러리는 다음과 같은 3개의 라이브러리를 말합니다.

• 임의의 타입 객체를 보관할 수 있는 container

• 컨테이너에 보관된 원소에 접근할 수 있는 반복자 iterator

• 반복자들을 가지고 일련의 작업을 수행하는 알고리즘 algorithm

우리가 택배 기사가 되어서 택배를 택배함에 넣는다고 생각해봅시다. 택배를 보관하고 있는 각각의 택배함은 'container'가 될 것이고, 자신이 주문한 택배를 찾는 것은 'iterator', 그리고 이 편지들을 날짜에 맞춰 편지함에 넣는 일을 하는 것은 'algoritm'이 수행한다고 비유적으로 생각하면 됩니다.

특히나 iterator는 포인터와 매우 유사한데
using std::vector<int>::iterator it = myVector.begin();
포인터가 메모리 주소에 접근할 때 사용한다고 하면, 이터레이터는 컨테이너 스트럭쳐에 접근할 때 사용한다.
포인터의 연산을 사용해서 컨테이너의 타입에 맞게 재정의. 포인터랑 비슷하지만 커버하는 범위가 다르다. 포인터가 보다 더 구체적으로 사용되는 것이다.

STL Container

데이터 스트럭쳐를 컨테이너 클래스라고 한다.

STL Container 에는 크게 두가지 종류가 있다
객체를 순차적으로 보관하는 Sequence Container
키를 바탕으로 대응값을 찾아주는 associative Container

Sequence Container에는 vector, list, deque가 있다.

vector: 확장 가능한 배열을 말한다. 배열처럼 크기를 선언하여 사용할 수도 있지만, vector<int> v(10); <-- 10개의 element를 0으로 초기화
동적으로 런타임에 사이즈가 바뀌는 배열을 말한다.

list: 이중 연결 리스트. 이전과 이후에 다 연결되어 있다. 각 노드가 다음 노드에 대한 포인터만 갖고 있는 것이 아닌 이전 노드에 대한 포인터도 가지고 있다.

deque: 덱은 벡터와 비슷하게 시간복잡도 O(1)으로 임의의 원소의 위치에 접근할 수 있으며, 맨 뒤에 원소를 추가/제거하는 작업도 O(1)으로 가능하다. 벡터와 달리 맨 앞에 원소를 추가/제거하는 작업도 O(1)으로 가능하다.임의의 위치에 있는 원소를 제거/추가 하는 작업은 벡터와 마찬가지로 O(n) 으로 수행 가능하다. 뿐만 아니라 그 속도도 벡터 보다 더 빠르다.

📂 vector

[]는 값을 읽을 때 사용한다.
capacity() 는 메모리에 할당된 요소 수
size() 초기화 된 요소 수
reserve(a) 는 미리 메모리를 a만큼 할당 받음
resize(a) 는 size를 a만큼 바꿈(범위 밖의 원소는 Lost)

#include <iostream>
#include <vector>
#include <string>



template <typename T>
void printVectorInfo(const std::vector<T>& vec) {
    std::cout << " 크기: " << vec.size() << std::endl;
    std::cout << " 용량: " << vec.capacity() << std::endl;
}


int main(){
  std::vector<int> v;
  v.push_back(10);
  v.push_back(20);
  v.push_back(40);
  v.push_back(80);

 std::cout << v.size() << std::endl;
 std::cout << "============================== v.size() " << std::endl;
 std::vector<std::string> vec(10);
 printVectorInfo(vec);
 std::cout << "============================== vec.size(), vec.capacity() " << std::endl;

 std::vector<int> t;
 t.reserve(32); 
 printVectorInfo(t);
 std::cout << "============================== reserve " << std::endl;

 t.reserve(t.size()+ 10);
 printVectorInfo(t);
 std::cout << "============================== reserve 연산 " << std::endl;

 t.resize(24);
 printVectorInfo(t);
 std::cout << "============================== resize " << std::endl;


  for(std::vector<int>::size_type i = 0; i < v.size(); i++){
    std::cout << "v 의"  << i + 1 << "번 째 원소" << v[i] << std::endl;
  }
  

  return 0;
}

코드를 실행해보면

4
============================== v.size()
크기: 10
용량: 10
============================== vec.size(), vec.capacity()
크기: 0
용량: 32
============================== reserve
크기: 0
용량: 32
============================== reserve 연산
크기: 24
용량: 32
============================== resize
v 의1번 째 원소10
v 의2번 째 원소20
v 의3번 째 원소40
v 의4번 째 원소80

템플릿을 통하여, 타입에 따라 벡터의 크기와 용량을 출력하는 printVectorInfo 함수를 만들어서 최적화를 하였고, 각 함수들을 실행해보며 크기와 용량이 어떻게 변하는지 확인하였다. t.size()는 아무 원소도 초기화 되어있지 않아 0이기 떄문에, reserve 내의 연산에서 아무런 영향이 없으며, 할당된 메모리가 파괴되는 형식으로 줄어들지는 않는 것을 확인하였다.

그리고 resize()를 하게 되면, 크기가 출력이 가능해지는데 우리는 초기화를 직접 한 적이 없다. 이상하다!! 초기화는 우리가 직접 실행할 때만 되는 건 줄 알았지만 놀랍게도 v[2]와 같은 원소에 접근하게 되면

0

이 출력된다. resize()는 초기화도 해줌을 알 수 있었다. 만약 새로운 크기가 현재 크기보다 크다면, 추가된 부분은 기본값으로 초기화 된다. 신기하다

정리해보면

• 임의의 원소 위치 접근 ([], at) : O(1)

• 맨 뒤의 원소 추가 및 제거 (push_back / pop_back): armonized O(1); 평균적으로 O(1)이지만 최악의 경우 O(n)

• 임의의 위치 원소 추가 및 제거 (insert, erase): O(n)

이제 iterator도 사용해보자

#include <iostream>
#include <vector>
#include <string>



template <typename T>
void printVectorInfo(const std::vector<T>& vec) {
    std::cout << " 크기: " << vec.size() << std::endl;
    std::cout << " 용량: " << vec.capacity() << std::endl;
}


int main(){
  std::vector<int> v;
  v.push_back(10);
  v.push_back(20);
  v.push_back(40);
  v.push_back(80);


  std::vector<int>::iterator it1 = v.begin();
  std::vector<int>::iterator it2 = v.end();
  std::cout << "vector의 begin 원소 "<< *it1 << std:: endl << "vector의 end 원소 " << *it2 << std::endl << "vector의 진짜 end 원소 " << *--it2 << std::endl;
  
  std::cout << "vector back 원소 " << v.back() << std::endl;
  
  
  for(std::vector<int>::iterator it = v.begin(); it != v.end(); it++){
    std::cout << "vector의 요소" << *it << std::endl;
  }
  
  return 0;
}

이 코드를 실행해보면 출력은

vector의 begin 원소 10
vector의 end 원소 0
vector의 진짜 end 원소 80
vector의 back 원소 80
vector의 요소10
vector의 요소20
vector의 요소40
vector의 요소80

보는 것과 같이 end()를 반환하게 되면, 끝의 주소값 보다 한 칸 뒤에 있는 element의 위치를 반환해주기 때문에, 실제 end의 원소값을 알고 싶으면 연산자를 활용하여 *--it2처럼 사용해서 한 칸 앞으로 밀어야 한다.

만약 이렇게 접근하지 않고 싶다면, 그냥 back()을 통하여 접근할 수 있다.
v.back() == *(--v.end()) 로 생각하면 편할 것이다.

insert and earse

#include <iostream>
#include <vector>
#include <string>



template <typename T>
void printVectorInfo(const std::vector<T>& vec) {
    std::cout << " 크기: " << vec.size() << std::endl;
    std::cout << " 용량: " << vec.capacity() << std::endl;
}

template <typename T>
void print_vector(std::vector<T>& vec){
  for(typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end(); itr++){
    std::cout << *itr << std::endl;
  }
  
}


int main(){
  std::vector<int> v;
  v.push_back(10);
  v.push_back(20);
  v.push_back(40);
  v.push_back(80);

  std::cout << " 처음 벡터 상태 " << std::endl;
  print_vector(v);
  std::cout << " ============================== " << std::endl;

  v.insert(v.begin() + 1, 15);
  print_vector(v);
  std::cout << " ============================== " << std::endl;

  v.erase(v.begin() + 2);
  print_vector(v);

  return 0;
}

출력해보면....

처음 벡터 상태
10
20
40
80
==============================
insert 하고 난 후 상태
10
15
20
40
80
==============================
earse 하고 난 후 상태
10
15
40
80

로 출력된다.

erase나 insert를 iterator로 사용하게 될 경우 주의할 점이 있는데, iterator로 해당 작업을 수행하게 되면, itr이라는 반복자는 유효한 반복자가 아니게 되고, itr != end_itr 영원히 성립되며 무한루프에 빠지게 된다.
알고리즘을 공부하다보면 해당 문제를 해결 할 수 있으니, 이 후에 다시 검토해보도록 하자.

const_interator

iterator를 읽기 전용으로만 사용할 수 있는 방법도 있다.
std::vector<int>::const_iterator cit; 이렇게 말이다.
다른 것으로 읽기 전용이라고도 볼 수 있는데, 포인터이긴 하나 데이터 값 자체를 변화시킬 수는 없다.

즉

std::vcetor<int>::const_iterator cit;
std::cout << *cit << std::endl;
std::cout << *(cit + 2) << std::endl;
// 이런 것들은 가능하지만
*cit = 30 // 이건 안된다는 말이다. 

포인터 연산을 통해 값을 불러오는 것은 가능하지만, 값을 변화시킬 수는 없다는 거.

std::vector<int>::const_iterator citr = v.cbegin();
std::vector<int>::const_iterator citr = v.cend();

reverse_iterator

vec.rbegin() 을 하게 되면 마지막 원소로 가게 되고,
vec.rend()을 하게 되면 원래 end 와 마찬가지로 한 칸 이전의 원소를 참조하게 된다.

#include <iostream>
#include <vector>

template <typename T>
void print_vector(std::vector<T>& vec) {
  // 전체 벡터를 출력하기
  for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
       ++itr) {
    std::cout << *itr << std::endl;
  }
}
int main() {
  std::vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  std::cout << "초기 vec 상태" << std::endl;
  print_vector(vec);

  std::cout << "역으로 vec 출력하기!" << std::endl;
  // itr 은 vec[2] 를 가리킨다.
  std::vector<int>::reverse_iterator r_iter = vec.rbegin();
  for (; r_iter != vec.rend(); r_iter++) {
    std::cout << *r_iter << std::endl;
  }
}

reverse_iterator 또한 상수 버전이 존재한다.
std::vector<int>::const_reverse_iterator 타입이고, crbegin() 과 crend()를 통해서 얻을 수 있다.

범위기반 반복문

#include <iostream>
#include <vector>

template <typename T>
void print_vector(std::vector<T>& vec) {
  // 전체 벡터를 출력하기
  for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
       ++itr) {
    std::cout << *itr << std::endl;
  }
}

template <typename T>
void print_vector_range_based(std::vector<T>& vec){
 for(const auto& item: vec){
   std::cout << item << std::endl;
 }

  
}
int main() {
  std::vector<int> vec;
  vec.push_back(10);
  vec.push_back(20);
  vec.push_back(30);
  vec.push_back(40);

  std::cout << "초기 vec 상태" << std::endl;
  print_vector(vec);

  std::cout << "범위 기반 반복문" << std::endl;
  print_vector_range_based(vec);

  return 0;
}

const auto&의 경우 벡터를 읽기 전용으로 참조만 하겠다는 것을 의미한다. 값의 변경이 필요하지 않을 때, 타입의 자동유추와 함께 사용되어 타입을 추론함과 동시에 값을 변경하지 않겠다는 것을 의미한다.

🗂️ list

양방향 연결 구조를 가진 자료형이다. vector와 달리 임의의 위치에 있는 원소로 마음대로 접근할 수 있는 것은 아니다.

그리고 list 연산자의 경우
it++ / it-- 와 같은 것만 사용가능하다 물론 반대의 경우인
++it / --it 도 성립한다.

int main(){
 std::list<int> lst;
 lst.push_back(1);
 lst.push_back(2);
 lst.push_back(3);
 lst.push_back(4);

 for(std::list<int>::iterator it = lst.begin(); it != lst.end(); it++){
   std::cout << *it << std::endl;
 }
  return 0;
}

출력값은

1
2
3
4

로 잘나옴을 확인할 수 있다.

list insert, earse

#include <iostream>
#include <list>

template <typename T> void print_list(std::list<T> &lst) {
  std::cout << "[";
  for (const auto &item : lst) {
    std::cout << item << " ";
  }
  std::cout << "]" << std::endl;
}

int main() {
  std::list<int> lst;
  lst.push_back(1);
  lst.push_back(2);
  lst.push_back(3);
  lst.push_back(4);

  std::cout << "리스트의 초기상태" << std::endl;
  print_list(lst);

  for(std::list<int>::iterator it = lst.begin(); it != lst.end(); it++) 
  { if(*it == 2){
    lst.insert(it, 7);
   }
  }
 std::cout << "삽입 리스트 상태" << std::endl;
 print_list(lst);

 for(std::list<int>::iterator it = lst.begin(); it != lst.end(); it++){
   if(*it == 4){
     lst.erase(it);
     break;
   }
 }
  
 std::cout << "원소 제거  리스트 상태" << std::endl;
 print_list(lst);
  
  return 0;
}

리스트의 초기상태
[1 2 3 4 ]
삽입 리스트 상태
[1 7 2 3 4 ]
원소 제거 리스트 상태
[1 7 2 3 ]

리스트는 벡터와 달리 원소를 지워도 반복자가 무효화 되지 않는다. 왜냐하면 주소값 자체는 그대로 있기 때문이다.
(이로 벡터는 원소를 지우게 되면 메모리에 할당하는 주소값이 변하게 되어 iterator가 제대로 작동하지 않게 되는 것임을 유추할 수 있다

🗄️ deque

vector와 비슷한 점을 가지고 있지만, 명확한 차이점이 존재한다. vector의 경우 할당받은 공간에 원소가 꽉 찬 경우 새로운 공간을 할당받아 메모리의 모든 원소를 복사하는 형태로, 공간을 동적으로 할당받아 사용한다.

deque의 경우, 메모리가 연속적으로 저장되어 있는 것이 아니라, 블록에 5개의 데이터가 저장되어 있는 형식임으로, 일반적인 상황에서 push_back이나 push_front의 수행시간이 시간복잡도 O(1)이다. 기존의 원소들을 복사할 필요가 없이 추가적으로 할당받은 블록에 바로 할당시켜주면 된다.

#include <iostream>
#include <deque>

template <typename T>
void print_deque(std::deque<T>& dq){
std::cout << "[";
  for(typename std::deque<T>::iterator it = dq.begin(); it != dq.end(); it++){
    std::cout << *it << " ";
  }
  std::cout << "]" << std::endl;
}

template<typename T>
void print_deque2(std::deque<T>& dq){
std::cout << "[";
 for(const auto& item : dq){
  std::cout << item << " ";
 }
 std::cout << "]" << std::endl;
}

int main(){
  std::deque<int> dq;
  dq.push_back(10);
  dq.push_back(20);
  dq.push_front(30);
  dq.push_front(40);

  std::cout << "초기 덱 상태" << std::endl;
  print_deque(dq);

  std::cout << "앞 원소 제거" << std::endl;
  dq.pop_front();
  print_deque(dq);
}

초기 덱 상태
[40 30 10 20 ]
앞 원소 제거
[30 10 20 ]

범위기반 반복문으로 해서 출력할 수도 있고, iterator로 접근하여 출력할 수도 있으니, 상황에 맞게 쓰면 되겠다.

set

set에 원소를 추가하기 위해서는 시퀀스 컨테이너처럼 insert를 이용하여 원소를 추가하면 된다. 어디에 추가할지에 대한 정보는 없는데, set에서 중요한 것은 원소가 있냐 없냐이기 때문이다. 원소를 추가하는 것은 O(log N)으로 처리되므로, 훨씬 빠르다. 트리구조로 저장되어있기 때문

itarator가 제공되지만, 리스트처럼 늘려가며 원소에 접근하는 것 말고는 방법이 없다.

find 함수를 통해 원소를 찾게 되면, std::set<int>::iterator를 리턴하고, 만일 존재하지 않는다면 s.end()를 리턴한다.

set도 마찬가지로 범위기반 반복문을 지원한다.
중복을 허용하지 않기 때문에 동일한 원소를 삽입하게 되면, 실행되지 않는다.
insert 작업 자체를 무시하게 된다.
그리고 내부 원소를 추가할 때 정렬된 상태를 유지하며 실행.

#include <iostream>
#include <set>

template <typename T>
void print_set(std::set<T>& s) {
  // 셋의 모든 원소들을 출력하기
  std::cout << "[ ";
  for (typename std::set<T>::iterator itr = s.begin(); itr != s.end(); ++itr) {
    std::cout << *itr << " ";
  }
  std::cout << " ] " << std::endl;
}
int main() {
  std::set<int> s;
  s.insert(10);
  s.insert(50);
  s.insert(20);
  s.insert(40);
  s.insert(30);

  std::cout << "순서대로 정렬되서 나온다" << std::endl;
  print_set(s);

  std::cout << "20 이 s 의 원소인가요? :: ";
  auto itr = s.find(20);
  if (itr != s.end()) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  std::cout << "25 가 s 의 원소인가요? :: ";
  itr = s.find(25);
  if (itr != s.end()) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
}

순서대로 정렬되서 나온다
[ 10 20 30 40 50 ]
20 이 s 의 원소인가요? :: Yes
25 가 s 의 원소인가요? :: No

#include <iostream>
#include <set>

template <typename T>
void print_set(std::set<T>& s) {
  // 셋의 모든 원소들을 출력하기
  std::cout << "[ ";
  for (typename std::set<T>::iterator itr = s.begin(); itr != s.end(); ++itr) {
    std::cout << *itr << " ";
  }
  std::cout << " ] " << std::endl;
}

class Todo {
  int priority;
  std::string task_name;

  public:

  Todo(int priority, std::string task_name): priority(priority), task_name(task_name) {} // 생성자 

  bool operator<(const Todo& t) const {
    if(priority == t.priority) {
      return task_name < t.task_name;
    }
    return priority > t.priority;
  }
friend std::ostream& operator<<(std::ostream& o, const Todo& td);
};

std::ostream& operator<<(std::ostream& o, const Todo& td) {
  o << "[ 중요도: " << td.priority << "] " << td.task_name;
  return o;
}

int main() {
  std::set<Todo> todos;

  todos.insert(Todo(1, "농구 하기"));
  todos.insert(Todo(2, "수학 숙제 하기"));
  todos.insert(Todo(1, "프로그래밍 프로젝트"));
  todos.insert(Todo(3, "친구 만나기"));
  todos.insert(Todo(2, "영화 보기"));

  print_set(todos);
  //여기서 Todo 객체를 사용하고 있는 연산자 객체를 오버로딩 하는 함수

  std::cout << "-------------" << std::endl;
  std::cout << "숙제를 끝냈다면!" << std::endl;
  todos.erase(todos.find(Todo(2, "수학 숙제 하기")));
  print_set(todos);


 return 0;
}

friend 는 클래스의 친구로써 friend로 선언된 클래스나 함수는 해당 클래스의 모든 멤버에 접근할 수 있다.
friend 키워드는 클래스의 private 또는 protected 멤버에 접근 권한을 부여할 때 사용된다.

위 코드에서 Todo 라는 typename으로 선언한 todos set에 클래스 생성자를 호출하며, insert를 통해 객체를 삽입하고, print_set 함수를 실행하게 되면, todos의 타입인 Todo를 typename으로 넘겨주게 되고, 결국 함수를 실행하게 될 때, operator<< 오버로딩 함수가 작동한다.

<< 연산자는 이전에 수행된 연산의 결과인 std::ostream 객체를 반환합니다. 이런 식으로 체이닝이 가능하도록 하기 위해 operator<< 함수는 std::ostream&를 반환합니다.

return o;는 출력이 끝난 스트림을 반환하여 다음 연산이 가능하게 합니다.

struct TodoCmp {
  bool operator()(const Todo& t1, const Todo& t2) const {
    if (t1.priority == t2.priority) {
      return t1.job_desc < t2.job_desc;
    }
    return t1.priority > t2.priority;
  }
};

int main(){
std::set<Todo, TodoCmp> todos;
}

operator 연산자를 오버로딩 하는 것 대신 직접 비교연산자에 대한 함수를 만들어주고 할당할 수도 있는데,

아래 set의 정의된 코드처럼 2번 째 parameter로 compare을 받기 때문에, 내가 원하는 비교연산자 수행 함수를 작성하여 전달하면 자료구조가 내부적으로 compare의 규칙에 따라 정렬을 수행하게 된다.

template <class Key, class Compare = std::less<Key>,
          class Allocator = std::allocator<Key>
          >class set;

map

#include <iostream>
#include <map>
#include <utility>

template <typename K, typename V> void print_map(std::map<K, V> &m) {
  // map에는 std::pair로 key와 value 가 들어간다.
  for (const auto &kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}


int main() {
  std::map<std::string, int> m;
  // 맵에 없는 키를 m["none_key"] 로 참조하게 되면, default value 가 return 
  m.insert(std::make_pair("hive", 4));
  m.insert(std::pair<std::string, int>("bee", 3));
  m["c++"] = 3;
  
  m["python"] = 6;
  m["Python"] = 7;
 //처음에 할당해주지 않았어도, 직접 할당가능하다. 
 //이미 존재한다면 값이 대체될 것이다. 
 
  if (m.find("hello") == m.end()) {
    // find 했는데 없으면 end()값을 반환함. 
    
    std::cout << "hello list not found" << std::endl;
    // std::cout << m["hello"] << std::endl;
  }
  
  std::cout << m.begin()->first
            << m.begin()->second; //대문자가 먼저나옴. 아스키코드 정렬.
  return 0;
}

본 내용은 씹어먹는c++을 통해 알게된 내용을 개인적인 공부를 위해 정리한 포스팅입니다. 저작권을 해칠 의도가 없으며, 모든 것은 해당 블로그 저자의 지식재산입니다.
https://modoocode.com/210