알고리즘 풀이를 위한 C/C++/STL 기초 정리 - STL(1) 편

## // C/C++/STL 기초

 

[https://docs.google.com/document/d/1xrhb-6Vm5_0zd2iImbdg_4kN2cTnY-ZSzyrFAavwABI/edit?usp=sharing](https://docs.google.com/document/d/1xrhb-6Vm5_0zd2iImbdg_4kN2cTnY-ZSzyrFAavwABI/edit?usp=sharing)

Algorithm Note - 1. C/C++/STL

 

3. STL(1) 사용법

 

// STL = algorithm + container + function + iterator 로 구성

 

//3.1 pair

#include<utility> 또는 #include<vector> 또는 #include<algorithm>

 

pair<int,int> p1 = make_pair(10,20);

pair<int,int> p1 = pair<int,int>(10,20);

pair<int,int> p2(10,20);

 

p1.first 와 p1.second 로 접근

 

//3.2 tuple

#include<tuple>

tuple<int,int,int> t1 = make_tuple(10,20,30);

cout<<get<0>(t1)<<'\n'; //<0>안에는 변수가 못들어 간다.

 

//3.3 tie

#include<tuple>

 

eg)

int x,y,z;

tie(x,y,z) = make_tuple(1,2,3);

eg)

tie(b,a,ignore) = make_tuple(a,b,10);

tie(a,b) = make_pair(b,a); //swap한줄 구현

 

//3.4 vector

#include<vector>

 

eg)

vector<int> v1;

vector<int> v1(10); //크기 10

vector<int> v1(10,5); // 크기 10이고 초기값 전부 5

vector<int> v1 = {1,2,3}; // 초기화 리스트를 이용해서 행성

 

eg)

v.push_back(); v.pop_back();

v.clear(); v.resize(); v.empty(); v.size();

 

v.begin(); v.end(); //포인터

  

v.front(); v.back(); v[1] //값 참조

 

v.emplace_back(1,2) //원소가 pair인 경우

 

eg)

v.insert(it,<t>)//해당 위치에 , 넣을거

v.insert(it,10,<t>) // 해당 위치에, 갯수 만큼 , 넣을거

v.insert(it,d.begin(),d.end())// 해당 위치에, 넣을 첫, 넣을 끝

  

eg)

v.erase(it);//지울거 포인팅

v.erase(it.start(),it.end())//지울거 시작 - 끝

  

//3.5 deque

#include<deque>

deque<int> dq;

 

dq.push_back(t);

dq.push_front(t);

dq.pop_back();

dq.pop_front();

 

//3.6 list 이중연결 리스트 : insert와 erase는 O(1)이 걸림

#include<list>

 

list<int> l ={2,1,-5};

l.sort(); // 기본 : 오름차순

l.sort(greater<int>());//내림차순

l.sort([](int& u,int& v){return abs(u)<abs(v);}); //커스텀 정렬

l.reverse

 

//순차 컨테이너 : vector list deque

//연관 컨테이너 : set map

 

//3.8 set 삽입 삭제 탐색에 log(n) 걸림

#include<set>

 

set<int> s1;

set<int> s2 = {1,2,3,4} // 자동 오름차 정렬 저장 및 중복 제거됨

set<int,greater<int>> s3 // 자동 내림차 정렬 하기

  

eg)

s1.insert(4); // 대입

pair<set<int>::iterator, bool > result = s2.insert(4); //결과 반환(넣은 위치,성공 여부)

 

    s1.erase(s.begin()); //삭제

    s1[] X //set은 순서 가 아니야

    auto it = s.erase(s.begin()+1);//{1,2,3,4} -> {1,3,4}

    it = s.erase(it) //{1,3,4} -> {1,4}

eg)

set은 for 나 foreach로 순회가 가능하다. lgN

 

eg)

s = {1,3,5,7}

auto it = s.find(1); //{1,3,5,7} 첫번재 원소를 가르킴

//없으면 s.end()를 반환함

 

    s.count(7) // 원소 7이 몇개? 1개

 

//3.8.2 multiset: 같은 원소 여러개를 저장 가능하다.

 

정리)

<T>.count의 의미

map,unordered_map,set 에서는 0또는 1 (생성하지 않고 존재 유무 )

multiset 에서는 0또는 N( 존재 및 갯수)

 

//3.9 map - key와 value로 이루어짐

  

#include<map>

  

map<int,int> d2 = {{1,2},{3,4}};

d2.size();//2

d2[1] //2 key를 이용해서 value참조

d2[0] //0 없으면 만들어진다. key값 0 에 value 기본값

 

eg)

if(d2[i]){...}//존재확인 + 없으면 만들어 버림

if(d2.count(i)){..} //존재 확인만

 

eg)

map<int,int> d

//내용물을 iterator 로 돌기

for(auto it = d.begin(); it != d.end() ; it++){

cout<<it->first<<it->second;

}

//내용물은 pair

for(auto& p:d){

cout<<p.first<<p.second;

}

  

//컨테이너 어댑터 : stack,queu,우선큐,bitset : 앞의 자료구조로 만듬.

 

//3.10 stack

#include<stack>

 

    stack<int> s1; //기본

    deque<int> d = {1,2,3}; stack<int> s2(d); //댁을 스택으로

    stack<int,list<int>> s3; // 리스트로 스택 만들기

 

    s.push(<T>)

    s.pop()

    s.top()

    s.size()

    s.empty()

    s.emplace(5,6)

 

//3.11 queue

#include<queue>

 

    queue<int> q1;

    deque<int> d = {1,2,3}; queue<int> q3(d) // 댁으로도 큐 가능

    queue<int,list<int>> q2; //리스트로 큐 만들기

 

    q1.push(<t>)

    q1.pop()

    q1.front()

    q1.back()

    q1.size()

    q1.empty()

    q1.emplace_back()

 

//3.12 priority_queue - #include<queue>에 같이 동봉됨.

 

#include<queue>

 

    priority_queue<int> pq;

 

    pq.push()

    pq.pop()

    pq.top() //  우선 큐는 특이하게 front 가 아닌 top 이다. tree형 stack을 연상하나봄.

    pq.empty() pq.size()

eg) 우선큐는 기본적으로 오름차 순으로 정렬된다. 그럼 내림차 우선 큐는 어떻게 만드나? 1. priority_queue<int,vector<int>,greater<int>> q3; 2. 입력시 pq.push(-x); 출력시 -pq.top() // a<b 는 -a > -b 이므로 -를 붙여 반대순서로 넣고/ 출력시 -붙여 원상복귀

 

//3.13 bitset

  

//vector<bool> 형태 , 1bit만 사용한다.

  

bitset<10> b2(88) //10자리 2진수를 만드는데, 십진수 88을 넣을꺼임

bitset<10> b2("10010")//10자리 2진수를 만드는데, 2진수 10010을 넣을꺼임

bitset<n> b2 // 애러

 

    bitset<100000>a;

    bitset<100000>b;

 

    cin >> a >> b;

 

    cout << (a & b) << '\n'; //AND

    cout << (a | b) << '\n'; //OR

    cout << (a ^ b) << '\n';    //XOR

    cout << ~(a) << '\n';   //NOT

    cout << ~(b);       //NOT

 

eg)참조

 

b2[i]

b2.test(i)

  

b.flip() b.flip(1) // 0 => 1, 1 => 0

b.set() b.set(1) // 0,1 => 1로

b.reset() b.reset(1) //0,1 => 0으로

  

b.all() //모두 1?

b.any() //적어도 한개는 1?

b.none() //모두 0?

b.count()//1이 몇개인가?

 

//삽입 삭제 시간 --> 백터는 N , set은 lgN, 리스트는 1

//count의 의미 set에서는 존재성 / multiset 에서는 갯수 / STL의 count도 갯수, map,unordered_map에서 존재성

 

 

DOS IMPACT - WEB Developer

KIM DO YOUNG

WEB : REACT JS | REACT NATIVE | GraphQL PRISMA