Mona04

Mona04

개발자가 되자

Ch16 string

28 분 소요

String

생성자

void main()
{
	string a(5, 'a');              // string(size_type n, char c);
	cout << a << endl;             // aaaaa
	string b("abcefg", 3);         // string(const char* s, size_type n);
	cout << b << endl;             // abc
	string c(b, 1, 3);             // string(const string& str, size_type pos, size_type npos);
	cout << c << endl;             // bc
	string d(a.begin(), a.end());  // string(Iter begin, Iter end);
	cout << d << endl;             // aaaaa
	string e = { 'a', 'b' };       // string(initializer_list<char> il);
	cout << e << endl;              // ab
}

string 다들 써봤을 거임.

위는 그나마 좀 안쓰는 놈들 정리해 놨음.

  1. a 는 c 로 n 개 초기화.
  2. b 는 s 에서 n 개만큼 초기화하되 널문자가 너머는 쓰레기문자가 들어감
  3. c 는 str 의 pos 인덱스에서 npos 인덱스 까지 복사함. 범위가 초과하던가 하면 터짐.
  4. d 는 string 도 stl 의 container 임을 보여주는 iterator 를 이용한 초기화
  5. e 는 intializer_list 를 이용한 초기화. initializer_list {} 이거로 초기화하는 것으로 자세한건 밑에 설명함

기타

getline, get 이런거 봐도 까먹음. 쉽게 쓰라고 준 cin >> 이나 잘 쓰자.

find(), find_first_of(), compare(), insert() 이런 잡다한 기능이 많으니 필요할 때 검색해서 쓰자. 그리고 복잡한 조작은 정규표현식 써야함.

근데 일반적 stl container 와 달리 find() != string::npos 이렇게 써야하는게 특이함. 이때 string::npos 는 보통 unsigned __int64 의 -1 인 값으로 부호없는 자료형이라 자료형 최댓값임

성능고려

+ 로 문자열 더하면 좌우변 길이만큼 오래걸림.

+= 는 append()를 호출하는데 벡터에 push_back() 할 때 capacity() 랑 size() 고려하는거랑 똑같이 상황에 맞게 reserve() 도 쓰고 하면 됨. +=으로 10000개 이렇게 넣을거면 공간이 점진적으로 늘어나게 되면 비용이 크니까 한번에 공간할당하고 쓰라는 말.

basic_string

using string  = basic_string<char, char_traits<char>, allocator<char>>;
using wstring = basic_string<wchar_t, char_traits<wchar_t>, allocator<wchar_t>>;
#ifdef __cpp_lib_char8_t
using u8string = basic_string<char8_t, char_traits<char8_t>, allocator<char8_t>>;
#endif // __cpp_lib_char8_t
using u16string = basic_string<char16_t, char_traits<char16_t>, allocator<char16_t>>;
using u32string = basic_string<char32_t, char_traits<char32_t>, allocator<char32_t>>;

우리가 아는 string 은 basic_string 에서 char 형으로 인스턴스 된것임. 즉 다른 크기의 문자타입에서도 똑같은게 가능하단 것.

trait 은 값비교 같은 때에 쓰는 문자 고유의 특징을 서술하는 클래스로 자기가 직접 basic_string 을 상속시켜서 원하는 문자열 클래스를 만들 때 다시 찾아보자.

allocator<T> 는 기본적으로 new 와 delete 을 메모리 관리를 위해 사용함. 커스터마이즈는 필요할때 찾아보자.

Smart Pointer

소멸자 자동 호출 귀찮을 때 c++ 이 제공해주는 counter 방식 포인터. Counter 방식과 GC 방식이 있음

auto_ptr

안쓰니까 까먹어도 됨

T 에 int[] 같은 배열을 넣으면 알아서 delete[] 를 호출을 못함(아래는 됨)

rvalue 처리를 c++11 을 사용못함.

unique_ptr, shared_ptr

struct AAA {
	~AAA() { cout << "소멸자 호출" << endl; }
};

void main()
{
	shared_ptr<AAA> shared_a = make_shared<AAA>();
	cout << "Counter is" << shared_a.use_count() << endl;
	{
		unique_ptr<AAA> a = make_unique<AAA>();
		shared_ptr<AAA> shared_a2 = shared_a;
		cout << "Counter is" << shared_a2.use_count() << endl;
	}
	cout << "Counter is" << shared_a.use_count() << endl;
	cout << "Block 끝" << endl;
}
Counter is1
Counter is2
소멸자 호출
Counter is1
Block 끝
소멸자 호출

  • shared / unique ptr 을 만들 땐 std::make_shared<T>(), std::make_unique<T>() 를 쓰면 됨. 만약 생성하는데 인자가 필요하면 그대로 넣으면 됨. 혹은 std::unique_ptr(new int) 이렇게 직접 new 를 넣어서 쓰는 방법이 있지만 번거로우니 잘 안씀.

  • 클래스 내의 멤버변수는 객체가 소멸될때 소멸자가 같이 호출되고 스택에 있는 객체는 스택에서 나올 때 소멸자가 호출되는 것을 알고 있을 거임.

    • 생성할 때 counter 가 1이 되고 unique_ptr 은 대입이나 복사가 안되서 counter 는 1에서 고정임.
    • 그래서 unique_ptr 은 함수 인자로 전달하거나 하면 참조로 밖에 못보냄
    • 이는 대부분 shared_ptr 을 쓰면 적당한 상황임
    • shared_ptr 은 대입이나 복사시 공유하는 counter 를 올리고 각 shared_ptr 이 소멸할 때마다 counter 를 내림. 0이 되면 소멸자를 호출시킴.
    • 해당 포인터를 여러군데에서 가져야하면 따라서 shared_ptr 이 적합함.
std::unique_ptr<int> Get() { return make_unique<int>(); }

void main()
{
	unique_ptr a = Get();
	shared_ptr b = Get();
	unique_ptr c = a; // 에러
	shared_ptr d = a; // 에러
}

이건 참고로만 알아두면 되는데, unique_ptr 은 rvalue 일때만 리턴값도 되고 생성시 바로 넣을 수도 있고 shared_ptr 과 호환도 됨.

STL

찍먹

C++ Standard Libary 의 세부집합으로 일반화 프로그래밍이라는 객체지향 프로그래밍과는 다른 접근의 클래스임.

왜 완전한 객체지향이 아니냐면 예를들어 stl container 마다 find() 함수를 만드는게 아니라 하나의 find() 함수로 여러 stl constainer 가 사용하게 함.(즉 캡슐화 이런거 안함)

이때 같은 기능임에도 멤버함수가 있는 경우가 있음. 이건 특정 container 에 최적화된 알고리즘이 있기 때문임. 그러니까 같은 이름이면 멤버함수 써야함 .

struct AAA {
	int value;
	AAA(int v) : value(v) {}
	void Print() { cout << value << endl; }
	bool operator<(const AAA& in) { return value < in.value; }
};

void main()
{
	vector<AAA> a = { 5,4,3,2,1 };
	sort(a.begin(), a.end());  // operator< 기준으로 오름차순으로 함. 
	for_each(a.begin(), a.end(), [](AAA& a) {a.Print(); });	 // 12345 출력
}

위는 종종 쓸 수 있는 stl 예시임.

sort 함수 등에는 strick weak ordering 을 만족 안하면 뻗는 경우가 종종 있음.

이때 많이 틀리는 부분은 두 비교 대상이 같은 경우 <, > 모두 false 여야 한 다는 것임.

자세한건 여기

Generic Programing

일반화 프로그래밍의 목적은 데이터형과 무관한 코드를 작성하는 것임.

특히 STL 에서는 int 같은 container 내부의 자료형 뿐만 아니라 container 에도 제약받지 않는 코드 를 작성하기를 원함.

이러한 코드는 밑의 알고리즘 에 해당됨

using _Container_base = _Container_base12;
using _Iterator_base = _Iterator_base12;

이러한 목적을 위해서 Container 가 사용하는 Iterator 가 Container 랑 동등하게 정의 되어 있음.

Iterator

잘 정리된거

이하는 iterator 를 특징에 따라 크게 5가지로 구분한 것임.(즉 구현 이전의 개념임)

뒤로 갈수록 앞에 것에 기능이 더 붙는 거라 계층적으로 분류한다고도 함.

왜 이걸 알아야하냐면 sort, find 같은 알고리즘에 우리가 쓰려는 container 가 적용가능한가? 이걸 판단할 때 쓰기 때문임.

다시한번 말하지만 이하는 특성에 따른 분류이고 구현될 iterator 의 요구사항일 뿐임. 예를들어 그냥 포인터는 이하의 모든 분류에 다 들어감

  • input iterator
  • output iterator
    • ++ 로 이동. (*iter) 로 참조만 가능하거나(전자) 대입만 가능함(후자).
  • forward iterator
    • ++ 으로 이동. (*iter) 로 참조 및 대입 가능. (input + outout 이라 보면 됨)
    • iterator 를 메모리에 저장해놓고 동일한 값을 여러번 참조할 수 있어야함
    • 다중 패스 알고리즘 가능
  • bidirectional iterator
    • forward 에 더해서 -- 로 뒤로 가기도 됨.
    • rbegin(), rend() 이런걸 지원하는 container 가 이를 사용함
  • random access iterator
    • [] 나 iterator + 10 같을걸 통해 임의의 원소에 들어갈 수 있음.
    • vector 나 deque 등이 이러한 iterator 를 적용함.
	template <class _FwdIt, class _Ty>
	_NODISCARD _FwdIt upper_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) {
    // find first element that _Val is before, using operator<
    return _STD upper_bound(_First, _Last, _Val, less<>());
	}

template <class _RanIt>
void sort(const _RanIt _First, const _RanIt _Last) { // order [_First, _Last), using operator<
    _STD sort(_First, _Last, less<>());
}

실제로 어떻게 되어있나 보려면 container 보단 알고리즘을 찾아보면 됨

예를들어 upper_bound에서 _Fwdit 이 forward iterator 의 약자임

sort 에서 _Ranit 은 random iterator 의 약자임.

만약 unordered_map 을 sort 함수로 정렬할 수 있나? 생각해보면 재는 bidirectional 이라 레벨이 딸려서 못쓰네 이렇게 판단할 수 있음. (당연히 Hash 함수로 연결되니 못하는거지만)

Container

  • vector, map, biset, list 같은 애들임.

  • 복사생성, 대입이 가능한 단일형의 다른 객체나 값들을 저장하는 객체임.

  • 자기가 소멸하면 안의 데이터도 소멸함.

  • 포인터를 추상화한 Iterator 가 있어서 자기 내부의 데이터를 순회할 수 있어야함.

  • 비교나 대입 등에 필요한 시간복잡도는 안의 내부의 데이터나 상황에 따라 상식적으로 판단해보자.

  • 혹시 내가 container 에 따른 대입/삽입/삭제/비교의 시간복잡도를 모른다고 하면 1278부터 읽어보길 권함.

Functor

  • operator() 가 사용가능한 객체. 특히 operator() 를 오버로딩한 클래스를 말함.

  • stl 내부에선 많이 씀.

  • 외부에서는 펑크터나 어탭터 이런건 복잡해서 그냥 람다나 함수포인터 씀.

  • 알고리즘에서 Predicate, Binary_Predicate 이라는 이름의 인자가 있을 것임. 얘네는 자주 보이는 펑크터인데, 전자는 bool 값을 리턴하는 단항 함수를 넣으란 거고 후자는 bool 값을 리턴하는 이항 함수를 넣으라는 것임.

namespace std {
	template<> struct hash<AAA> {
		std::size_t operator()(const VISIT& in) const noexcept { return (in.val) % 100070 + in.k; }
	};

위는 펑크터가 어떻게 쓰이는지 보여주려고 들고온 예시임.

unordered_set 등에서 해시펑션을 펑크터로 쓰고 그 클래스가 hash 임

위는 그 hash 클래스를 AAA 타입에 대해서 명시적 특수화 한 것.

그럼 stl 은 AAA 에 대해서 해시값을 얻을 때 위를 적용할 것임.

만약 저게 없으면 우리는 unordered_set<AAA> 를 사용하지 못함

알고리즘

find(), sort(), copy(), 등이 포함됨. 필요할 때 검색해서 쓰면 됨.

앞에서 말했듯이 특정 container 에 종속되지 않고 앞에서 설명한 iterator 의 분류에 따른 적절한 iterator 만 받으면 잘 수행해줌.

앞에서 말햇듯 특정 container 의 메소드가 같은 역할을 하면 알고리즘보단 메소드가 더 나음.

Initializer List

책안보고 이거만 봐도 됨

struct AAA {
	int value1;
	float value2;
};

struct BBB {
	int value1[5];
	BBB(const initializer_list<int>& li) {
		if (li.size() < 5) return;
		copy(li.begin(), li.begin() + 5, value1);
	}
};

void main()
{
	AAA aaa = { 1, 3.14f };            // uniform initialize
	cout << aaa.value1 << endl << aaa.value2 << endl;
	BBB bbb = { 1,2,3,4,5,6 };       // initializer_list 
	BBB bbb = { 1, 2.2 };               // narrow conversion 이라 안됨
	for_each(bbb.value1, bbb.value1 + 5, [](int a) {cout << a; });
}

  • uniform initialize 와 비슷한데 narrow conversion 을 못함.

  • 그리고 initializer_list 로 생성자를 오버로딩하면 uniform initialize 는 못쓰게 됨.

  • 얘네도 container 라서 반복자도 있고 size() 도 있음

  • auto a = {1,2,3}; 이러면 자료형이 initializer_list 임.

댓글남기기

관련

Boj 24895) 다트

14 분 소요

백준 24895. 볼록껍질의 성질을 이용한 이분탐색과 누적합

Quantum Information Basic

19 분 소요

양자컴퓨터가 어떤 문제를 효율적으로 풀 수 있는지에 대한 간략한 이해.