STL 특징

STL 특징

February 18, 2020 ( last updated : February 17, 2020 )
stl

https://github.com/gmm117/gmm117.github.io

Abstract

    표준 라이브러리
    유틸리티
    컨테이너
    반복자
    알고리즘
    STL컨테이너
    함수객체
    스트링
    STL 추가적으로 알아낸 내용

표준 라이브러리

단일 인자를 갖는 생성자가 자동 형 변환이 일어나는 것을 막기 위해 사용되는 키워드이다.

class Stack

{

explicit Stack(int nSize){}

}

Stack s1(40) - O

Stack s2 = 40 - X

-> 아래 4가지 캐스팅을 사용함으로써 타입 변환의 의도를 명확히 할 수 있다는 장점을 가지고 있다.

캐스팅이 묵시적으로 일어나는 경우 이를 명시적으로 형변환하겠다라고 분명히 해주는 용도로 쓰인다. 묵시적 캐스트(implicit cast)와 일차적으로 동일하나, 논리적으로 변환 가능한 타입만 변환해준다. 클래스의 경우엔 상속 관계를 따져보고 변환하며 상호호환 관계가 아니라면 컴파일 에러를 발생시켜 개발자가 에러를 쉽게 찾을 수 있게 해준다. (실수형의 변수를 정수형으로 캐스팅하거나 반대로 실수형 변수를 정수형으로 캐스팅하는 것은 허용된다. 또한 상호 호환되는 열거형과 정수형과의 변환, double과 float의 변환 등도 허용된다. 그러나 포인터의 타입을 다른 것으로 변환하는 것은 허용되지 않으며 컴파일 에러로 처리된다. )

char c = ‘A’;

char* pc = &c;

int* pi = pc; // int* pi = static_cast<int*>(pc); (X)

dynamic_cast 연산자는 포인터끼리 또는 레퍼런스끼리 변환하는데 사용한다. 포인터를 레퍼런스로 바꾸거나 레퍼런스를 포인터로 변환하는 것은 상식적으로 필요하지도 않고 가능하지도 않다. 포인터끼리 변환할 때도 반드시 상속 계층에 속한 클래스끼리만 변환할 수 있다. int *를 char *로 변환하거나 Parent *를 int *로 변환하는 것은 안된다.

부모 자식간을 변환할 때 업 캐스팅은 원래부터 허용되는 것이므로 이 캐스트 연산자가 있으나 없으나 당연히 가능하다. 문제는 부모 타입의 포인터를 자식 타입의 포인터로 다운 캐스팅할 때인데 이때는 무조건 변환을 허용하지 않고 안전하다고 판단될 때만 허용한다. 안전한 경우란 변환 대상 포인터가 부모 클래스형 포인터 타입이되 실제로 자식 객체를 가리키고 있을 때 자식 클래스형 포인터로 다운 캐스팅할 때이다. 말이 좀 복잡한데 실제로 가리키고 있는 객체의 타입대로 캐스팅했으므로 이 포인터로 임의의 멤버를 참조해도 항상 안전하다.

반대로 부모 클래스형 포인터가 부모 객체를 가리키고 있는 상황일 때 자식 클래스형으로의 다운 캐스팅은 안전하지 않은 변환이다. 왜냐하면 부모 객체를 다운 캐스팅해서 자식 객체를 가리키는 포인터에 대입한 후 이 포인터로 자식에게만 있는 멤버를 참조할 수도 있기 때문이다. dynamic_cast 연산자는 이럴 경우 캐스팅을 허용하지 않고 NULL을 리턴하여 위험한 변환을 허가하지 않는다.

class Person { ~ }; class Child { ~ }; void main() { Person p = new Child(); - (O) Child1 *ch1 = dynamic_cast<Child1>(p); - (O) : Down Cast는 가능 UpCast는 못하게 막아줌 }

char c = ‘A’;

char* pc = &c;

int* pi = reinterpret_cast<int*>(pc); (O)

reinterpret_cast와 () 차이는 reinterpret_cast는 포인터끼리, 포인터와 수치형과의 변환에 대해 수행할 수 있다는 것과 const, volitile 타입의 포인터 타입에 대해서는 캐스팅을 수행할 수 없다는 것이다.

유틸리티

예) pair<int, char>(42, ‘*’)

  make_pair((42, '*')

예) auto_ptr prt1(new Class A) -> ClassA* a = new ClassA();

예) auto_ptr prt1(new Class A) - O, auto_ptr ptr2 = new ClassA; - X

예문)

std::auto_ptr ptr1(new ClassA);

std::auto_ptrptr2(ptr1)

-> 1. ptr1은 new 연산자에 의해서 생성된 객체의 소유권 가짐

 2. 객체의 대한 소유권이 ptr1에서 ptr2로 넘어간다.

std::auto_ptr ptr1(new ClassA);

std::auto_ptr ptr2(new ClassA);

prt2 = ptr1;

-> auto_ptr할당 > ptr2가 소유한 객체를 소멸 > 소유권을 ptr1에서 prt2로 이전

std::auto_ptr ptr;

ptr = new ClassA; - X

ptr = std::auto_ptr(new ClassA);

->1. 클래스 안에서 auto_ptr을 사용함으로써 사용자는 리소스 릭을 피할 수 있다.

2. 왜냐하면 멤버가 소멸됨에 따라서 auto_ptr의 소멸자가 자동으로 소멸을 해주기 때문이다.

예)

class ClassB

{

private:

const std::auto_ptr ptr1;

const std::auto_ptr ptr2 :

public:

classB(ClassA val1, ClassB val2)

ptr1(new ClassA(val1)), ptr2(new ClassA(val2))

{

}

classB(const ClassB& val2)

ptr1(new ClassA(x.ptr1)), ptr2(new ClassA(x.ptr2))

{

}

const classB& operator=(const Class B& x)

{

*ptr1 = *x.ptr1;

*ptr2 = *x.ptr2;

return *this;

}

-> 소멸자 필요 없음. / 복사 생성자와 할당 연산자는 반드시 작성해주어야한다.

  1. auto_ptr은 소유권을 공유할 수 없다.

  2. auto_ptr은 배열 타입을 지원하지 않는다. - delete[] 가 아닌 delete를 호출하므로

  3. auto_ptr은 범용 스마트 포인터가 아니다.

-> 다른 스마트 포인터가 유용하게 사용될 수 있는 상황을 해결하기 위해서 설계된 것이 아니다.

-> auto_ptr은 레퍼런스 카운트라는 개념을 사용하지 않는다.

  1. auto_ptr은 표준 컨테이너 클래스와 함께 사용될 수 없다.

-> auto_ptr은 표준 컨테이너 클래스의 원소로 사용되지 않는다. 왜냐하면, auto_ptr의 복사와 할당이 이루어진 이후 소스와 싱크가 동등하지 않기 때문이다.

  1. 클래스 auto_ptr 세부사항

1) auto_ptr() : auto_ptr의 값을 0으로 초기화

2) 객체를 소유하지 않은 auto_ptr을 생성

3) get() : auto_ptr이 소유한 객체의 주소를 반환

4) operator*() : auto_ptr이 소유한 객체를 반환한다.

5) release() : auto_ptr이 소유한 객체의 소유권 해제, 객체의 주소를 반환, 객체소유 안할시 NULL 포인터를 반환

6) reset(ptr): auto_ptr이 소유하던 기존의 객체는 삭제된다. *this는 ptr이 참조하는 객체의 소유자가 된다.

                 만약 prt이 널 포인터가 아니라면, new로 생성된 값을 넘겨줘야 한다.
  1. 수치제한의 새로운 개념은 두가지 장점을 가진다.

  1. 최소값, 최대값의 처리 : min, max

  2. 두 값의 교환 : swap

  3. 비교 연산자의 확장(rel_ops)

-> 서로 타입이 달라서 비교할 수 있다는게 이점이다. 하지만 C++ 표준 라이브러리에 의해 제공도는 것이 아니기 때문에 호환성이

  보장되지 않는다.

컨테이너

  1. set : * 원소가 가진 값에 따라 정렬이 되는 컨테이너이다. 값은 값을 지닌 원소들은 하나밖에 존재하지 않음

예제) typedef set IntSet; -> value값에 따라서 기본적인 오름차순 정렬이 된다.

    typedef set<int, greate<int>-> 내가 정의한 함수를 넣어서 정렬을 바꿀수도 있다.

  1. multiset * 중복이 허락된다는 점을 제외하고는 set과 동일, 동일한 값을 지닌 원소들이 동시에 존재할 수 있다.

    * value가 중복될 경우 먼저 삽입된 데이터가 먼저 나오게 된다.

  2. map * key/value를 쌍으로 가지고 있는 컨테이너이다. 각각의 원소들은 정렬 기준의 기본이 되는 키를 가지고 있다.

             * 같은 값을 지닌 키는 단 하나만 존재할 수 있다.

         * 연관배열을 같은 map - 배열의 인덱스를 key처럼 사용이 가능함.

            - 연관배열 : 인덱스로 임의의 타입을 가질 수 있는 배열을 의미한다.

 예제) coll["VAT"] = 0.15;

    coll[“PI”] = 3.14;

             coll["HONG"] = 1030;

         coll["NULL"] = 0;

         * 원소의 키를 변경하고자 한다면 pos->first = "h"; - x

                                                      coll["new_key"] = coll["old_key"];

                                                      replace_key(coll, "old_key", "new_key");

  3. multimap * 중복이 허락된다는 점을 제외하고는 map과 동일, 중복된 키가 허용되지만 map은 중복되면 안된다.

             -> 모든 연관 컨테이너들은 바이너리 트리의 구현을 기반으로 이루어져 있다.

  1. stack : LIFO(last-in-first-out)

  2. queue : FIFO(Fist-in-first-out)

  3. priority queue : 우선순위를 지닌 원소들을 관리하는 컨테이너이다.

1) 원소들은 복사 생성자에 의해서 복사되어 질 수 있어야 한다. 복사된 객체는 원본과 동일해야만 한다.

2) 원소에 대한 요구사항 충족되야함

1) 원소를 복사하는 것은 간단하다.

2) 레퍼런스는 에러가 발생하기 쉽다. 즉, 사용자는 더 이상 존재하지 않은 객체에 대해서 참조하지 않는다는 사실을 보장해 주어야한다.

1) 원소를 복사하는 것은 나쁜 성능을 가져올 수 있다.

2) 같은 객체를 여러 컨테이너에 동시에 관리하는 것이 불가능하다.(복사본이므로)

(예제)

vector coll1; vector coll2;

vector::iterator pos = coll1.begin();

/* 런타임에러

for(int i=0; i<=9; i++) { coll2.push_back(i); }

/* 런타임에러

/* 런타임에러

-> 이러한 복구 능력을 제공하기 위해서는 삽입 연산 전에 현재 컨테이너의 모든원소들에 대한 복사본을 가지고 있어야 한다.

-> push, pop 동작의 경우에는 모든 원소들에 대한 복사본이 필요없다. 이유는 예외가 발생하더라도 컨테이너의 아무런 영향을 끼치지

 않는다.

반복자

1) 후위 삽입 반복자 : 컨테이너 뒷부분에 push_back()을 호출하여 원소를 삽입한다.

                           가능한 컨테이너 : vector, deque, list

2) 전위 삽입 반복자 : 컨테이너 앞부분에 push_front()를 호출하여 원소를 삽입한다.

                           가능한 컨테이너 : deque, list

3) 삽입반복자<inserter(container, pos)> : insert()를 사용하여 pos 위치를 삽입한다.

  1. 스트림 반복자 : 스트림에서부터 읽기와 쓰기가 가능한 반복자

      1) istream_iterator<string>(cin) : 표준 입력 스트림 cin에서부터 읽어드리는 스트림 반복자를 생성한다.

  2) unique_copy() : 알고리즘은 인접한, 중복된 값들을 제거한다.

  3) ostream_iterator<string>(cout, "\n") : 컨테이너 안에 모든 string 원소들을 cout를 호출하여 출력하기 위해 출력-스트림-반복

                                                            자를 생성한다.

  2. 역방향 반복자 :

      1) rbegin() -> 컬렉션의 마지막 위치

   2) rend()  -> 컬렉션의 처음 위치

알고리즘

  1. 원소의 제거
  1. 알고리즘 인자로서의 함수

cout « elem « ’ ‘;

           }
  1. 조건자

1) 단항 조건자

 - find_if() 알고리즘은 주어진 범위에서 단항 조건자가 true을 반환하는 첫번째 원소를 검색하기 위해서 사용된다.

   예) find_if(coll.begin(), coll.end(), isPrime);

        bool isPrime(int number) { return true; }

2) 이항 조건자 : 2개의 아큐먼트의 속성을 비교한다. 이것은 원소가 < 연산자를 제공하지 못하는 경우나 다른 정렬

                      기준을 만들고자 할 경우 필요한 것이다.
  1. 함수-객체

STL컨테이너

=> 2번째는 deque를 리턴하는 함수처럼 선언된 것이므로 1번째꺼로 초기화를 해야한다.

  1. 사이즈와 관련된 동작 : empty(), size(), max_size()

  2. 비교와 관련된 동작 : ==, !=, <, <=, >, >=

    • 비교연산자는 3가지의 규칙에 따라서 정의된다.

      1) 두 컨테이너는 같은 타입을 가지고 있어야만 한다.

      2) 만약 두 컨테이너의 원소들이 같고, 이들의 순서 또한 같다면, 두 컨테이너는 같다.

      3) 다른 컨테이너에 비해 작은 것을 검사하기 위해서 사전방식의 비교가 사용된다.

      • 사전식비교 : 원소 대 원소로 비교하는 것을 의미(알파벳, 숫자순으로 비교함.)
  1. 사이즈와 용량

-> 사용자가 vector 안의 포인터나 레퍼런스, 반복자를 관리하거나 또는 속도가 목표라면 용량을 먼저 확보해 두어야한다.

-> 디폴트 생성자가 제공되는 복잡한 타입에 대해서는 초기화에시간이 걸리기 때문에 초기화를 하는 이유가 재할당이라면 reserve를

  사용해야함
  1. vector 동작들

1) 컨테이너의 앞,끝 쪽으로 삽입과 삭제가 이루어 지는경우

2) 컨테이너의 원소들을 참조하지 않는 경우

3) 컨테이너가 더 이상 사용되지 않을 경우 메모리가 해제되기를 원한 경우

  1. list의 멤버 함수들은 vector와 deque와의 다른점

    • list는 용량과 재할당과 관련된 함수들을 제공하지 않는다.

    • list는 원소를 이동시키기 위한 특별한 멤버함수들을 제공한다. 포인터 값만 재지정하므로 속도가 빠르다.

  2. 원소의 삽입 및 제거

    • List에서는 vector와 deque에 없는 remve와 remove_if를 제공한다. remove를 알고리즘이 아닌 멤버함수로 호출해야한다.

예제)

set c;

c.insert(1); c.insert(2); c.insert(4); c.insert(5); c.insert(6); c.insert(8);

cout « *c.lower_bound(7) « endl; -> 7크거나 같은 값을 찾아서 리턴한다. : 8 cout « *c.equal_range(5).first « endl; -> 5가 삽입될 수 있는 첫번째 : 5 cout « *c.equal_range(5).second « endl; -> 5가 삽입될 수 있는 두번재 : 6

- 모든 연관 컨테이너와 마찬가지로 반복자는 양방향 반복자이다. 그러므로 랜덤액세스 반복자를 요구하는 알고리즘을 사용할 수 없다.

- 반복자의 입장에서 볼 때 컨테이너의 모든 원소들이 상수로 취급된다는 것이다. 값을 수정하는 알고리즘의 종류들로 set, multiset에

  대해서 사용할 수 없다.

- insert 같은 경우에는 반환값이 pair로 반환이 된다. 그 이유는 성공여부를 확인하기 위해서이다. 중복이 허용되지 않으므로

   -> first 멤버는 새롭게 삽입된 원소의 위치, second는 삽입 연산의 성공여부

- set 의 erase는 제거된 원소의 개수를 반환한다. set은 중복이 안되므로 0, 1이 나타나게 될 것이다.

- set<int> coll2(coll1.begin(), coll1.end()); // 다른 set에 오름차순으로 모든 원소들을 할당한다.

- 런타임시에 정렬 기준을 결정

  1. 템플릿의 파라미터로 넣는방법 : map<string, greater > StringFlaoatMap;

  2. 생성자의 인자로 넣는방식(특별한 비교 객체 타입을 가지는 map) - 런타임시 처리된다.

typedef map<string, string, RuntimeStringCmp> StringStringMap; // RuntimeStringCmp->class

  1. set과 map의 차이점

    • map, multimap의 원소는 key/value 쌍으로 되어 있으며 연관 배열처럼 사용할 수 있다.
  1. map에 원소를 전달하는 방법은 크게 3가지로 나뉜다.
1) value_type을 사용 : 암시적인 형 변환을 피하기 위해서 사용자는 value_type를 사용하여 정확한 타입을 전달해야함.

  예) std::map<std::string, float> coll;

       coll.insert(std::map<std::string,float>::value_type("otto", 22.3));

2) pair<> 사용

  예) std::map<std::string, float> coll;

//암시적인 형변환 가능

       coll.insert(std::pair<std::string,float>("otto", 22.3));

//암시적인 형변환 불가능

       coll.insert(std::pair<const std::string,float>("otto", 22.3));

3) make_pair() 사용

  예) std::map<std::string, float> coll;

       coll.insert(std::make_pair("otto", 22.3));

       if(coll.insert(std::make_pair("otto", 22.3)).second) // 새로운 원소의 삽입 결과를 검사한다.

- 사용자는 key 대신 특정 value를 가진 원소를 제거하기 위해서 find() 멤버함수를 사용할 수 없다.

  1. 연관 배열처럼 map을 사용하기

    • 연관 컨테이너들은 일반적으로 원소를 직접적으로 액세스할 수 있는 기능을 제공하지 않는다. 하지만 map은 key값을 직접 액세스가

      가능하다. - 키 변경 가능

    • 반복자로는 키 변경안됨( c.first = 3 (x))

      예) map<string, float> coll;

        coll["otto"] = 7.7; // 이 경우에도 map에 자동적으로 추가가 된다.

    • map을 대입했을 경우

typedef map<string, float> StringFloatMap;

StringFloatMap stocks;

stocks[“BASF”] = 369.50; stocks[“VW”] = 413.50; stocks[“DAIMLER”] = 819.00; stocks[“BMW”] = 834.00;

stocks[“Volkswagen”] = stocks[“VW”]; //Volkswagen key가 추가되고 그 value값은 VW에 있던 value값이 들어가게 됨.

StringFloatMap::iterator pos;

pos = stocks.begin();

for(pos; pos != stocks.end(); pos++) { cout « pos->first « ’ ‘ « pos->second « endl; }

1) invasive 접근방법 : 기능을 제공

- 사용자는 STL 컨테이너가 필요로 하는 인터페이스를 제공해주기만 하면 된다

2) noninvasive 접근방법 : iterator와 같은 반복자를 사용

- 사용자느 알고리즘과 특별한 컨테이너의 상호 인터페이스로 사용되는 특별한 인터페이스를 작성하거나 제공해야한다.

3) wrapper 접근방법

- 내부 자료를 은닉하고 랩퍼 클래스를 작성한다.

=> remove_if(coll2.begin(), coll2.end(), bind2nd(less(), 50)) remove_if 마지막이 bind2nd(less(), 50) true를 반환해야지

 삭제가 된다.

1) value_type을 사용 : 암시적인 형 변환을 피하기 위해서 사용자는 value_type를 사용하여 정확한 타입을 전달해야함.

  coll.insert(std::map<std::string,float>::value_type("otto", 22.3));

2) pair<> 사용

  coll.insert(std::pair<std::string,float>("otto", 22.3))

3) make_pair() 사용

 coll.insert(std::make_pair("otto", 22.3));

STL반복자

  1. 입력 반복자(Input Iterators)
  1. 출력반복자(Output Iterators)
  1. 전방향 반복자(Forward Iterators) : ++iter, iter++
  1. 양방향 반복자(Bidirectional Iterators) : –iter, iter–
  1. 랜덤액세스 반복자
  1. vector 반복자의 증, 감소 문제

template struct iterator_traits // 포인터가 아닐 경우( 반복자 ). { // get traits from iterator _Iter typedef typename _Iter::iterator_category iterator_category; typedef typename _Iter::value_type value_type; // <-- typedef typename _Iter::difference_type difference_type; //반복자간의 거리를 표현하기 위한 타입이다. typedef difference_type distance_type; // retained typedef typename _Iter::pointer pointer; typedef typename _Iter::reference reference; };

template struct iterator_traits<_Ty *> // 포인터일 경우. { // get traits from pointer typedef random_access_iterator_tag iterator_category; typedef _Ty value_type; // <-- typedef ptrdiff_t difference_type; typedef ptrdiff_t distance_type; // retained typedef _Ty *pointer; typedef _Ty& reference; };</CLASS>

함수객체

1) 함수-객체 장점

 + 같은 함수-객체에 대해서 동시에 다른 상태를 가질 수 있다는 것이다.

 + 각각의 함수-객체는 자신만의 타입을 가진다. 사용자는 함수-객체의 타입을 템플릿 인자로 제공할 수 있다.

 + 함수-객체는 함수 포인터보다 빠르다.

  1. 정렬 기준으로서의 함수-객체(사용자가 정렬기준 관련 함수-객체를 만들 수 있다.)

  2. 내부 상태를 가지는 함수-객체

    • generate_n() 알고리즘과 함께 쓰이면서 start로부터 시작해서 연속된 정수형 숫자를 생성해 주는 함수 객체

예제)

class IntSequence { private: int value;

public: IntSequence(int initialValue): value(initialValue) {

} int operator() () { return value++; }

};

int main() { list coll;

generate_n(back_inserter(coll), 9, IntSequence(1));

PRINT_ELEMENTS(coll);

generate(++coll.begin(), –coll.end(), IntSequence(42));

PRINT_ELEMENTS(coll); }

=> reference 대신에 value로 전달된 함수-객체는 개체의 상태를 변경시키지 않는 상수성과 임시 객체성이라는 장점이 있다.

  만약 reference로 전달되었다면 IntSequence(1) 두번 호출이 안될 것이다.

  하지만 함수-객체의 상태를 수정할 경우에 얻는 이득을 얻을 수 없었을 것이다.

1) 함수-객체를 레퍼런스로 전달하는 것이다.

2) for_each() 알고리즘의 반환값을 사용하는 것이다.

  1-1. Reference와 value에 차이

1) generate_n<back_insert_iterator<list >, int, IntSequence&>(back_inserter(coll), 10, seq);

2) generate_n(back_inserter(coll), 10, IntSequence(1));

-> reference를 넘겼으므로 seq의 value값이 저장되며 다시 호출시 저장된 숫자 이후부터 출력

value를 넘겼으므로 IntSequence class의 value값이 저장되지 않는다.

2-1. for_each()의 반환값

1) for_each() 알고리즘은 함수-객체를 반환하는 특별한 속성을 가지고 있다.

2) for_each() 알고리즘의 반환값을 검사함으로써 함수-객체의 상태를 얻어올 수 있다.

3) 조건자와 함수-객체
  1. 함수어댑터
1) mem_fun,mem_fun_ref

  - mem_fun_ref(op) 객체에 대해서 멤버 함수 op()를 호출한다. vector<Person>& coll

  - mem_fun(op) 객체의 포인터에 대해서 멤버 함수 op()를 호출한다. vector<Person*>& coll

 - mem_fun, mem_fun_ref는 반드시 상수멤버함수라는 점을 알아야한다.

  for_each(coll.begin(), coll.end()

    - mem_fun_ref(&Person::print), mem_fun(&Person::print)

 4. 함수어댑터를 위한 사용자 정의 함수객체

     - 함수-객체의 인자와 결과를 위해서 타입 멤버를 제공해야한다.

 5. 조립함수-객체

     - 기존의 다른 컴포넌트에서 새로운 컴포넌트를 만들고자 할 경우 매우 유용하게 사용할 수 있다. 단순한 함수-객체에서 아주

       복잡한 형태의 함수-객체를 생성하는 것을 가능하게 한다.

알고리즘

//5와 같거나 큰 값을 찾아 그 위치를 반환한다.

find_if(vec.begin(), vec.end(), bind2st(std::greater_equal(), 5));

bind2nd 인자를 두 개를 받는 함수를 하나로 받는 함수로 바꾸는 것이다.

sort 같은 함수의 경우 인자가 하나인 함수만을 받기 때문에 2개를 하나로 바꿔주는 bind를 쓰게 된 것이다.

  1. for_each()

    • 수정할 값을 인자로 받는다.

예) void square(int& elem) -> 수정할 값을 인자로 받기 때문에 call_by_reference 참조자로 받아야한다.

   {

elem = elem*elem;

   }

   for_each(coll.begin(), coll.end(), square)

  1. transform

    • 수정된 값을 반환하는 함수를 사용한다.

    • 원소를 직접적으로 수정하기 보다는 새로운 값을 할당하여 반환함으로 약간은 더 느리다.

예) transfrom(coll.begin(), coll.end(), //소스범위

                  coll.begin(), 목적지범위

                  bind2nd(plus<int>(), 10));
  1. 원소의 교체(swap_range)
  1. 새로운 값의 할당(fill)
  1. 생성된 값을 할당

예) generate_n(back_insert(coll), 5, rand); generate(coll.begin(), coll.end(), rand);

  1. 원소의 교체<replace(beg, end, oldValue, newValue>
  1. 원소의 복사 후 교체<replace_copy(beg, end, destBeg, oldValue, newValue)>
  1. 특정 값을 지닌 원소의 제거

1) 시퀀스 안의 원소들을 제거(remove, remove_if)

 - beg,end 범위 안에서 value와 동일한 값을 가지는 원소를 제거한다.

 - 수정된 시퀀스의 논리적인 마지막 위치를 반환한다.

 - 제거된 원소들을 제거되지 않은 다음의 원소로 덮어쓴다.

 - 이 알고리즘은 원소를 수정하기 때문에 연관 컨테이너와는 사용할 수 없다.

2) 원소의 제거 결과를 복사하여 전달<remove_copy(beg,end,destBeg,value), remove_copy_if(beg,end,destBeg,op)>

 - [beg,end)의 소스 범위에서 value와 동일한 값을 가지는 원소를 제거하고 destBeg에 복사한다.

3) 중복된 원소의 제거<unique(beg,end), unique_if(beg,end,op)>

 - [beg,end) 범위에서 연 속 중복인 원소를 제거한다. (연속중복이란, 범위 내에서 자신의 바로 뒤에 위치한 원소를 의미)

 - 수정된 시퀀스의 새로운 논리적인 끝 위치를 반환한다.

 - 제거되지 않은 원소의 순서는 동일하게 유지된다.

 - 알고리즘의 원소를 수정하기 때문에 연관컨테이너를 사용하면 안된다.

4) 중복 원소의 제거 결과를 복사하여 전달<unique_copy(beg, end, destBeg), unique_copy_if(beg, end, destBeg, op)>

 - [beg,end)의 모든 원소를 destBeg로 시작하는 목적지 범위에 복사한다. _if 같은 경우에는 op가 true로 반환될때 수행되어 진다.

Tip : unique를 통해서 연속 중복을 제거하지만, 사이즈는 변경되지 않으므로, 제거를 위해서는 erase를 사용해야한다.

nth_element(coll.begin(), coll.end()-3, coll.end()); 가장 큰 3개를 앞으로 정렬

1) nth_element, partition 차이점

  - nth_element() : 첫 번째 파트에 몇 개의 원소를 가질 지 결정할 수 있다.

  - partition : 첫번째 파트와 두 번째 파트를 구별하기 위해서 정렬기준을 전달해 줄 수 있다.

inner_product(coll.begin(), coll.end(), coll.begin()

                 ,0(초기값)

                 ,multiplies<int>() //외적

                 ,plus<int>()); // 내적

  1. 절대적인 값과 상대적인 값으로의 변경

    1) 상대적인 값을 절대적인 값으로의 변경

    • partial_sum(beg, end, destBeg)

    • [beg, end)의 각 원소에 대해서 부분합을 계산하여 destBeg로 시작하는 목적지 범위에 결과를 기록한다.

    예) a1, a2, a3 -> partial_sum(coll.begin(), coll.end(), ostream_iterator(cout, " "));

     a1 a1+a2 a1+a2+a3

    2) 절대적인 값에서 상대적인 값으로의 변경

    • adjacent_difference(beg, end, destBeg) : [beg, end) 범위의 각 원소에 대해서 차이를 계산한다.

    • adjacent_difference(beg, end, destBeg, (op)) : 각 원소에 대해서 op를 호출한다.

예) adjacent_difference(coll.begin(), coll.end(), ostream_iterator(cout, " "));

 -> a1, a2-a1, a3-a2, a4-a3

 adjacent_difference(coll.begin(), coll.end(), ostream_iterator<int>(cout, " "), plus<int>());

 -> a1, a2+a1, a3+a2, a4+a3

스트링

  1. 비교

1) compare 멤버 함수로는 부분 문자열 비교도 가능하다. boolean이 아닌 정수값을 반환한다.

 예) s.compare(1,2,"bcx",2,2) //s : abcd : "ab"가 "cd"보다 작다 < 0
  1. 수정자

1) 할당자(=, assign)

  - 새로운 값을 할당해 주는 = 연산자를 사용하고 한개 이상의 아규먼트가 필요한 경우에는 assign 멤버 함수를 사용할 수 있다.

2) 값 교체하기(swap)

3) 빈 문자열 만들기

 - 스트링의 모든 문자들을 제거하기 위해서 사용된다.

    s = ""; s.clear() // 내용을 지운다 ,  s.erase() // 모든 문자들을 지운다.

 - erase(pos), erase(beg, end) : 문자열을 삭제한다.
 - clear() : 모든 문자들을 제거하여, 빈 문자열로 만든다.  12. 문자들의 삽입과 제거

 - 문자들을 덧붙이기 위해서 +=, append(), push_back()을 사용

 - append()는 사용자로 하여금 여러 아규먼트들을 사용해서 추가되는 값을 지정할 수 있다.

 - append()의 또 다른 버전은 사용자로 하여금 두 반복자들을 지정해서 문자들의 범위로 추가할 수 있게 한다.

 - push_back() 후위삽입자

 - insert 멤버 함수는 문자들을 삽입할 수 있게 해주며 삽입될 위치의 인덱스를 필요로 한다.(단일문자나 숫자는 안됨)

   insert(idx, num, c), insert(pos, num, c)

 - replace

   string s="i18n";

   s.replace(1,2,"nternationalizatio"); s : internationalization
  1. 부분 문자열과 스트링 연결
 - substr() 멤버 함수를 사용함으로써 스트링에서부터 부분 문자열을 추출해 낼 수 있다.

 예) string s("interchangeability")

      s.substr()     //s의 복사본을 반환한다.

      s.substr(11)  // "ability" 반환

      s.substr(5,6) // "ability" 반환

      s.substr(s.find('c')) // "changeability" 반환
  1. 입출력 연산자
- 스트링에 대해서도 다음과 같은 I/O 연산자들이 정의되어 있다.

1) operator >>은 입력 스트림으로부터 스트링을 읽어드린다.

2) operator <<은 출력 스트림에 스트링을 기록한다.

- >> 연산자는 다음의 상황이 발생할 때까지 모든 문자들을 읽어드린다.

1) 다음 문자가 공백일 경우

2) 스트림이 더 이상 올바른 상태가 아닌 경우(end-of file때문에)

3) 스트림의 현재 width()가 0보다 크고, width()만큼 읽어들인 경우

4) max_size()만큼의 문자들을 읽어들인 경우
  1. 검색과 찾기

1) 단일 문자, 문자 시퀀스(부분 문자열) 또는 문자의 특정한 세트 중의 하나

2) 앞, 뒤 방향으로

3) 특정 위치에서 시작하는 문자열

4) 검색 함수의 인자 설명

  1. npos
  1. 스트링에 대한 반복자 지원

1) assign : [beg,end) 범위의 모든 문자들을 할당한다.

 string s1("hello");
 string s2("hong");

 s1.assign(s2.begin(), s2.end()); //s1은 사라지고 s2의 hong오 덮어쓰기 되어진다.
  1. 국제화
  1. 스트링과 vector 차이점

-> 예를 들어, 스트링은 대게 레퍼런스 카운팅을 사용하지만 vector는 결코 그렇지 않다.

  1. 스트링 클래스 세부사항.

1) 새롭게 알게 된 내용

- traits_type : 문자 특성의 타입

- value_type : 문자들의 타입

- size_type : 인덱스와 사이즈 값을 위한 unsigned 정수 타입

- difference_type : 차이값들을 위한 signed 정수 타입

- reference 문자 래퍼런스의 타입

- void clear(), string& erase() -> 반환값에 따라 다름( 문자 지우는 것에 대해서는 똑같은 동작을 수행함)

STL 추가적으로 알아낸 내용

vector는 동적으로 확장/축소가 가능한 dynamic array로 구현되어 있다.

강점 ● 개별 원소들을 position index로 접근이 가능하다 (상수 복잡도) ● 원소를 컨테이너의 끝에 삽입/제거 하는 것이 빠르다 (상수-아모타이즈드 복잡도) ● 어떠한 순서로도 원소들을 순회할 수 있다. 즉, Random access iterating이 가능함. (로그 복잡도) 일반적으로 vector는 다른 두 개의 시퀀스 컨테이너인 deque, list에 비해 개별 원소에 대한 접근 속도(why? 연속적인 메모리 공간에
저장하므로)와 컨테이너의 끝에서 삽입/제거하는 속도가 가장 빠르다 약점 ● 컨테이너의 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 deque/list에 비해 현저히 떨어진다.

주의 ● 동적으로 컨테이너의 크기가 확장/축소되는 것이 편하기는 하나, 확장시의 reallocation은 비용이 꽤 크다. ● capacity를 확장 시켜줄 수 있는 적절한 크기의 reserve로 인한 메모리 확보가 중요.

  1. deque(double ended queue)
    • Random access iterator를 통한 개별 원소에 대한 접근이 가능하다. operator []도 지원된다.
    • 컨테이너의 크기 역시 동적으로 조절되지만, 그 방법은 vector 방식과는 구별된다.

강점 ● 개별 원소들을 position index로 접근이 가능하다. ● 원소를 컨테이너의 끝 뿐 아니라, 앞에서도 삽입/제거 하는 것이 빠르다. ● 어떠한 순서로도 원소들을 순회할 수 있다.

약점 ● 컨테이너의 시작 / 끝 위치가 아닌 곳에서 삽입/제거 수행시 그 성능은 list에 비해 현저히 떨어진다.

  1. deque : 원소를 컨테이너의 끝 뿐 아니라, 앞에서도 삽입/제거 하는 것이 빠르다.
    • vector는 컨테이너 끝에 삽입/제거하는 것만이 빨랐지만, deque는 컨테이너 끝 뿐 아니라 처음부분에 삽입/제거도 효율이 높다.
    • 이러한 특징으로 STL의 스택과 큐 클래스는 deque와 list로 구현이 가능하지만, 기본 클래스는 deque이다.
  2. vector와의 두번째 차이점이 컨테이너의 동적 확장/축소 방식이다.
    • vector의 경우 컨테이너 내부 capacity가 고갈되면 이를 확장하기 위해 전체 메모리 크기만큼 reallocating이 발생한다.
    • 하지만, deque의 경우 일정 크기를 가지는 chunk 단위로 확장되는 방식을 가지고 있다. 이렇기에 vector에 비해 다음과 같은 장단점이 존재한다.

장점 ● 저장 원소가 많고, 내부 capacity가 작은 경우 vector에 비해 확장 비용이 절감된다. : 전체가 재할당되기 보다, 늘어나야 될 크기만큼만의 chunk가 하나 더 할당되면 됨

단점 ● 컨테이너 처음부터 끝까지 연속 메모리 공간이 아니므로, vector에서 가능했던 원소들간 포인터 연산이 불가능하다.

  1. list 강점 ● 컨테이너의 어느 위치에서도 삽입/제거가 빠르다 (상수 복잡도)

● 원소들의 컨테이너 내 순서 이동이 빠르다. (상수 복잡도)

- vector와 deque와 다르게 list의 가장 큰 강점은 컨테이너 내 어느 위치에서도 원소의 삽입/제거가 빠르다는 것이다.

약점

● 원소의 position index로 직접 접근이 불가능하다. : 특정 원소에 접근하려면 처음이나 끝에서부터 선형 탐색을 하여야만 한다. ● 컨테이너 내 원소 순회는 forward/reverse 순회만 가능하며, 느리다. (선형 복잡도)

● 원소들간 상호 연결 정보를 위해 추가적인 메모리가 사용된다.(원소 수가 적을 수록 상대적으로 많은 메모리를 소비하게 됨.)

  1. map

장점

● 미리 로딩해서 인덱스를 구성해서 사용할 경우는 상당히 유용(insert와 delete가 거의 일어나지 않는 경우)

단점 ● map의 요소가 늘어날수록 그 처리속도는 기하급수적으로 떨어짐 ● insert,delete가 최악.(insert, delete 시에 내부 구조를 재배열하기 때문에 느림)

1) value_type을 사용 : 암시적인 형 변환을 피하기 위해서 사용자는 value_type를 사용하여 정확한 타입을 전달해야함.

  coll.insert(std::map<std::string,float>::value_type("otto", 22.3));

2) pair<> 사용

  coll.insert(std::pair<std::string,float>("otto", 22.3))

3) make_pair() 사용

 coll.insert(std::make_pair("otto", 22.3));

template<class _Ty1, class _Ty2> inline pair<_Ty1, _Ty2> make_pair(_Ty1 _Val1, _Ty2 _Val2) { // return pair composed from arguments return (pair<_Ty1, _Ty2>(_Val1, _Val2)); }

Originally published February 18, 2020
Latest update February 17, 2020

Related posts :