알고리즘 ] 1. C++ STL 파악하기

1. C++ STL(Standard Template Library, 표준 템플릿 라이브러리)

- C++에서 지원하는 기본 템플릿 라이브러리를 사용해서 문제를 푸는 것이 효율적이다.

 

2. 기능

- 컨테이너와 배열 같은 클래스들을 제공

- 정렬, 검색 등을 지원하는 트리 구조의 컨테이너가 있음

 

3. 종류

1) 시퀀스 컨테이너 (배열/연결 리스트연결 리스트)

- 일반적인 자료구조

- 정렬되지 않은 형태

- 컨테이너: array (C++ 11), vector, list, deque

2) 어댑터 컨테이너

- 기본적인 시퀀스 컨테이너의 변형 버전

- 컨테이너: stack, queue, priority_queue

3) 정렬 연관 컨테이너

- 트리 구조로 이루어진 자료구조

- 정렬되어 있는 형태

- 검색, 정렬, 삽입, 삭제 등의 시간 복잡도에서 유리하다.

- 컨테이너: set, multiset, map, multimap

 

4. 사용법

1) vector

[인덱스로 접근]

#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec;
  vec.push_back(10);  // 맨 뒤에 10 추가
  vec.push_back(20);  // 맨 뒤에 20 추가
  vec.push_back(30);  // 맨 뒤에 30 추가
  vec.push_back(40);  // 맨 뒤에 40 추가

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

[Iterator 사용해서 접근]

// 반복자 사용 예시
#include <iostream>
#include <vector>

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

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

  // int arr[4] = {10, 20, 30, 40}
  // *(arr + 2) == arr[2] == 30;
  // *(itr + 2) == vec[2] == 30;

  std::vector<int>::iterator itr = vec.begin() + 2;
  std::cout << "3 번째 원소 :: " << *itr << std::endl;
}

[중간에 추가, 삭제]

  vec.insert(vec.begin() + 2, 15);
  print_vector(vec);

  std::cout << "----------------------------" << std::endl;
  // vec[3] 제거
  vec.erase(vec.begin() + 3);

 

2) stack

#include<iostream>
#include<stack>
using namespace std;
 
int main(void){
    stack<int> st;
    
    st.push(10);
    st.push(20);
    st.push(30);
    st.push(40);
    st.push(50);
    
    cout << "st.size() : " << st.size() << endl;
    cout << "st.top() -> st.pop()" << endl;
    while(!st.empty()){
        cout << st.top() << endl;
        st.pop();
    }    
    return 0;    
}

 

3) set

- 중복값 저장 불가능

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;
  }
}

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){

	// map
	// <string, int> => <key, value>
	map< string, int > m;


	// insert(key,value)
	m.insert(make_pair("a", 1));
	m.insert(make_pair("b", 2));
	m.insert(make_pair("c", 3));
	m.insert(make_pair("d", 4));
	m.insert(make_pair("e", 5));
	m["f"] = 6; // also possible


	// erase(key)
	m.erase("d");
	m.erase("e");
	m.erase(m.find("f")); // also possible


	// empty(), size()
	if(!m.empty()) cout << "m size : " << m.size() << '\n';


	// find(key)
	cout << "a : " << m.find("a")->second << '\n';
	cout << "b : " << m.find("b")->second << '\n';


	// count(key)
	cout << "a count : " << m.count("a") << '\n';
	cout << "b count : " << m.count("b") << '\n';


	// begin(), end()
	cout << "traverse" << '\n';
    // map< string, int >::iterator it; also possible 
	for(auto it = m.begin(); it != m.end(); it++){
		cout << "key : " << it->first << " " << "value : " << it->second << '\n';
	}

	return 0;

}