반응형
반응형

1. string의 주요 인터페이스와 특징

  1. 시퀀스 컨테이너, 배열 기반 컨테이너

  2. string, wstring 제공

    • string : char 형식 문자 관리
    • wstring : wchar_t 형식 문자 관리
  3. 멤버 정의 형식

    멤버 정의 형식 내용
    allocator_type 메모리 관리자 형식
    const_iterator const 반복자 형식
    const_pointer const value_type* 형식
    const_reference const vluae_type& 형식
    const_reverse_iterator const 역 반복자 형식
    difference_type 두 반복자 차이의 형식
    iterator 반복자 형식
    npos 찾기 관련 '실패' 정의 값, 일반적으로 -1
    pointer value_type* 형식
    reference value_type& 형식
    reverse_iterator 역 반복자 형식
    size_type 첨자나 원소 개수 등 형식
    traits_type 문자의 특성 형식
    value_type 원소의 형식
  4. 생성자

string s;              // 기본 생성자
string s(sz);          // sz 문자열로 s 생성
string s(sz,n);        // sz 문자열에서 n개 문자로 s 생성
string s(n,c);         // n개의 c 문자로 s 생성
string s(iter1,iter2); // 반복자 구간 [iter1,iter2)의 문자로 s 생성
string s(p1, p2);      // 포인터 구간 [p1, p2)의 문자로 s 생성
  1. 멤버 함수
s.append(sz)        // s에 sz를 붙임
s.assign(sz)        // s에 sz문자열을 할당
s.at(i)             // s의 i번째 문자를 참조
p=s.begin()         // p는 s의 첫문자를 가리키는 반복자
p=s.end()           // p는 s의 끝을 표식하는 반복자
p=s.rbegin()        // p는 s 역순차열의 첫문자를 가리키는 반복자
p=s.rend()          // p는 s 역순차열의 끝을 표식하는 반복자
s.c_str()           // C 스타일의 문자열 주소 반환(null문자 포함)
n=s.capacity()      // n은 s에 할당된 메모리 공간 크기
s.clear()           // s를 비움
s.compare(s2)       // s와 s2를 비교
s.copy(buf,n)       // buf로 n 개의 문자를 복사
s.data()            // 문자열의 배열 주소를 반환
s.empty()           // s가 비었는지 조사
q=s.erase(p)        // p가 가리키는 문자를 제거, q는 다음 원소 가리킴
q=s.erase(b,e)      // 반복자 구간 [b,e)의 모든 문자 제거, q는 다음 원소
s.find(c)           // c 문자를 검색
s.rfind(c)          // c 문자를 끝부터 찾음
s.insert(n,sz)      // n의 위치에 sz를 삽입
s.length()          // 문자의 개수
n=s.max_size()      // n은 s가 담을 수 있는 최대 문자 개수(메모리 크기)
s.push_back(c)      // s의 끝에 c를 추가
s.replace(pos,n,sz) // pos 위치의 n개 문자를 sz로 바꿈
s.reserve(n)        // b개의 문자를 저장할 공간 예약
s.resize(n)         // s의 크기를 n으로 변경하고 확장되는 공간의 값을 기본값으로 초기화
s.resize(n,c)       // s의 크기를 n으로 변경하고 확장되는 공간의 값을 c로 초기화
s.size()            // s의 원소 개수
s2=s.substr(pos)    // s2는 pos부터 s의 문자열
s.swap(s2)          // s와 s2를 swap
  1. 연산자

    연산자 내용
    s[i] i 번째 위치 문자
    s+=s2 s와 s2의 합을 s에 할당
    s+s2 s와 s2를 합한 string 객체
    s=s2 s2에 s 할당
    out<<s s를 스트림에 씀
    in>>s 스트림에서 s로 읽음
    getline(in,s) 스트림에서 s로 한줄을 읽음
    그 외 비교연산 ==, !=, <, >, <=, >=

참고

2. 상세 예제

  1. 문자열 초기화 예제
string t("Hello!");
const char* p1 = "Hello!";
const char* p2 = p1 + 6;

string s1;
string s2("Hello!");
string s3("Hello!", 2);
string s4(5, "H");
string s5(t.begin(), t.end());
string s6(p1, p2);
// s1 =
// s2 = Hello!
// s3 = He
// s4 = HHHHH
// s5 = Hello!
// s6 = Hello!
  1. 문자열 붙이기 예제
    • append : 부분 또는 전체 붙일 때
    • += : 전체 붙일 때
string s("He");
string t("llo!");
const char* p1 = "llo!";
const char* p2 = p1+4;

s.append(t);
// Hello!
s.append(t,0,4);
// Hello! ( [0,4) 구간 합치기 )
s.append("llo!");
// Hello!
s.append("llo!", 4);
// Hello!
s.append(t.begin(), t.end());
// Hello!
s.append(p1,p2);
// Hello!
s.append(5, 'H');
// HeHHHHH
s += t;
// Hello!
s += "llo!"
// Hello!
for(string::iterator iter=t.begin(); iter != t.end(); ++iter){
   s.push_back(*iter);
}
// Hello!
  1. 문자열 대입 예제
    • assign : 부분 또는 전체 문자열 할당
    • = : 전체 문자열 할당
string t("Hello!");
const char* p1 = "Hello!";
const char* p2 = p1 + 6;

string s;

s.assign(t);
// Hello!;
s.assign(t,0,6);
// Hello!(t의 [0,6) 구간 할당)
s.assign("Hello!");
// Hello!;
s.assing("Hello!", 6);
// Hello! ( 앞에서 부터 6개 문자열 할당 )
s.assign(6, 'H');
// HHHHHH ( H 6개 문자열 할당 )
s.assign(t.begin(), t.end());
// Hello!
s.assign(p1, p2)
// Hello!
s = t;
// Hello!
s = "Hello!";
// Hello!
  1. c_str(), data()
    • c_str : null 문자 포함한 C-style 문자열 반환
    • data : null 문자 포함하지 않는 C-style 문자열 반환
string s("Hello!");
const char *sz = s.c_str();
// \0 문자로 끝나는 문자열
const char *buf = s.data();
// \0 문자 포함하지 않는 문자열
  1. compare()
    • 문자열을 비교(부분 문자열 비교 가능)
    • s1 > s2 이면 1을 반환
    • s1 < s2 이면 -1을 반환
    • s1 == s2 이면 0을 반환
string s1("ABCDE");
string s2("AKABC");
const char* sz = "AKABC";

s1.compare(s2);
// -1 반환 ("ABCDE" 와 "AKABC" 비교)
s1.compare(2,3,s2);
// 1 반환 ( s1과 s2의 2 위치부터 3개 비교, "CDE", "ABC" 비교)
s1.compare(0,3,s2,2,3);
// 0 반환 (s1의 0 위치부터 3개["ABC"]와 s2의 2 위치부터 3개["ABC"]를 비교)
s1.compare(sz);
// -1 반환 ( "ABCDE" 와 "AKABC" 비교 )
s1.compare(2,3,sz);
// 1 반환 ( s1과 sz의 2 위치부터 3개 비교, "CDE", "ABC" 비교)
s1.compare(0,1,sz,1)
// 0 반환
  1. copy()
    • null 문자 없는 문자열 복사
string s("Hello!");
char buf[100];

s.copy(buf, s.length());
// buf = Hello!
buf[s.length()] = '\0';
// buf = Hello!\0
s.copy(buf,4,2);
// buf = llo! ( 2위치 부터 4개 복사 )
buf[4] = '\0';
// buf = llo!\0
  1. find() , rfind()
const char *sz = "Be careful in Uncle Randy's new car";
string t("Randy");
string s = sz;

s.find("e");
// 1 출력( e가 처음 발견된 위치 )
s.find("e", 10);
// 18 (10위치 부터 검색하여 e가 처음 발견된 위치)
s.find("new car");
// 28 (new car 가 처음 발견된 n의 위치)
s.find("new car", 10);
// 28 (10위치 부터 new car 가 처음 발견된 n의 위치)
s.find("new car", 0, 1);
// 12 (0 위치 부터 new car의 1개 값(n)이 처음 발견된 위치)
s.find(t, 0);
// 20 ( 0위치 부터 t("Randy")가 발견된 첫 위치)
  1. insert()
    • 문자열 삽입
string t("ABC");
string s("Hello");

s.insert(1, "ABC");
// "HABCeelo"(S의 1위치에 ABC 삽입)
s.insert(1, "ABC", 2);
// "HABeelo"(S의 1위치에 ABC에서 2개문자[AB] 삽입)
s.insert(1, t);
// "HABCello" ( s의 1위치에 t["ABC"] 삽입)
s.insert(1, t, 0, 2);
// "HABeelo" ( s의 1위치에 t의 0번째 위치 부터 2개 문자["AB"] 삽입)
s.insert(1, 3, "A");
// "HAAAello" ( s의 1위치에 "A"를 3개 삽입)
s.insert(s.begin() + 1);
// "H ello" ( s의 1위치에 공백 삽입 )
s.insert(s.begin() + 1, 'A');
// "HAello" ( s의 1위치에 'A' 삽입)
s.insert(s.begin() + 1, 3, 'A');
// "HAAAello" ( s의 1위치에 'A'를 3개 삽입)
s.insert(s.begin() + 1, t.begin(), t.end());
// "HABCello" ( s의 1위치에 t[begin,end) 삽입)
  1. replace()

    • 문자열을 교체
string t("ABC");
string s("Hello!");

s.replace(0,3,"ABC");
// "ABClo!" (s의 0번째 부터 3개 문자를 "ABC" 로 변경)
s.replace(0,3,t);
// "ABClo!" (s의 0번째부터 3개 문자를 t["ABC"]로 변경)
s.replace(0,3,"ABC",2);
// "ABlo! ( s의 0번째부터 3개 문자를 "ABC"의 앞 2개 문자로 변경)
s.replace(0,3,t,0,2);
// "ABlo! ( s의 0번째부터 3개 문자를 t의 0번째부터 2개 문자["AB"]로 변경)
s.replace(0,3,2,'A');
// "AAlo!" ( s의 0번째부터 3개 문자를 'A' 2개로 변경)
s.replace(s.begin(), s.begin()+3, "ABC");
// "ABClo!" (s의 0번째 부터 3개 문자를 "ABC" 로 변경)
s.replace(s.begin(), s.begin()+3, t);
// "ABClo!" (s의 0번째부터 3개 문자를 t["ABC"]로 변경)
s.replace(s.begin(), s.begin()+3, "ABC", 2);
// "ABlo! ( s의 0번째부터 3개 문자를 "ABC"의 앞 2개 문자로 변경)
s.replace(s.begin(), s.begin()+3, 3, 'A');
// "AAAlo!" ( s의 0번째부터 3개 문자를 "A" 3개로 변경)
s.replace(s.begin(), s.end(), t.begin(), t.end());
// "ABC" (s의 문자를 t의 [begin,end) 구간 문자["ABC"]로 변경)
  1. substr()
  • 일부 문자열을 추출할 때 사용
string t("Hello!");
string s;

s = t.substr(0);
// "Hello!" ( 0 부터 끝까지 )
s = t.substr(0, string::npos);
// "Hello!" ( 0 부터 끝까지 )
s = t.substr(0, 2);
// "He" ( 0부터 2개 )
s = t.substr(2,3);
// "llo" ( 2부터 3개 )
s = t.substr(2, string::npos);
// "llo!" ( 2부터 끝까지)
  1. 스트림으로 부터 입력
string s;
getline(cin, s);
// 문자열을 입력 받는다.
getline(cin, s ,'\n');
// 문자열을 입력 받는다. 종료 문자열 저장 가능
  1. 뇌를 자극하는 C++ STL
반응형
반응형

1.stack

  1. 기본 컨테이너는 deque
  2. 템플릿 형식
    • T : 원소 형식
    • Conatiner : stack에 사용될 컨테이너
template<typename T,
         typename Container=deque<T>>
class stack
  1. 멤버 형식
멤버 형식 내용
value_type Container::value_type, T형식
size_type Container::size_type, 첨자 또는 원소 개수 등의 형식
container_type Container 형식, 기본 deque
  1. 생성자
explicit stack(const Container& = Container())
// 컨테이너 기본 생성자 호출해 stack을 생성하거나
//인자로 받아 stack을 생성
  1. 멤버 함수
bool empty() const             // 원소가 없는가?
size_type size() const         // 원소의 개수
void push(const vluae_type& x) // 원소 추가
void pop()                     // 원소 제거
value_type& top()              // Top 원소의 참조
const value_type& top() const  // const 객체 Top 원소 참조
  1. 예제
#include<stack>
stack<int> st;
st.push(10);   // 원소 추가
st.push(20);
st.push(30);

while(!st.empty()){
   cout<< st.top() << endl; // Top 원소 꺼내기
   st.pop(); // 원소 제거
}

2. queue 컨테이너

  1. 기본 컨테이너는 deque
  2. 템플릿 형식
    • T : 원소 형식
    • Conatiner : queue에 사용될 컨테이너
template<typename T,
         typename Container=deque<T>>
class queue
  1. 멤버 형식
멤버 형식 내용
value_type Container::value_type, T형식
size_type Container::size_type, 첨자 또는 원소 개수 등의 형식
container_type Container 형식, 기본 deque
  1. 생성자
explicit queue(const Container& = Container())
// 컨테이너 기본 생성자 호출해 queue을 생성하거나
//인자로 받아 queue를 생성
  1. 멤버 함수
bool empty() const             // 원소가 없는가?
size_type size() const         // 원소의 개수
void push(const vluae_type& x) // 원소 추가
void pop()                     // 원소 제거
value_type& front()            // 첫 원소 참조
value_type& back()              // 마지막 원소의 참조
const value_type& front() const // const 객체 첫 원소 참조
const value_type& back() const   // const 객체 마지막 원소 참조
  1. 예제
#include<queue>
queue<int, list<int>> q;
q.push(10);   // 원소 추가
q.push(20);
q.push(30);

while(!q.empty()){
   cout<< q.front() << endl; // Top 원소 꺼내기
   q.pop(); // 원소 제거
}

3. priority_queue 컨테이너

  1. 들어간 순서에 상관없이 우선순위가 높은 데이터나 나옴

  2. STL에서 priority_queue

    • STL의 힙 알고리즘(make_heap, push_heap, pop_heap)을 사용해 구현
    • 임의 접근 반복자를 제공해야함(vector 또는 deque)
  3. 기본 컨테이너는 vector

  4. 템플릿 형식

    • T : 원소 형식
    • Conatiner : priority_queue에 사용될 컨테이너, 기본 vector
    • Comp : 우선순위를 결정할 정렬 기준, 기본 less
template<typename T,
         typename Container=deque<T>,
         typename Comp=less<typename Container::value_type>>
class priority_queue
  1. 멤버 형식
멤버 형식 내용
value_type Container::value_type, T형식
size_type Container::size_type, 첨자 또는 원소 개수 등의 형식
container_type Container 형식, 기본 vector
  1. 생성자
explicit priority_queue(
   const Comp& = Comp(),
   const Container& = Container())
// 컨테이너 기본 생성자 호출해 queue을 생성하거나
//인자로 받아 priority_queue를 생성
  1. 멤버 함수
bool empty() const             // 원소가 없는가?
size_type size() const         // 원소의 개수
void push(const vluae_type& x) // 원소 추가
void pop()                     // 원소 제거
value_type& top()              // Top 원소의 참조
const value_type& top() const   // const 객체 Top 원소 참조
  1. 예제
#include<queue>
priority_queue<int> pq1;
pq1.push(40);   // 원소 추가
pq1.push(20);
pq1.push(30);
pq1.push(50);
pq1.push(10);

while(!pq1.empty()){
   cout<< pq1.top() << endl; // Top 원소 꺼내기
   // 50 40 30 20 10 (less)
   pq1.pop(); // 원소 제거
}

priority_queue<int, deque<int>, greater<int>> pq2;
pq2.push(40);   // 원소 추가
pq2.push(20);
pq2.push(30);
pq2.push(50);
pq2.push(10);

while(!pq2.empty()){
   cout<< pq2.top() << endl; // Top 원소 꺼내기
   // 10 20 30 40 50 (greater)
   pq2.pop(); // 원소 제거
}

참고

  1. 뇌를 자극하는 C++ STL
반응형

'C++ > STL' 카테고리의 다른 글

[STL-19] string  (0) 2021.03.14
[STL-17] 반복자  (0) 2021.03.14
[STL-16] 함수 객체 - 함수 어댑터  (0) 2021.03.14
[STL-15] 함수 객체 - 비교/논리 연산 조건자  (0) 2021.03.14
[STL-14] 함수 객체 - 산술 연산 함수 객체  (0) 2021.03.14
반응형

1. 반복자 개요

  1. 반복자란?
    • 포인터를 추상화한 클래스
    • 포인터가 하지 못하는 더 많은 동작 가능
  2. 반복자의 종류
    • 입력 반복자 : 전방향 읽기(istream)
    • 출력 반복자 : 전방향 쓰기(ostream)
    • 순방향 반복자 : 전방향 읽기,쓰기
    • 양방향 반복자 : 양방향 읽기, 쓰기(list, set, multiset, map, multimap)
    • 임의 접근 반복자 : 랜덤 읽기, 쓰기(vector, deque)
  3. 반복자 종류에 따른 가능 연산
반복자 가능 연산
입력 반복자 *iter, ->, ++, ==,!=, iterator(iter)
출력 반복자 *iter=x, ++, iterator(iter)
순방향 반복자 *iter, ->, ++, == , =, iterator(), iterator(iter)
양방향 반복자 순방향 반복자 기능 + --
임의 접근 반복자 양방향 반복자 기능 + , [], +=, -=, +, -, <, >, <=, >=
  1. 순차열

    • 순서 있는 원소의 집합
  2. 구간

    • 순차열의 시작과 끝을 나타내는 반복자의 쌍으로 표현
    • [begin, end) : begin은 순차열 원소에 포함되지만, end는 포함되지 않음
    • ex) 10, 20, 30, 40, 50, 60
    • iter = 30 일 경우
    • [begin, end) => 10, 20, 30, 40, 50
    • [begin, iter) => 10, 20
    • [iter, end) => 30, 40, 50

2. 반복자 상세

종류 방향 쓰기
iterator 정방향 O
const_iterator 정방향 X
reverse_iterator 역방향 O
const_ reverse_iterator 역방향 X
  1. const 키워드 + 반복자

    • 반복자가 가리키는 원소의 위치 변경 안할 때 사용
  2. 역방향 반복자

    • 반복자가 가리키는 다음 원소의 값을 참조함
    • ex) 10,20,30,40,50 일 때
    • rbegin 은 end()를 가리키고, 50을 참조
    • rend 는 10을 가리키고, 10 한칸 앞을 참조
vector<int> v = {10,20,30,40,50};
vector<int>::iterator iter = v.begin();
vector<int>::const_iterator citer = v.begin();
const vector<int>::iterator const_iter = v.begin();
const vector<int>::const_iterator const_citer = v.begin();

// 값 대입
*iter  = 100; *const_iter = 100;   // 가능
*citer = 100; *const_citer = 100;  // 불가능

// 반복자 변경
**iter; ++citer;              // 가능
++const_iter , ++const_citer; // 불가능

// 역방향 반복자
for(vector<int>::reverse_iterator riter v.rbegin(); riter != v.rend(), +riter){
   cout << *riter << " ";
}
cout << endl;
// 50,40,30,20,10 출력됨

3. 삽입 반복자

  1. 순차열에 원소를 삽입 할 수 있게 반복자를 변환하는 어댑터

    • 기본은 덮어쓰기 모드로 동작
  2. inserter()

    • insert_iterator 객체 생성
    • 컨테이너의 insert() 멤버 함수 호출
    • 삽입모드로 동작하게 함
    • 모든 컨테이너 사용 가능
vector<int> v1 = {10,20,30,40,50};
vector<int> v2;
copy(v1.begin(), v1.end(), v2.begin());
// copy 알고리즘은 덮어쓰기 모드로 동작하므로
// v2의 size가 0 이여서 오류 발생함

copy(v1.begin(), v1.end(), inserter<vector<int>>(v2, v2.begin()));
// 삽입 모드로 변경
// v2  = {10,20,30,40,50};
  1. back_inserter()

    • back_insert _iterator 객체 생성
    • 컨테이너의 push_back() 멤버 함수 호출
    • 뒤쪽에 삽입함
    • vector, deque, list 만 사용 가능
  2. front_inserter()

    • front_insert _iterator 객체 생성
    • 컨테이너의 push_front() 멤버 함수 호출
    • 앞쪽에 삽입함
    • deque, list만 사용 가능
vector<int> v = {10,20,30,40,50};
list<int> lt1 = {1,2,3};
list<int> lt2 = {1,2,3};

copy(v.begin(), v.end(), back_inserter<list<int>>(lt1));
// lt1 = {1,2,3,10,20,30,40,50}

copy(v.begin(), v.end(), front_inserter<list<int>>(lt2));
// lt2 = {50,40,30,20,10,1,2,3}

4. 입/출력 스트림 반복자

  1. istream_iterator<T>

    • 입력 스트림과 연결된 반복자
    • T 형식의 값을 스트림에서 읽을 수 있음
  2. ostream_iterator<T>

    • 출력 스트림과 연결된 반복자
    • T 형식의 값을 스트림에 쓸 수 있음
vector<int> v = {10,20,30,40,50};
copy(v.begin(), v.end(), ostream_iterator<int>(cout));
// 1020304050 이 출력됨
copy(v.begin(), v.end(), ostream_iterator<int>(cout, ","));
// 10,20,30,40,50 이 출력됨

list<int> lt = {100,200,300};
transform(
   lt.begin(), lt.end(), v.begin(),
   ostream_iterator<int>(cout, " "),
   plus<int>());
// 110 220 330 이 출력됨

//istream_iterator
vector<int> v2;
copy(
   istream_iterator<int>(cin),
   istream_iterator<int>(),
   back_inserter<vector<int>>(v));
// 사용자 입력을 받아 v 에 push_back

copy(
   istream_iterator<int>(cin),
   istream_iterator<int>(),
   ostream_iterator<int>(cout, " "));
// 사용자 입력을 받아 cout으로 출력
// ctrl + D 를 누르면 입력 종료

5. 반복자 특성과 보조 함수

  1. 반복자 특성이란?
    • 각 반복자의 특징을 저장하는 템플릿 클래스
    • 사용자 알고리즘 구현 할 때 STL 알고리즘 처럼 일반화하면서 반복자 종류의 특징에 따라 효율적인 동작을 하는 알고리즘을 구현하려면 STL이 제공하는 반복자 특성 활용 필요
  2. iterator_traits
    • 모든 반복자의 공통된 인터페이스
    • 모든 반복자가 제공하는 다섯 정보를 가지고 있음
template<class Iter>
struct iterator_traits{
   typedef typename Iter::iterator_category iterator_category
   typedef typename Iter::value_type value_type;
   typedef typename Iter::difference_type difference_type;
   typedef typename Iter::pointer pointer;
   typedef typename Iter::reference reference;
}
  1. 반복자 태그(5개)
    • 반복자의 종류를 구분하기 위해 사용
struct input_iterator_tag {...};
struct output_iterator_tag{...};
struct forward_iterator_tag
   :public input_iterator_tag{...};
struct bidirectional_iterator_tag
   :public forward_iterator_tag{...};
struct random_access_iterator_tag
   :public bidirectional_iterator_tag{...};
  1. 사용자 함수 구현 예시
//vector
template<typename T>
class Vector{
public:
   class Iterator{
      typedef random_access_iterator_tag iterator_category;
      typedef T value_type;
      typedef int difference_type;
      typedef T* pointer;
      typedef T& reference;
      void operator+=(int) { }
   }
      Iterator Begin() {
      return Iterator();
   }
}

//list
template<typename T>
class List{
public:
   class Iterator{
      typedef bidirectional_iterator_tag iterator_category;
      typedef T value_type;
      typedef int difference_type;
      typedef T* pointer;
      typedef T& reference;
      void operator++() { }
   }
   Iterator Begin() {
      return Iterator();
   }
}

// advance(양방향 반복자) 오버로딩
template<typename Iter>
void _Advance(Iter& iter,
            int n,
            bidirectional_iterator_tag category_tag){
   for(int i = 0; i < n; i++){
      ++iter;
   }
}

// advance(임의 접근 반복자) 오버로딩
template<typename Iter>
void _Advance(Iter& iter,
            int n,
            random_access_iterator_tag category_tag){
   iter += n;
}

// Advance() 반복자 보조 함수
template<typename Iter>
void Advance(Iter& iter, int n){
   _Advance(iter, n, iterator_traits<Iter>::iterator_category());
}

// 사용 예시
Vector<int> v = {10,20,30};
List<int> v = {10,20,30};

Vector<int>::Iterator viter(v.Begin());
List<int>::Iterator liter(lt.Begin());

Advance(viter, 2);
Advance(liter, 2);

6. 보조 함수

  1. advance(p, n)

    • p 반복자를 p += n의 위치로 이동
  2. n=distance(p1, p2)

    • n은 p2 - p1
    • distance(v.begin(),v.end()) = 원소 개수

참고

  1. 뇌를 자극하는 C++ STL
반응형
반응형

1. 바인더

  1. 이항 함수자를 단항 함수자로 변환
  2. STL은 두 가지 바인더 제공
    • bind1st : 첫번 째 인자 고정
    • bind2nd : 두번 째 인자 고정
  3. 예제
    • less 첫 번째 인자를 10으로 고정
   // less의 첫 인자를 10으로 고정한 binder
   binder1st<less<int>> binder = bind1st(less<int>(), 10);
   binder(5); // => less<int>()(10,5) 와 동일

   // 임시 객체로 사용
   bind1st(less<int>(), 10)(5);
  1. c++11 에서 비추 , c++17 에서 삭제됨
    • std::bind를 대신 사용하자.

2. 부정자(negator)

  1. 조건자를 반대의 조건자로 변환
  2. STL은 두 가지 부정자 제공
    • not1 : 단항 조건자를 변환
    • not2 : 이항 조건자를 변환
  3. 예제
    • less 조건자를 반대 조건자로 변환
less<int> oLess;
binary_negate<less<int>> negate = not2(less<int>());
// 아래 세 방법은 모두 동일
negate(5, 10);
not2(oLess)(5,10);
not2(less<int>())(5, 10);
// 5 < 10 의 반대는 5 => 10 이므로 false

3. 함수 포인터 어댑터

  1. 일반 함수를 어댑터 적용 가능한 함수 객체로 변환
    • 일반 함수는 STL 어댑터에 적용 안됨
    • 어댑터에 적용 가능한 함수 객체로 변환
  2. STL은 아래 함수 포인터 어댑터 제공
    • ptr_fun()
  3. 사용 예시
    • 사용자 정의 함수를 변환
bool Pred(int n){
   return 30 <= n && n <= 40;
}

vector<int> v = {10,20,30,40,50};
//30이상 40이하의 원소 개수 => 2
count_if(
   v.begin(),
   v.end(),
   Pred);

// 30이상 40이하가 아닌 원소 개수 => 3
count_if(
   v.begin(),
   v.end(),
   not1(ptr_fun(Pred)));
  1. 사용자 정의 ptr_fun 구현
template<typename RType, typename AType>
class Ptr_fun_class:public unary_function<AType, RType>{
   RType (*pf)(AType);
public:
   Ptr_fun_class(RType (*_pf)(AType))
      : pf(_pf) {}
   RType operator()(AType n) const{
      return pf(n);
   }
}

// 일반 함수를 함수 객체로 변환하는 Ptr_fun() 함수
template<typename RType, typename Atype>
Ptr_func_class<RType,AType> Ptr_fun(
   RType (*pf)(Atype) {
      return Ptr_fun_class<Rtpye, AType>(pf);
   }
)

4. 멤버 함수 포인터 어댑터

  1. 멤버 함수를 함수 객체로 변환
  2. 알고리즘이 객체 원소의 멤버 함수 호출 가능
  3. STL은 두 가지 멤버 함수 포인터 어댑터 제공
    • mem_fun_ref() : 객체로 멤버 함수 호출
    • mem_fun() : 객체의 주소로 멤버 함수 호출
  4. mem_fun_ref() 예시
vector<Point> v;
v.push_back(Point(1,1));
v.push_back(Point(2,2));
v.push_back(Point(3,3));
v.push_back(Point(4,4));
v.push_back(Point(5,5));

// 멤버 함수 호출 불가능
for_each(
   v.begin(), v.end(),
   &Point::Print);

// 멤버 함수 호출 가능
for_each(
   v.begin(), v.end(),
   mem_fun_ref(&Point::Print));
  1. 사용자 정의 Mem_fun_ref 예시
template<typename RType, typename CType>
class Mem_fun_ref_class:public unary_function<CType, RType>{
   RType (CType::*pf)() const;
public:
   Mem_fun_ref_class(RType (CType::*_pf)() const)
      : pf(_pf) {}
   RType operator()(const CType& o) const{
      return (o.*pf)();
   }
}

// 어댑터 함수 : 멤버 함수를 주소를 저장하는 함수 객체로 반환
template<typename RType, typename CType>
Mem_fun_ref_class<RType, CType> Mem_fun_ref(
   RType (CType::*pf() const){
      return Mem_fun_ref_class<RType,CType>(pf);
   }
)
  1. mem_fun() 어댑터 예시
    • 원소가 객체의 주소 일 때 사용
vector<Point*> v;
v.push_back(new Point(1,1));
v.push_back(new Point(2,2));
v.push_back(new Point(3,3));
v.push_back(new Point(4,4));
v.push_back(new Point(5,5));

for_each(
   v.begin(),
   v.end(),
   mem_fun(&Point::Print)
);

참고

  1. 뇌를 자극하는 C++ STL
반응형

'C++ > STL' 카테고리의 다른 글

[STL-18] 컨테이너 어댑터  (0) 2021.03.14
[STL-17] 반복자  (0) 2021.03.14
[STL-15] 함수 객체 - 비교/논리 연산 조건자  (0) 2021.03.14
[STL-14] 함수 객체 - 산술 연산 함수 객체  (0) 2021.03.14
[STL-13] 함수 객체 - 개요  (0) 2021.03.14
반응형

1. STL에서 제공하는 연산 조건자

  1. 비교 연산 조건자
    • 아래 함수 객체는 모두 이항 조건자
함수명 내용
equal_to<T> ==
not _equal_to<T> !=
less<T> <
less_equal<T> <=
greater<T> >
greater_equal<T> >=
  1. 논리 연산 조건자
함수명 내용 인자
logical_and<T> && 이항
logical_or<T> || 이항
logical_not<T> ! 단항

2. 연산 조건자 사용 법

  1. less<T>
    • 헤더 추가 : <functional>
    • 일반적으로 아래 방법 사용
    • less<int>()(10, 20);
less<int> oLess;   // 객체 생성

// 1. 암묵적 호출
oLess(10, 20);

// 2. 명시적 호출
oLess.operator()(10,20);

// 3. 임시 객체로 암묵적 호출(일반적인 사용)
less<int>()(10,20);

// 4. 임시 객체로 명시적 호출
less<int>().operator()(10,20);
  1. logical_and
    • 헤더 추가 : <functional>
int n = 30;
logical_and<bool> oAnd;

// 1. 암묵적 호출
oAnd(
   greator<int>()(n,10),
   less<int>()(n, 50)
);
// n이 10보다 크고, 50 보다 작은가? true

// 2. 명시적 호출
oAnd.operator()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

// 3. 임시 객체로 암묵적 호출(일반적 사용)
logical_and<bool>()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

// 4. 임시 객체로 명시적 호출
logical_and<bool>().operator()(
   greator<int>()(n,10),
   less<int>()(n, 50)
);

3. 사용자 정의 구현

  1. less
    • binary_function 상속
    • 첫번째 , 두번째 인자 : T
    • 리턴 인자 : bool
    • operator 함수는 const
template<typename T>
struct Less: public binary_function<T,T,bool>{
   bool operator()(const T& left, const T& right) const{
      return left < right;
   }
};

2. logical_and
```cpp
template<typename T>
struct Logical_and: public binary_function<T,T,bool>{
   bool operator()(const T& left, const T& right) const{
      return left && right;
   }
}

4. 알고리즘과 같이 사용하는 예

  1. count_if 로 같이 사용 예
    • count_if는 단항 조건자를 요구
    • bind2nd<T> 어댑터 사용하여 이항 조건자를 단항 조건자로 변경
vector<int> v = {10,20,30,40,50};
// 1. 20보다 작은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<less<int>>(
      less<int>(), 20
      )
);
// 1개

// 2. 20보다 작거나 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<less_equal<int>>(
      less_equal<int>(), 20
      )
);
// 2 개

// 3. 20보다 큰 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<greater<int>>(
      greater<int>(), 20
      )
);
// 3개

// 4. 20보다 크거나 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<greater_equal<int>>(
      greater_equal<int>(), 20
      )
);
// 4개

// 5. 20과 같은 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<equal_to<int>>(
      equal_to<int>(), 20
      )
);
// 1 개

// 5. 20과 다른 원소 개수
count_if(
   v.begin(),
   v.end(),
   bind2nd<not_equal_to<int>>(
      not_equal_to<int>(), 20
      )
);
// 4 개

참고

  1. 뇌를 자극하는 C++ STL
반응형

'C++ > STL' 카테고리의 다른 글

[STL-17] 반복자  (0) 2021.03.14
[STL-16] 함수 객체 - 함수 어댑터  (0) 2021.03.14
[STL-14] 함수 객체 - 산술 연산 함수 객체  (0) 2021.03.14
[STL-13] 함수 객체 - 개요  (0) 2021.03.14
[STL-12] 알고리즘7-수치 알고리즘  (0) 2021.03.14
반응형

1. STL에서 제공하는 산술 연산 함수 객체

함수명 내용 인자
plus<T> 더하기 이항
minus<T> 빼기 이항
multiplies<T> 곱하기 이항
divides<T> 나누기 이항
modulus<T> 나머지 이항
negate<T> 부호 변경 단항

2. 사용 법

  1. plus<T>
    • 헤더 추가 : <functional>
    • 일반적으로 아래 방법 사용
    • plus<int>()(10, 20);
plus<int> Plus;   // 객체 생성

// 1. 암묵적 호출
oPlus(10, 20);

// 2. 명시적 호출
oPlus.operator()(10,20);

// 3. 임시 객체로 암묵적 호출(일반적인 사용)
plus<int>()(10,20);

// 4. 임시 객체로 명시적 호출
plus<int>().operator()(10,20);

3. 알고리즘과 같이 사용하는 예

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {1,2,3,4,5};
vector<int> v3(5);

//1. plus<int>()
transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), plus<int>());
// v3 = {11,22,33,44,55}

//2. multiplies<int>()
transform(v1.begin(), v1.end(), v2.begin(), v3.begin(), multiplies<int>());
// v3= {10, 40, 90,  160, 250}

//3. negate<int>() : 부호 변경
transform(v1.begin(), v1.end(), v3.begin(), negate<int>());
// v3 = {-10, -20, -30, -40, -50}

// 4. minus<int>() + 인접 원소와의 차이
adjacent_difference(
   v1.begin(),
   v1.end(),
   v3,begin(),
   minus<int>()
);
// v3 = {10, 10, 10, 10, 10}

// 5.multiplies<int>() + 곱 누적
partial_sum(
   v1.begin(),
   v1.end(),
   v3.begin(),
   multiplies<int>()
);
// v3 = {10, 200, 6000, 240000, 12000000}

// 6.multiplies<int>() + 모든 원소 곱
int mul = accumulate(
   v1.begin(),
   v1.end(),
   1,
   muliplies<int>()
);
// mul = 12000000

참고

  1. 뇌를 자극하는 C++ STL
반응형
반응형

1. 용어 정리

  1. 함수 객체란?
    • operator() 연산자를 오버로딩한 클래스 객체
    • 다른 이름으로 functor(함수자)라고 불림
  2. 함수류 : 함수 객체, 함수, 함수 포인터

2. 함수 객체 종류

  1. 일반 함수 객체 : 특정 기능을 수행

    • 산술 연산 함수 객체 : 산술 연산 기능 수행
    • 비교 연산 함수 객체 조건자 : 비교 조건자
  2. 함수 어댑터 : 함수류를 인자로 받아 다른 함수 객체로 변환

    • 바인더: 이항 함수 객체를 단항 함수 객체로 변환
    • 부정자 : 함수 객체 조건자를 반대로 변환
    • 함수 포인터 어댑터 : 함수 포인터를 STL이 요구하는 함수 객체로 변환
    • 멤버 함수 포인터 어댑터 : 멤버 함수 포인터를 함수 객체로 변환

3. 조건자

  1. bool 형식을 반환하는 함수류
    • 함수 객체 조건자
    • 함수 조건자
    • 함수 포인터 조건자
  2. STL에서 조건자?
    • 모두 함수 객체 조건자
    • 조건자는 객체의 상태값을 변경할 수 없음
    • operator() 연산자 오버로딩 함수는 모두 const

4. 어댑터

  1. 함수 객체를 다른 함수 객체로 변환할 때 사용
  2. 어댑터 인자로 사용되는 단항 함수 필요 조건
    • argument_type 정의 필요
    • result_type 정의 필요
  3. 어댑터 인자로 사용되는 이항 함수 필요 조건
    • first_argument_type 정의
    • second_argument_type 정의
    • result_type 정의
template<typename T>
struct Plus{
   typedef T first_argument_type;
   typedef T second_argument_type;
   typedef T result_type;

   T operator()(const T& left, const T& right) const{
      return left + right;
   }
};

vector<int> v1 = {10,20,30};
vector<int> v3(3);

// Plus 함수를 단항 함수로 변경
transform(
   v1.begin(),
   v1.end(),
   v3.begin(),
   binder1st<Plus<int>> (Plus<int>(), 100)
   );
// v3 = {110, 120 , 130}
  1. 단항, 이항 함수 형식 정의 방법
    • 위 조건 정의 대신 아래 클래스 상속
    • unary_function : 단항 함수 정의시
    • binary_function : 이항 함수 정의시
template<typename T>
struct Plus: public binary_function<T,T,T>{
   T operator()(const T& left, const T& right) const{
      return left+right;
   }
};

vector<int> v1 = {10,20,30};
vector<int> v3(3);

// Plus 함수를 단항 함수로 변경
transform(
   v1.begin(),
   v1.end(),
   v3.begin(),
   binder1st<Plus<int>> (Plus<int>(), 100)
   );
// v3 = {110, 120 , 130}

참고

  1. 뇌를 자극하는 C++ STL
반응형
반응형

0. 수치 알고리즘

  1. <numeric> 헤더에 포함됨

1. 수치 리스트

알고리즘 설명
x2=accumulate(b,e,x) x2는 x를 초기값으로 시작한 구간 [b,e) 순차열 원소의 합
x2=accumulate(b,e,x,f) x2는 x를 초기값으로 시작한 구간 [b,e) 순차열 원소의 누적. f를 누적에 사용
x2=inner_product(b,e,b2,x) x2는 x를 초기값으로 시작한 구간 [b,e)와 구간 [b2,b2+e-b)의 내적(두 순차열의 곱의 합)
x2=inner_product(b,e,b2,x,f1,f2) x2는 x를 초기값으로 시작한 구간 [b,e)와 구간 [b2,b2+e-b)의 모든 원소끼리 f2 연산 후 f1연산으로 총 연산한 결과
p=adjacent_difference(b,e,t) 구간 [b,e)의 인접 원소와의 차를 순차열 [t,p)에 저장
p=adjacent_difference(b,e,t,f) 구간 [b,e)의 인접 원소와의 연산을 순차열 [t,p)에 저장. f를 연산에 사용
p=partial_sum(b,e,t) 구간 [b,e)의 현재 원소까지의 합을 순차열 [t,p)에 저장
p=partial_sum(b,e,t,f) 구간 [b,e)의 현재 원소까지의 연산을 순차열 [t,p)에 저장. f를 연산에 사용

2. 상세 내용

  1. accumulate(b,e,x)
    • 순차열 원소의 합을 구함
vector<int> v = {10,20,30,40,50};
int sum = accumulate(v.begin(), v.end(), 0);
// sum = 150 = 0+10+20+30+40+50

int sum2 = accumulate(v.begin(), v.end(), 100);
// sum = 250 = 100+10+20+30+40+50+
  1. accumulate(b,e,x,f)
    • 순차열 원소에 f함수 적용 가능
    • f는 이항 함수
    • 함수에 따라 누적합,누적곱 등 연산 가능
// 1. Functor
template<typename T>
struct Plus{
   T operator() (const T& left, const T& right){
      return left+right;
   }
};

// 2. 클라이언트
void main(){
   vector<int> v = {1,2,3,4,5};
   // 사용자가 정의한 합함수
   int a = accumulate(v.begin(), v.end(), 0, Plus<int>());
   // a = 15 = 0+1+2+3+4+5

   // stl multiplies
   int mul = accumulate(v.begin(), v.end(), 1, multiplies<int>());
   // mul = 120 = 1 * 1 * 2 * 3 * 4 * 5
}
// 3. 서버
T accumulate(Iterator first, Iterator last, T x, Function fun){
   T ret = x;
   for(Iterator p = first; p != last ; ++p){
      ret = fun(ret, *p);
   }
   return ret;
}
  1. inner_product(b,e,b2,x)
    • 두 순차열의 내적 계산
vector<int> v1 = {1,2,3,4,5};
vector<int> v2 = {2,2,2,2,2};

int in = inner_product(v1.begin(), v1.end(), v2.begin(), 100);
// in = 130 = 100 + 1*2 + 2*2 + 3*2 + 4*2 + 5*2
  1. inner_product(b,2,b2,x,f1,f2)
    • 다양한 원소 간의 연산과 누적 연산 수행 가능
    • 두 순차열의 원소끼리의 차이의 합을 계산하는 예제
int Plus(int left, int right){
   return left+right;
}

int Minus(int left, int right){
   return left-right;
}

vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {2,2,2,2,2};

int a = inner_product(
   v1.begin(), v1.end()
   , v2.begin(), 0, Plus, Minus);
// a = 140 = 0 + 10 -2 + 20 - 2 + 30 -2 + 40 -2 + 50 - 2

//서버 예시
T inner_product(Iter first, Iter first2, T x, Func1 fun1, Func2 fun2){
   T ret = x;
   for(Iter p = first, q = first2; p != last; ++p, ++q){
      ret = fun1(ret, fun2(*p,*q))
   }
   return ret;
}
  1. adjacent_difference(b,e,t)
    • 순차열에서 연속한 원소 간의 차 계산
vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);
auto iter = adjacent_difference(
   v1.begin(), v1.end(), v2.begin()
);
// v2 = {10, 10, 10, 10, 10}
// 1번 10 => 10
// 2번 10 => 20 - 10
// ...
// iter - 1 = > 마지막 10을 가리킴
  1. adjacent_difference(b,e,t,f)
    • 인접 원소와의 사용자 정의 함수 수행
    • EX) 인접 원소 합을 저장
int Plus(int left, int right){
   return left + right;
}

vector<int> v1 = {10,20,30,40,50}
vector<int> v2(5);
auto iter = adjacent_difference(
   v1.begin(), v1.end(), v2.begin(), Plus
);
// v2 = {10, 30, 50, 70, 90}
// 10 => 10
// 30 => 10 + 20
// ...
// iter - 1 = 90을 가리킴
  1. partial_sum(b,e,t)
    • 순차열에서 시작부터 매 현재 원소까지의 합을 구함
vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);

auto iter = partial_sum(
   v1.begin(), v1.end(), v2.begin()
);
// v2 = {10, 30, 60, 100, 150}
// 10 => 10
// 30 => 10 + 20
// 60 => 10 + 20 + 30
// ...
// iter - 1 => 150을 가리킴
  1. partial_sum(b,e,t,f)
    • 순차열에서 시작부터 매 현재 원소까지의 사용자 정의 연산을 수행함
int Multi(int left, int right){
   return left * right;
}

vector<int> v1 = {10,20,30,40,50};
vector<int> v2(5);

auto iter = partial_sum(v1.begin(), v1.end(), v2.begin(), Multi);
// v2 = { 10, 200, 6000, 240000, 12000000}
// 10 => 10
// 200 => 10 * 20
// 6000 => 10 * 20 * 30
// ...
// iter - 1 => 12000000을 가리킴

참고

  1. 뇌를 자극하는 C++ STL
반응형
반응형

0. 정렬된 범위 알고리즘

  1. 정렬된 구간에서만 동작하는 알고리즘
  2. 원소가 같음 비교시 a==b 연산 사용 안함
  3. 원소가 같은 비교시 !(a<b) && !(b<a) 사용

1. 정렬 알고리즘 리스트

알고리즘 설명
binary_search(b,e,x) 구간 [b,e)의 순차열에 x와 같은 원소가 있는가?
binary_search(b,e,x,f) 구간 [b,e)의 순차열에 x와 같은 원소가 있는가? f를 비교에 사용
includes(b,e,b2,e2) 구간 [b2,e2)의 모든 원소가 구간 [b,e)에도 있는가?
includes(b,e,b2,e2,f) 구간 [b2,e2)의 모든 원소가 구간 [b,e)에도 있는가? f를 비교에 사용
p=lower_bound(b,e,x) p는 구간 [b,e) 순차열에서 x와 같은 첫 원소의 반복자
p=lower_bound(b,e,x,f) p는 구간 [b,e) 순차열에서 x와 같은 첫 원소의 반복자. f는 비교에 사용
p=upper_bound(b,e,x) p는 구간 [b,e) 순차열에서 x 보다 큰 첫 원소의 반복자
p=upper_bound(b,e,x,f) p는 구간 [b,e) 순차열에서 x 보다 큰 첫 원소의 반복자. f를 비교에 사용
pair(p1,p2)=equal_range(b,e,x) 구간 [p1,p2)의 순차열은 구간 [b,e)의 순차열에서 x와 같은 원소의 구간. [lower_bound(), upper_bound())의 순차열과 같음
pair(p1,p2)=equal_range(b,e,x,f) equal_range(b,e,x)와 동일. f를 비교에 사용
p=merge(b,e,b2,e2,t) 구간[b,e)의 순차열과 구간 [b2,e2)의 순차열을 합병해 [t,p)에 저장
p=merge(b,e,b2,e2,t,f) merge(b,e,b2,e2,t)과 동일. f를 비교에 사용
inplace_merge(b,m,e) 정렬된 [b,m) 순차열과 [m,e) 순차열을 [b,e)순차열로 합병
inplace_merge(b,m,e,f) inplace_merge(b,m,e,f)와 동일. f를 비교에 사용
p=set_union(b,e,b2,e2,t) 구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 합집합으로 [t,p)에 저장
p=set_union(b,e,b2,e2,t,f) set_union(b,e,b2,e2,t)와 동일. f를 비교에 사용
p=set_intersection(b,e,b2,e2,t) 구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 교집합으로 [t,p)에 저장
p=set_intersection(b,e,b2,e2,t,f) set_intersection(b,e,b2,e2,t)과 동일. f를 비교에 사용
p=set_difference(b,e,b2,e2,t) 구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 차집합 [t,p)에 저장
p=set_difference(b,e,b2,e2,t,f) set_difference(b,e,b2,e2,t)과 동일. f를 비교에 사용
p=set _symmetric_difference(b,e,b2,e2,t) 구간 [b,e)의 순차열과 [b2,e2)의 순차열을 정렬된 대칭 차집합으로 [t,p)에 저장
p=set _symmetric_difference(b,e,b2,e2,t,f) set _symmetric_difference(b,e,b2,e2,t)와 동일. f를 비교에 사용

2. 상세 예시

  1. binary_search(b,e,x)

    • 구간 [b,e)에서 x와 같은 원소가 있음 true
vector<int> v = {10,20,30,40,50};
bool b = binary_search(v.begin(), v.end(), 20);
// b = true
  1. binary_search(b,e,x,f)
    • f를 조건자(이항 함수)로 사용하여 찾음
bool Pred(int left, int right){
   return 3 < right - left;
} // 오른쪽이 왼쪽보다 3보다 크면 참

vector<int> v = {40,46,12,80,10,47,30,55,90,53};
sort(v.begin(), v.end(), Pred);
// 조건자에 의한 정렬
// v = {12,10,30,40,46,47,55,53,80,90}
// 12와 10의 차이가 3보다 작기 때문에 12가 앞
// 55와 53의 차이가 3보다 작기 때문에 55가 앞

bool b = binary_search(v.begin(), v.end(), 32, Pred);
// b = true
// !Pred(30,32) => true 이고,
// !Pred(32,30) => true 이므로,
// 참조건 (!Pred(30,32)&&!Pred(32,30)) = true
  1. includes(b,e,b2,e2)
    • [b,e) 에 [b2,e2)가 포함되면 true
vector<int> v = {10,20,30,40,50};
vector<int> v2 = {10,20,40};
vector<int> v3 = {10,20,60};

bool b1 = includes(v1.begin(), v1.end()
                  ,v2.begin(), v2.end());
// b1 = true
// v2는 v에 포함되므로

bool b2 = includes(v1.begin(), v1.end(), v2.begin(), v2.end());
// b2 = false
// v3의 60은 v에 포함되지 않으므로

//조건자 사용
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
b1 = includes(v1.begin(), v1.end()
            , v2.begin(), v2.end()
            , greater<int>())
  1. lower _bound, upper _bound, equal_range
    • 찾는 원소가 여러 개 일 때 반복자 반환
    • lower_bound : 첫 원소의 반복자 반환
    • upper_bound : 마지막 다음 원소 반복자 반환
    • equal_range : [lower_bound, upper_bound) pair 반환
vector<int> v = {10,20,30,30,30,40,50};

auto lower = lower_bound(v.begin(), v.end(), 30);
auto upper = upper_bound(v.begin(), v.end(), 30);
auto eual = equal_range(v.begin(), v.end(), 30);
// lower = 첫 30을 가리킴
// upper = 마지막 30의 다음 40을 가리킴
// eqaul = (lower,upper)의 pair 형태
  1. merge(b,e,b2,e2,t)
    • 정렬된 두 순차열을 목적지 순차열로 병합
vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {20,30,60};
vector<int> v3(10);

auto iter = merge(v1.begin(), v1.end()
                 ,v2.begin(), v2.end()
                 ,v3.begin());
// v3 = {10,20,20,30,30,40,50,60,0,0};
// iter -1 => 60을 가리킴
  1. inplace_merge(b,m,e)
    • 하나의 순차열이 두 구간으로 정렬되어 있을 때
    • 하나의 구간으로 정렬 가능
vector<int> v = {10,20,30,40,50,20,30,60};
// v => 10,20,30,40,50 과
// 20,30,60 의 두 개의 구간으로 정렬되어 있음

inplace_merge(v.begin(), v.begin()+5, v.end());
// v = {10,20,20,30,30,40,50,60} 으로 정렬됨

3. 집합 관련 알고리즘

  1. set_union(b,e,b2,e2,t)
    • 두 순차열의 합집합을 구함
  2. set_intersection(b,e,b2,e2,t)
    • 두 순차열의 교집합을 구함
  3. set_difference(b,e,b2,e2,t)
    • 두 순차열의 차집합을 구함
  4. set_ symmetric_difference(b,e,b2,e2,t)
    • 두 순차열의 대칭 차집합을 구함
vector<int> v1 = {10,20,30,40,50};
vector<int> v2 = {20,30,60};
vector<int> v3(10);

// 1. 합집합
auto iter = set_union(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,20,30,40,50,60,0,0,0,0}
// iter - 1 => 60을 가리킴

// 2. 교집합
auto iter = set_intersection(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {20,30,0,0,0,0,0,0,0,0}
// iter - 1 => 30을 가리킴

// 3.차집합
auto iter = set_difference(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,40,50,0,0,0,0,0,0,0}
// iter - 1 => 50을 가리킴

// 4. 대칭 차집합
auto iter = set_symmetric_difference(
   v1.begin(), v1.end()
  ,v2.begin(), v2.end()
  ,v3.begin());
// v3 = {10,40,50,60,0,0,0,0,0,0}
// iter - 1 => 60을 가리킴

참고

  1. 뇌를 자극하는 C++ STL
반응형
반응형

0. 정렬 알고리즘

  1. 변경 알고리즘의 특수한 형태
  2. 특정 정렬 기준으로 원소의 순서를 변경 및 정렬

1. 정렬 알고리즘 리스트

알고리즘 설명
make_heap(b,e) 힙을 생성. 구간 [b,e)의 순차열을 힙 구조로 변경
make_heap(b,e,f) make_heap(b,e)와 동일. f는 조건자로 비교에 사용.
push_heap(b,e) 힙에 원소 추가. push_back와 같이 사용. 구간 [b,e)의 순차열을 다시 힘 구조가 되게 함.
push_heap(b,e,f) push_heap(b,e)와 동일. f는 조건자로 비교에 사용
pop_heap(b,e) 힙에서 원소 제거. 구간 [b,e)의 순차열의 가장 큰 원소(첫 원소)를 제거.
pop_heap(b,e,f) pop_heap(b,e)와 동일. f는 조건자로 비교에 사용.
sort_heap(b,e) 힙을 정렬. 구간 [b,e)의 순차열을 힙 구조를 이용해 정렬
sort_heap(b,e,f) sort_heap(b,e)와 동일. f는 조건자로 비교에 사용
nth_element(b,m,e) 구간 [b,e)의 원소 중 m-b개 만큼 선별된 원소를 [b,m) 순차열에 놓이게 함
nth_element(b,m,e,f) nth_element(b,m,e) 와 동일. f는 조건자로 비교에 사용
sort(b,e) 구간 [b,e)를 퀵 정렬 기반으로 정렬
sort(b,e,f) sort(b,e) 와 동일. 조건자 f를 사용해 정렬.
stable_sort(b,e) 구간 [b,e)를 머지 정렬을 기반으로 정렬. 값이 같은 원소의 상대적 순서 유지.
stable_sort(b,e,f) stable_sort(b,e)와 동일. f는 조건자로 비교에 사용.
partial_sort(b,m,e) 힙 정렬 기반으로 정렬. 구간 [b,e) 원소 중 m-b개 만큼 상위 원소를 정렬하여 [b,m) 순차열에 놓음
partial_sort(b,m,e,f) partial_sort(b,m,e) 와 동일. f는 조건자로 비교에 사용.
partial _sort_copy(b,e,b2,e2) 힙 정렬 기반으로 정렬. 구간 [b,e) 원소 중 상위 e2-b2개의 원소만 정렬하여 [b2,e2)로 복사
partial _sort_copy(b,e,b2,e2,f) partial _sort_copy(b,e,b2,e2)와 동일. f는 조건자로 비교에 사용.

2.힙 관련 알고리즘

  1. 자료 구조 힙
    • 완전 이진 트리로 구성
    • 트리 내의 모든 원소가 부모 노드보다 큰 값(또는 작은 값)을 가짐
    • 루트 노드는 항상 가장 작은 값(또는 가장 큰 값)을 가짐
    • 최대값, 최소값 연산이 빠름
  2. 힙의 연산
    • 추가 연산
      • 완전 이진 트리 가장 끝에 원소 추가
      • 힙의 규칙을 깨지 않게 교환하여 힙을 유지
    • 제거 연산
      • 루트 노드를 삭제
      • 삭제된 루트 노드에 힙의 마지막 노드 가져옴
      • 힙의 규칙 깨지 않게 교환하여 힙을 유지
  3. heap 예제
    • min heap : v = {1,3,2,4,6,5}
    • max heap : v = {6,5,3,4,2,1}
  4. make_heap(b,e)
    • 구간 [b,e)의 순차열을 힙 구조로 만듦
vector<int> v = {10,20,30,40,50,60};
// 1. 최대 heap 생성
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}

// 2. 최소 heap 생성
make_heap(v.begin(), v.end(), greater<int>());
// v= {10,20,50,30,40,60}
  1. push_heap(b,e)
    • 원소가 추가된 상태에서 사용
    • 추가된 구간 [b,e) heap을 교환하여 heap을 유지함.
    • 일반적으로 push_back()과 함께 사용
//위의 예제 수행 후
v.push_back(35);
// 마지막에 단순 원소 추가
// v = {60,50,30,40,20,10,35}
push_heap(v.begin(), v.end());
// v = {60,50,35,40,20,10,30}
// heap 형태를 재계산
  1. pop_heap(b,e)
    • root node를 (논리적)제거(제일 마지막으로 이동)
    • 원리
      • root node와 마지막 node를 교환
      • heap을 유지하도록 교환 반복
vector<int> v = {10,20,30,40,50,60};
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}
pop_hep(v.begin(), v.end());
// v= {50,40,30,10,20,60}
  1. sort_heap(b,e)
    • 구간 [b,e)를 heap 정렬
    • 구간 [b,e)가 heap 구조여야 함
vector<int> v = {10,20,30,40,50,60};
make_heap(v.begin(), v.end());
// v = {60,50,30,40,20,10}
sort_heap(v.begin(), v.end());
// v= {10,20,30,40,50,60}

3. 기타 정렬 알고리즘 상세

  1. nth_element(b,m,e)
    • 전체 구간 [b,e) 에서 구간 [b,m) 만큼의 순차열을 부분적으로 정렬
    • 주로 n 개의 요소를 선별할 때 사용
    • 또는 n 번째 요소가 필요할 때 사용
vector<int> v = {10,30,20,40,50,60};
nth_element(v.begin(), v.begin() + 1, v.end());
// 두번째로 작은 값 : v[1] = 20
  1. sort(b,e)
    • 퀵 정렬을 기반으로 정렬
vector<int> v = {5,1,3,2,7,9,8};
//오름차순 정렬(less: defualt)
sort(v.begin(), v.end());
// v = {1,2,3,5,7,8,9}

//내림차순 정렬(greater)
sort(v.begin(), v.end(), greater<int>());
// v = {9,8,7,5,3,2,1}
  1. stable_sort(b,e)
    • 머지 정렬을 기반으로 정렬
    • 같은 원소의 상대적인 순서를 유지할 때 사용
vector<int> v= {30,50,30,20,40,10,40};
//오름차순 정렬(less: defualt)
stable_sort(v.begin(), v.end());
// v = {10,20,30,30,40,40,50}

//내림차순 정렬(greater)
stable_sort(v.begin(), v.end(), greater<int>());
// v = {50,40,40,30,30,20,10}
  1. partial_sort(b,m,e)
    • heap정렬 기반으로 정렬
    • 순차열의 상위 구간만 정렬할 때 사용
    • heap정렬의 특징이 필요할 때 사용
    • m과 e가 같다면 전체 원소를 정렬함
vector<int> v = {10,30,20,40,50,60};
partial_sort(v.begin(), v.begin() + 3, v.end());
// v.begin() 부터 3개까지만 heap 정렬함
// v = {10,20,30,40,50,60}
  1. partial _sort_copy(b,e,b2,e2)
    • 구간 [b,e) 를 heap정렬 하고,
    • 구간 [b2,e2)에 정렬 결과를 저장함.
vector<int> v = {10,30,20,40,50,60};
vector<int> v2(3);
partial_sort_copy(v.begin(), v.end(), v2.begin(), v2.end());
// v.begin() 부터 3개까지만 heap 정렬함
// v2 = {10,20,30}

참고

  1. 뇌를 자극하는 C++ STL
  2. https://velog.io/@nninnnin7/HEAP
반응형

+ Recent posts

반응형