ft_containers 공부

songtofu·2022년 2월 16일
cppft_containers
0

ft_containers

목록 보기
2/2

container?

-다른 객체(원소)들을 보관하는 하나의 커다란 보관소. STL 컨테이너는 클래스 템플릿(class template)의 형태로 구현되어 있기 때문에 임의의 타입의 원소들을 위한 컨테이너를 만들 수 있다. 물론 한 컨테이너에는 한가지 종류의 객체들만 보관할 수 있다.
-자신이 보관하는 원소들의 메모리를 관리하며, 각각의 원소에 접근할 수 있도록 멤버 함수를 제공한다. 컨테이너 상에서 원소에 접근하는 방법은 두가지가 있다. 하나는 직접 함수를 호출해서 접근, 다른 하나는 반복자(iterator)을 이용해서 접근하는 것

Container class template

  • 순차 컨테이너 (Sequence Container)
    - vector (벡터)
    - deque (데크)
    - list (리스트)
  • 컨테이너 어댑터 (Container Adaptor)
    - stack (스택) : Last in First out
    • queue (큐) : First in First out
    • priority_queue (우선순위 큐)
  • 연관 컨테이너
    - set
    • multiset : 여러 키를 가지는 set
    • map
    • multimap : 여러 키를 가지는 map
    • bitset

friend 키워드?

  • 클래스 구현자만 이 클래스의 friend를 선언할 수 있다. 함수 또는 클래스는 자신을 클래스의 friend로 선언할 수 없다. 클래스 정의에서 멤버가 아닌 friend 함수 또는 다른 클래스의 키워드와 이름을 사용하여 클래스의 private 및 protected 멤버에 대한 액세스 권한을 부여한다.
  • 예제
  1. 함수에 사용
// classes_as_friends1.cpp
// compile with: /c
class B;

class A {
public:
   int Func1( B& b );

private:
   int Func2( B& b );
};

class B {
private:
   int _b;

   // A::Func1 is a friend function to class B
   // so A::Func1 has access to all members of B
   friend int A::Func1( B& );
};

int A::Func1( B& b ) { return b._b; }   // OK
int A::Func2( B& b ) { return b._b; }   // C2248

위의 예제에서는 A::Func1( B& ) 함수에만 B 클래스에 대한 friend 액세스 권한이 부여됩니다. 따라서 private 멤버에 대한 _b 액세스는 클래스의 에서 Func1 올바르지만 A 에서는 올바르지 Func2 않습니다.

  1. 클래스에 사용
    friend 클래스의 B 선언이 다음과 같다고 가정합니다.
friend class A;

friend 클래스는 모든 멤버 함수가 클래스의 friend 함수인 클래스입니다. 즉, 멤버 함수가 다른 클래스의 전용 및 보호된 멤버에 액세스할 수 있습니다.
이 경우 A 클래스의 모든 멤버 함수에 B 클래스에 대한 freind 액세스 권한이 부여되었습니다.

iterator?

  • 컨테이너에 보관된 원소에 접근할 수 있는 반복자 (iterator), 포인터와 같은 객체
  • 템플릿 버전의 경우
for (typename std::vector<T>::iterator itr = vec.begin(); itr != vec.end();
     ++itr) {

와 같이 typename을 추가해줘야함. iterator 가 std::vector 의 의존 타입이기 때문.

Vector

  • 배열처럼 객체들을 순차적으로 보관하는 시퀀스 컨테이너(sequence container) 중 하나.
  • 쉽게 생각해서 가변길이 배열.
  • 임의의 위치에 있는 원소를 접근하는 것을 매우 빠르게 수행.

  • begin()함수는 예상대로 vector의 첫번째 원소를 가르키는 반복자를 리턴, 하지만 end() 함수의 경우 마지막 원소 한 칸 뒤를 가리키는 반복자를 리턴한다.
    왜? -> 여러 이유 존재, 가장 중요한 점 = 이를 통해 빈 벡터를 표현할 수 있다는 점. (begin() == end())라면 원소가 없는 벡터를 의미.

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

이터레이터를 포인터 처럼 사용한다고 하였다, 실제로 현재 이터레이터가 가리키는 원소의 값을 보고 싶다면

std::cout << *itr << std::endl;

포인터로 를 사용해서 가르키는 주소값의 값을 보았던 것 처럼, 를 이용해서 itr이 가르키는 원소를 볼 수 있다.
물론 itr는 실제 포인터가 아니고 *연산자를 오버로딩해서 마치 포인터 처럼 동작하게 만든 것 이다. *연산자는 itr이 가르키는 원소의 레퍼런스를 리턴한다.

또한, + 연산자를 통해 그 만큼 떨어져 있는 원소를 가리키게 할 수도 있다.

  • insert함수, erase함수 예시
#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 << "처음 벡터 상태" << std::endl;
  print_vector(vec);
  std::cout << "----------------------------" << std::endl;

  // vec[2] 앞에 15 추가
  vec.insert(vec.begin() + 2, 15);
  print_vector(vec);

  std::cout << "----------------------------" << std::endl;
  // vec[3] 제거
  vec.erase(vec.begin() + 3);
  print_vector(vec);
}
  • insert함수, erase함수 주의할 점
#include <iostream>
#include <vector>

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

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

  std::vector<int>::iterator itr = vec.begin();
  std::vector<int>::iterator end_itr = vec.end();

  for (; itr != end_itr; ++itr) {
    if (*itr == 20) {
      vec.erase(itr);
    }
  }

  std::cout << "값이 20 인 원소를 지운다!" << std::endl;
  print_vector(vec);
}

위와 같은 상황에선 오류가 발생한다.
이유 :: 컨테이너에 원소를 추가하거나 제거할 시 기존에 사용하였던 모든 이터레이터들을 사용할 수 없게 된다. 위의 경우 vec.erase(itr)을 수행하게 되면 더 이상 itr은 유효한 반복자가 아니게 되는 것. 또한, end_itr 역시 무효화 된다. 따라서, itr != end_itr 이 영원히 성립되어서 무한 루프에 빠지게되어 오류가 발생.

코드를 고치려면

std::vector<int>::iterator itr = vec.begin();
//1번째 방법
for (; itr != vec.end(); ++itr) {
if (*itr == 20) {
  vec.erase(itr);
  itr = vec.begin();
}
}
//2번째 방법
for (std::vector<int>::size_type i = 0; i != vec.size(); i++) {
if (vec[i] == 20) {
  vec.erase(vec.begin() + i);
  i--;
}
}

const_iterator

  • vector에서 지원하는 const_iterator는 const 포인터를 생각하면 된다. 가리키고 있는 원소의 값을 바꿀 수 없다.
  • const 반복자는 cbegin()과 cend()함수를 이용하여 얻을 수 있다.

    역반복자(reverse iterator)

  • 반복자와 똑같지만 벡터 뒤에서 부터 앞으로(거꾸로)간다.
  • rend()역시 맨 앞 원소의 바로 앞을 가리키게 된다. 또한 반복자의 경우 값이 증가하면 뒤쪽 원소로 가는 것처럼, 역반복자의 경우 값이 증가하면 앞쪽 원소로 가게 된다.
  • const_reverse_iteraotr타입 존재, crbegin(), crend()로 얻을 수 있다.
  • 오류 예제 (segmentation fault) 역반복자를 사용해야하는 이유.
    ///여기 수정해야함 코드 들어가야함
    (cpp
    #include
    #include

int main() {
std::vector vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);

// 끝에서 부터 출력하기
for (std::vector::size_type i = vec.size() - 1; i >= 0; i--) {
std::cout << vec[i] << std::endl;
}

return 0;
})
오류의 이유 : vector의 index를 담당하는 타입이 부호없는 정수이기 때문.
따라서, i 가 0일 때 i--를 하게 되면 -1이 아니라 해당 타입에서 가장 큰 정수가 된다. 따라서 for 문이 무한 루프.

Map

  • 연관 컨테이너 (associative container)의 한 종류.

    연관 컨테이너

  • key-value (키 - 값)구조를 가진다. 특정한 키를 넣으면 이에 대응되는 값을 돌려준다는 것.

  • 템플릿 라이브러리 이기 때문에 키와 값 모두 임의의 타입의 객체가 될 수 있다.


  • Q1. 박명순이 데이터에 존재하나요? (특정 키가 연관 컨테이너에 존재하나요?)
    A1. TRUE
    Q2. 만약 존재한다면 이에 대응되는 값이 무엇인가요? (특정 키에 대응되는 값이 무엇인가요?)
    A2. 46
    -Q1의 경우 set과 multiset이고 Q2의 경우 map과 multimap이다.

    Map 예시

    #include <iostream>
#include <map>
#include <string>
template <typename K, typename V>
void print_map(std::map<K, V>& m) {
// 맵의 모든 원소들을 출력하기
for (auto itr = m.begin(); itr != m.end(); ++itr) {
  std::cout << itr->first << " " << itr->second << std::endl;
}
}
int main() {
std::map<std::string, double> pitcher_list;

// 참고로 2017년 7월 4일 현재 투수 방어율 순위입니다.

// 맵의 insert 함수는 pair 객체를 인자로 받습니다.
pitcher_list.insert(std::pair<std::string, double>("박세웅", 2.23));
pitcher_list.insert(std::pair<std::string, double>("해커 ", 2.93));

pitcher_list.insert(std::pair<std::string, double>("피어밴드 ", 2.95));

// 타입을 지정하지 않아도 간단히 std::make_pair 함수로
// std::pair 객체를 만들 수 도 있습니다.
pitcher_list.insert(std::make_pair("차우찬", 3.04));
pitcher_list.insert(std::make_pair("장원준 ", 3.05));
pitcher_list.insert(std::make_pair("헥터 ", 3.09));

// 혹은 insert 를 안쓰더라도 [] 로 바로
// 원소를 추가할 수 있습니다.
pitcher_list["니퍼트"] = 3.56;
pitcher_list["박종훈"] = 3.76;
pitcher_list["켈리"] = 3.90;

print_map(pitcher_list);

std::cout << "박세웅 방어율은? :: " << pitcher_list["박세웅"] << std::endl;
}

//실행 결과
니퍼트 3.56
박세웅 2.23
박종훈 3.76
장원준  3.05
차우찬 3.04
켈리 3.9
피어밴드  2.95
해커  2.93
헥터  3.09
박세웅 방어율은? :: 2.23
  - 맵의 경우 템플릿 인자로 2개를 가진다. 첫번째는 키의 타입, 두번째는 값의 타입.
  ```cpp
std::map<std::string, double> pitcher_list;
  • 맵에 원소를 넣기 위해서는 std::pair 객체를 전달해야한다.
    template <class T1, class T2>
struct std::pair {
T1 first;
T2 second;
};
  - std::pair 객체를 하나하나 전달하는 것은 귀찮다. 그래서 std::make_pair함수를 제공
  ```cpp
pitcher_list.insert(std::make_pair("차우찬", 3.04));
pitcher_list.insert(std::make_pair("장원준 ", 3.05));
pitcher_list.insert(std::make_pair("헥터 ", 3.09));
  • 맵의 경우 operator[] 를 이용해서 새로운 원소를 추가할 수 있다. (만일 해당하는 키가 맵에 존재하지 않는다면) 만일 키가 이미 존재하고 있다면 값이 대체된다.
  • 반복자를 이용한 순차적 원소 탐색
    template <typename K, typename V>
void print_map(std::map<K, V>& m) {
// 맵의 모든 원소들을 출력하기
for (auto itr = m.begin(); itr != m.end(); ++itr) {
  std::cout << itr->first << " " << itr->second << std::endl;
}
}
  - 맵에 저장된 값을 찾고 싶다면 간단히 [] 연산자를 이용하면 된다. 하지만 주의할 점이 있다.
  ```cpp
#include <iostream>
#include <map>
#include <string>
template <typename K, typename V>
void print_map(const std::map<K, V>& m) {
  // kv 에는 맵의 key 와 value 가 std::pair 로 들어갑니다.
  for (const auto& kv : m) {
    std::cout << kv.first << " " << kv.second << std::endl;
  }
}
int main() {
  std::map<std::string, double> pitcher_list;

  pitcher_list["오승환"] = 3.58;
  std::cout << "류현진 방어율은? :: " << pitcher_list["류현진"] << std::endl;

  std::cout << "-----------------" << std::endl;
  print_map(pitcher_list);
}

과 같이 0 이라는 값이 나온다. 없는 값을 참조하면 오류가 발생해야 정상인데? 이는 [] 연산자가 맵에 없는 키를 참조하게 되면, 자동으로 값의 디폴트 생성자를 호출해서 원소를 추가해버리기 때문이다.
따라서, 되도록 find()함수로 키가 존재하는지 확인 후 값을 참조하는 것이 좋다.

  • map은 중복된 원소를 허락하지 않는다. 이미 같은 키가 원소로 들어 잇다면 나중에 오는 insert는 무시된다.

Stack

  • 스택은 컨테이너 어댑터의 일종, LIFO(선입선출)에서 작동하도록 설계되었으며, 컨테이너의 한쪽 끝에서만 요소를 삽입하고 추출한다.
  • 스택의 맨 위라고 알려진 특정 컨테이너의 "뒤로" 푸시/팝 됩니다.
  • 표준 컨테이너 클래스는 벡터, 데크, 리스트로 이러한 요구사항을 충족한다. 기본적으로 특정 스택 클래스는 인스턴스화에 대해 컨테이너 클래스가 지정되지 않은 경우 표전 컨테이너 데크가 사용됩니다.

출처

profile
songtofu
읽으면 머리에 안들어와서 직접 쓰는 중. 잘못된 부분 지적 대환영
이전 포스트

ft_containers 과제

0개의 댓글