📦

ft_containers

Created

2022/07/25 04:29

Updated

2022/08/25 08:36

Intro

CPP Module을 수행하다보면 데이터를 저장할 수 있는 CPP의 여러 Container를 접할 수 있다.

본 과제의 수행 목적은 CPP container의 용도와 특징을 파악하며 재구성, 구현 하는 것이다.

Before to go

1. Compile time polymorphism

CPP에는 다형성(Polymorphism)이라는 개념이 존재한다. 아마 CPP Module 과제를 수행하며 이 다형성 개념을 공부한 경험이 있을 것이다.

다형성을 통해 함수를 결정하는 시점이 두 개가 존재하는데 첫 번째는 컴파일(Compile) 타임 때, 두 번째는 런타임(Runtime) 때이다.

같은 이름의 함수를 여러 개 만들어 후보군을 두는 함수 오버로딩(Overloading)은 컴파일(Compile) 때, 부모 클래스의 함수를 재정의 한 함수를 사용하는 오버라이딩(Overriding)는 런타임(Runtime) 때 결정 된다.

예시

// Compile time
int add(int, int);
int add(int, int, int);    //number of parameters different
double add(double, double);    //type of parameters different

// Runtime
#include <iostream>
using namespace std;
class base {
    public:
    virtual void display() {
        cout<<"Function of base class"<<endl;
    }
};
class derived : public base {
    public:
    void display() {
        cout<<"Function of derived class"<<endl;
    }
};
C++
복사

본 과제를 수행하다보면 컴파일 타임 때 함수 오버로딩 뿐만 아니라 템플릿을 활용한 타입 추론, 템플릿 메타 함수 등 많은 작업이 이루어지고 그 코드가 많은 것을 알 수 있는데, 컴파일 타임에 위와 같은 작업이 수반될 때 나타나는 장점이 무엇이 있는지 알아보았다.

컴파일 타임 때 작업을 수행하면 실행 시간이 크게 줄어드는 장점이 있다. static과 같은 정적 값은 컴파일 타임 때 계산되기 때문에 런타임 때 이러한 계산 작업을 크게 줄일 수 있다. 더해서 만약 오랜 시간이 걸리는 루프 실행문을 컴파일 타임 때 수행한다면 마찬가지로 런타임을 줄일 수 있다. 이러한 방법은 강력한 최적화 방법으로 소개되고 있다. 하지만 이 같은 경우 줄어든 런타임 만큼 컴파일 타임이 길어질 수 있다는 단점도 존재한다.

런타임 때 발생할 수 있는 예측하지 못한 오류를 컴파일 타임 때 잡을 수 있다는 장점도 존재한다. CPP는 템플릿을 통한 다형성(Polymorphism)을 구현하는데 이 템플릿 프로그래밍은 컴파일 타임 때 코드를 작성해주어 런타임 때 메모리와 수행 시간을 크게 줄일 수 있는 장점이 있다. 하지만 만약 컴파일 타임 때 템플릿 작업을 수행하지 않는다면 적절하지 않은 타입이 들어왔을 때 예기치 못한 상황이 발생할 수 있다.

예시

template <typename _Type>
void example(void)
{
	_Type &a;
	a.fnc(); // 만약 _Type 내에 fnc라는 함수가 존재하지 않는다면?
}
C++
복사

2. SFINAE

Substitution failure is not an error의 약자로, ‘대체 실패는 오류가 아니다’라는 뜻이다.

하나의 함수 이름을 사용하여 여러 작업을 수행하고자 할 때 함수 오버로드 후보군을 만든다. 그리고 후보군이 템플릿으로 생성 되었다면 그 템플릿 인자에 자료형이나 값이 대입이 되는 경우가 있을 수 있다.

그 후 컴파일 타임 때 적절한 후보군을 찾는 과정이 수행 되는데 만약 대체 과정 중 오류가 발생해도 C++ 표준이 허용한다면 컴파일러는 컴파일 오류를 나타내지 않고 그 후보를 후보군에서 제외하는 작업만 수행한다.

예시

#include <iostream>

struct TEST {
    // rename int as test
    typedef int test;
};

// 01
template <typename T> void fnc(typename T::test) {
    std::cout << "Type in the structure" << std::endl;
}

// 02
// 만약 이 함수가 없다면, 아래의 main문은 반드시 오류를 출력한다.
template <typename T> void fnc(T) {
    std::cout << "Only typename T function" << std::endl;
}

int main(void) {
    fnc<TEST>(10); // TEST 안에 'test'가 있기 때문에 정상적으로 수행
    fnc<int>(10); // int 안에 'test'가 없기 때문에 'typename T::test'
									// 에서 오류가 발생하나, SFINAE에 따라 후보에서 제외함
									// 이후 대체 함수가 남아있어 오류 없이 정상 수행
    return (0);
}
C++
복사

아래의 경우는 SFINAE 개념이 잘 적용 된 것 처럼 보인다. 하지만 3W(-Wall -Werror -Wextra) 옵션과 같이 컴파일을 해보면 에러가 발생하는 것을 알 수 있다.

예시

#include <iostream>

struct TEST {
    // rename int as test
    typedef int test;
};

template <typename T> void fnc(typename T::test) {
    std::cout << "Type in the structure" << std::endl;
    std::cout << sizeof(typename T::test) << std::endl; // diff
}

template <typename T> void fnc(T) {
    std::cout << "Only typename T function" << std::endl;
    std::cout << sizeof(typename T::test) << std::endl; // diff
}

int main(void) {
    fnc<TEST>(10);
    fnc<int>(10);
    return (0);
}
C++
복사

왜냐하면 SFINAE가 적용되는 시점을 벗어났기 때문인데, 이 문서의 SFINAE 항목을 보면 다음과 같이 기술되어 있다.

Only the failures in the types and expressions in the immediate context of the function type or its template parameter types or its explicit specifier (since C++20) are SFINAE errors. If the evaluation of a substituted type/expression causes a side-effect such as instantiation of some template specialization, generation of an implicitly-defined member function, etc, errors in those side-effects are treated as hard errors.

함수 유형 또는 템플릿 파라미터 유형 또는 명시적 지정자의 직접적인 맥락에서 발생하는 오류만 SFINAE 에러로 취급한다. 그리고 대체 이후에 발생되는 에러는 하드 에러로 취급한다.

따라서 void fnc(T) 함수 내의 일반 실행문인 sizeof(typename T::test) 는 SFINAE의 범주에서 벗어나 에러가 발생한다.

3. 템플릿 메타 함수

한 번 읽어보면 매우 좋을 글

다음으로 진행하기 전 템플릿 메타 함수가 무엇인지 알 필요가 있다. 템플릿 메타 함수는 컴파일 타임에 함수는 아니지만 마치 함수처럼 동작하는 템플릿 클래스들을 말한다. 일반 함수는 값(Value)에 대해 연산하지만 템플릿 메타 함수는 타입(Type)에 대해 연산한다.

예제 01

#include <iostream>

bool is_negative(int nbr)
{
	if (nbr < 0)
		return true;
	return false;
}

int main(void)
{
	if (is_negative(1))
	{
		std::cout << "negative" << std::endl;
	}
	else
	{
		std::cout << "positive" << std::endl;
	}
	return (0);
}
C++
복사

위의 예제는 일반 함수를 통해 파라미터가 음수인지 양수인지 구분하는 코드이다.

예제 02

#include <iostream>

template <typename _Tp>
void catch_type()
{
	if (std::is_void<_Tp>::value) // 템플릿 메타 함수
	{
		std::cout << "void" << std::endl;
	}
	else
	{
		std::cout << "not void" << std::endl;
	}
}

int main(void)
{
	catch_type<void>();
	catch_type<int>();
	return (0);
}
C++
복사

예제 02는 catch_type을 템플릿을 사용해 구현하고 if문 내의 is_void 템플릿 메타 함수를 통해 type이 void인지 아닌지를 출력하는 예시이다.

여기서 is_void는 type_traits 라이브러리 내에 있는 구조체로 함수처럼 동작하는 템플릿 클래스(구조체)이다.

type_traits 는 타입에 따라 여러 연산을 수행할 수 있는 템플릿 메타 함수를 제공하는 라이브러리이다.

// 모든 타입에 대응하는 템플릿 메타 함수
template <class _Tp> struct __libcpp_is_void       : public false_type {};
// void 타입에만 대응하는 템플릿 메타 함수
template <>          struct __libcpp_is_void<void> : public true_type {};

// 위의 __libcpp_is_void를 상속받는 is_void
template <class _Tp> struct _LIBCPP_TEMPLATE_VIS is_void
    : public __libcpp_is_void<typename remove_cv<_Tp>::type> {};
C++
복사

과제를 수행하면서 특히 눈에 띄는 템플릿 메타 함수가 있었는데 정리를 위해서 아래에 기록을 남긴다.

template <class _Tp, _Tp __v>
struct _LIBCPP_TEMPLATE_VIS integral_constant
{
	static _LIBCPP_CONSTEXPR const _Tp value = __v; // __v를 static으로 가지는 템.메.함
	typedef _Tp value_type;
	typedef integral_constant type;
	_LIBCPP_INLINE_VISIBILITY
	_LIBCPP_CONSTEXPR operator value_type() const _NOEXCEPT { return value; }
#if _LIBCPP_STD_VER > 11
	_LIBCPP_INLINE_VISIBILITY
	constexpr value_type operator()() const _NOEXCEPT { return value; }
#endif
};
C++
복사

integral_constant는 여러 템플릿 메타 함수를 조합해 조건을 따질 때 많이 사용했는데 예시는 다음과 같다.

template <class _Tp> struct _LIBCPP_TEMPLATE_VIS is_class
    : public integral_constant<bool, __is_class(_Tp)> {};
C++
복사

위에서 사용했던 is_void처럼 is_class는 클래스인지 아닌지를 나타내는 메타 함수이다.

if (std::is_class<_Tp>::value)
// 이하 생략
C++
복사

위와 같이 value가 true인지 false인지를 비교하는데 이 value는 integral_constant의 value이다.

integral_constant의 value는 __v와 같은데, is_class의 상속 형태를 보면 __is_class(_Tp)와 같은 것을 알 수 있다. 결론적으로 __is_class(_Tp)의 실행 구조가 어떻게 되어 있는지는 모르지만 이 결과값이 integral_constant의 value를 결정짓는 것을 알 수 있다.

4. enable_if

템플릿 메타 함수로 SFINAE 개념을 활용해 조건에 맞지 않는 오버로딩 함수들을 후보군에서 제외시켜주는 역할을 수행한다. 처음에 enable_if가 SFINAE와 같다고 생각하였지만, enable_if는 SFINAE를 옳게 구현하는 방법 중 하나이다. enable_if는 여러 템플릿 메타함수를 조합해 조건을 만족하는 타입을 인자로 받는 것을 목적으로 한다.

Prototype

template <bool, class _Tp = void> struct enable_if {};
template <class _Tp> struct enable_if<true, _Tp> {typedef _Tp type;};
C++
복사

enable_if의 프로토 타입은 두 가지가 존재한다. 결론만 먼저 말하면 만약 enable_if의 첫 번째 템플릿 인자인 bool이 true라면 enable_if::type의 타입은 _Tp가 된다. 다시 말해서 bool이 true라면 type이 존재한다는 것이다.

예제

#include <iostream>
#include <type_traits>

template <typename _Tp>
void catch_type(typename std::enable_if<std::is_void<_Tp>::value>::type * = 0)
{
	if (std::is_void<_Tp>::value)
	{
		std::cout << "void" << std::endl;
	}
	else
	{
		std::cout << "not void" << std::endl;
	}
}

int main(void)
{
	catch_type<void>();
	catch_type<int>(); // 지우면 컴파일 정상적으로 됨
	return (0);
}
C++
복사

enable_if는 SFINAE를 적용한 방법 중 하나라고 했다. 따라서 템플릿 인자에도 함수 인자에도 enable_if를 사용할 수 있다. 위는 함수 파라미터에 enable_if를 적용한 모습이다.

enable_if 안에 is_void 메타 함수를 적용했는데, 만약 _Tp가 void라면 value가 true가 되어 enable_if의 type이 존재하게 될 것이다. 위의 코드를 컴파일 했을 때 오류가 나게 되는데, 왜냐하면 catch_type<int>() 실행 구문에서 int 타입은 void가 아니기 때문이다.

추가적인 예로 벡터의 생성자를 들어보겠다.

// 1.
vector (size_type n, const value_type& val);

// 2.
template <class InputIterator>
vector (InputIterator first, InputIterator last);

// 작성한 실행문
vector<int> _v(10, 3);
C++
복사

벡터의 생성자가 1번과 2번 두 개가 있고 마지막에 벡터 _v를 생성하는 실행문을 작성하였다.

위의 실행문은 1번 생성자를 실행할까 아니면 2번 생성자를 실행할까? 정답은 2번 생성자이다. 우리는 분명 10개의 공간에 3이라는 값을 넣고싶은데 왜 2번 생성자를 실행할까?

그 이유는 size_type과 템플릿 인자인 InputIterator에 있다. 본 예제에는 나와있지 않지만 벡터 코드를 살펴보면 size_type은 부호 없는 정수 타입이다. 따라서 10은 부호가 있는 정수이기 때문에 1번 생성자에도 맞긴 하지만 완전히 들어맞는 생성자는 2번 생성자이다. 만약 InputIterator에 int가 들어온다면 2번 생성자는 다음과 같이 표현할 수 있을 것이다.

vector (int first, int last);
C++
복사

컴파일러는 여러 후보군 중 가장 적합한 후보를 찾아 코드를 생성하고 컴파일한다. 따라서 위와 같이 InputIterator에 iterator 타입이 들어오지 않아서 발생하는 오류나 모호함을 방지하기 위해 enable_if를 사용한다.

예시

template <typename InputIterator>
vector(InputIterator first, 
				enable_if<std::is_iterator<InputIterator>::value>::type last);
C++
복사

위와 같이 enable_if를 사용하면 템플릿 파타미터 InputIterator에 iterator 타입이 들어왔을 때만 2번 생성자가 실행 될 것이다.

5. VSTD

링크

• _VSTD is now an alias for std instead of std::_LIBCPP_ABI_NAMESPACE. This is technically not a functional change, except for folks that might have been using _VSTD in creative ways (which has never been officially supported).

_VSTD는 std::_LIBCPP_ABI_NAMESPACE를 대신해서 사용되는 매크로이다.

대충 std와 비슷한 전역 namespace라고 생각하면 되지 않을까 싶다.

Container

Container란 이름에서 알 수 있듯이 본 과제는 데이터를 저장할 수 있는 객체를 구현하는 것을 목적으로 한다.

Container는 데이터의 여러 타입을 수용할 수 있는 능력을 지닌다. 이는 템플릿(template)을 통해 구현되고

정수형, 실수형, 문자형 심지어 객체형태 까지의 여러 데이터 타입을 포용하는 유연성을 갖고 있다.

컨테이너는 객체에 직접적으로 접근하여 관리하거나 사용할 수 있는 기능을 제공하는데 이는 iterator라는 반복자를 통해 제공된다.

다음은 크게 세 개로 구분되는 컨테이너의 종류이다.

1. Sequence containers ( 시퀀스 컨테이너, 순차적 컨테이너 )

Sequence container는 데이터에 순차적으로 접근할 수 있는 구조(container)이다.

Template	Container	Description
Class template	vector	동적 연속 배열
Class template	deque	양방향 큐 (double-ended queue)
Class template	list	이중 연결 리스트 (doubly-linked-list)
Class template	array (C++11)	정적 연속 배열
Class template	forward_list (C++11)	단일 연결 리스트 (singly-linked list)

2. Associative containers ( 연관 컨테이너 )

Associative container는 데이터에 빠르게 접근하고 검색할 수 있는 구조이다.

Template	Container	Description
Class template	map	키에 의해 정렬된 키-값 쌍의 모음 이 때 키는 고유(Unique)함
Class template	set	키로 정렬 된 고유 키의 모음
Class template	multimap	키에 의해 정렬 된 키-값 쌍의 모음
Class template	multiset	키로 정렬 된 키의 모음

3. Unordered associative containers

데이터를 빠르게 검색할 수 있는 해싱 된 구조

Template	Container	Description
Class template	unordered_map (C++11)	키에 의해 hashed 된 키-값 쌍의 모음 이 때 키는 고유(unique)함
Class template	unordered_set (C++11)	키에 의해 hashed 된 고유 키의 모음
Class template	unordered_multimap (C++11)	키에 의해 hashed 된 키-값 쌍의 모음
Class template	unordered_multiset (C++11)	키에 의해 hashed 된 키의 모음

4. Container adaptors

기존 컨테이너의 인터페이스를 제한하여 기능이 변환되거나 성능이 제한 된 컨테이너를 말한다.
특정 형태의 동작만을 수행하도록 기존의 인터페이스를 제한하고 반복자(iterator)를 지원하지 않는다.
따라서 정렬, 원소 탐색과 같은 STL (Standard Template Library) 알고리즘을 사용할 수 없다.

Template	Container	Description
Class template	stack	LIFO(Last In - First Out) 구조
Class template	queue	FIFO(First In - First Out) 구조
Class template	priority_queue	우선 순위 큐 데이터 구조

Iterator

반복자(Iterator)

반복자(Iterator)는 배열 또는 컨테이너의 요소를 가리키는 모든 객체로 연산자 집합을 사용하여 해당 범위의 요소를 반복할 수 있는 객체이다. (i.e. 증분 연산(++) 또는 역참조(*))

반복자와 가장 비슷한 것은 포인터라고 할 수 있다. 포인터 또한 증분연산을 통해 배열을 반복하며 순회를 할 수 있다. 더해서 vector와 같은 container에 따로 설계 된 반복자도 존재하는데 이도 포인터나 반복자와 같은 역할을 수행한다.

하지만 모든 반복자가 포인터의 모든 기능을 수행할 수 있는 것은 아니고 반복자가 지원하는 특성과 속성에 따라서 5개의 다른 범주로 분류된다.

Type	Description
입력 반복자 (Input iterator)	read-only 컨테이너로부터 값을 읽는 데 쓰이는 반복자로 값을 읽을 수는 있지만 변경할 수는 없다. 증가 연산자(++)를 사용해서 순방향으로만 이동이 가능하다.
출력 반복자 (Output iterator)	write-only 값을 변경하는 데 사용되는 반복자로 입력 반복자와 반대로 값을 변경할 수는 있지만 읽을 수는 없다. 순방향(++)으로만 이동이 가능하다.
순방향 반복자 (Forward iterator)	read-write 증가 연산자를 사용하여 순방향으로만 이동이 가능하다.
양방향 반복자 (Bidirectional iterator)	read-write 증가 연산자(++) 또는 감소 연산자(--)를 사용하여 순방향 또는 역방향으로 이동이 가능하다.
임의 접근 반복자 (Random access iterator)	read-write 최상위 레벨의 반복자로 가장 많은 기능을 제공한다. 양방향 반복자의 기능 및 첨자연산자([])를 통해 임의의 요소에 접근할 수 있다. 일반 포인터의 기능을 거의 다 사용할 수 있다.

특성과 속성에 따라 범주가 분류 되어 있듯이 컨테이너에 따라 사용하는 iterator의 종류 또한 다르다.

Container type	Iterator type
vector	임의 접근 반복자 (Random access iterator)
map	양방향 반복자 (Bidirectional iterator)
set	양방향 반복자 (Bidirectional iterator)
stack	none

포인터(pointer)와 반복자(Iterator)의 비교 Pointer와 Iterator는 공통점이 있으면서 분명한 차이점이 존재한다. 포인터는 변수가 메모리에 위치한 주소 즉 변수의 메모리 주소를 저장하는 변수이고 iterator는 배열이나 컨테이너 내의 범주의 요소를 가리키고 반복적으로 순회할 수 있는 객체이다. 더해서 포인터는 증가와 감소 그리고 덧셈의 간단한 수학적인 연산을 수행할 수 있지만 iterator는 위에서 언급한 바와 같이 범주에 따라 연산 수행 여부가 다르다. 그리고 T* 타입의 포인터는 어떤 객체든 T 타입의 객체를 다 가리킬 수 있지만 iterator는 제한적으로 해당 컨테이너 내의 요소에만 접근할 수 있다. 마지막으로 포인터는 증감 연산 시 연속된 메모리 주소에만 접근할 수 있다. 하지만 연속적으로 메모리가 연결되어 있지 않거나 새로운 객체로 복사 시 정상적으로 객체에 접근할 수 없다.

Vector

Sequence container로 동적 연속 배열 형태이다.

Class Prototype

// class prototype
template <class T, class Allocator = std::allocator<T> > class vector;
C++
복사

Member

public:
    typedef T                                        value_type;
    typedef Allocator                                allocator_type;
    typedef typename allocator_type::reference       reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef implementation-defined                   iterator;
    typedef implementation-defined                   const_iterator;
    typedef typename allocator_type::size_type       size_type;
    typedef typename allocator_type::difference_type difference_type;
    typedef typename allocator_type::pointer         pointer;
    typedef typename allocator_type::const_pointer   const_pointer;
    typedef std::reverse_iterator<iterator>          reverse_iterator;
    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
C++
복사

member type	definition	notes
value_type	첫 번째 템플릿 파라미터 (T)
allocator_type	두 번째 템플릿 파라미터 (Alloc)	기본 값 : allocator<value_type>
reference	allocator_type::reference	기본 allocator일 때 : value_type &
const_reference	allocator_type::const_reference	기본 allocator일 때 : const value_type&
pointer	allocator_type::pointer	기본 allocator일 때 : value_type *
const_pointer	allocator_type::const_pointer	기본 allocator일 때 : const value_type *
iterator	value_type에 임의(random)로 접근하는 반복자	const_iterator로 변환할 수 있음
const_iterator	const value_type에 임의(random)로 접근하는 반복자
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	부호가 있는 integral type iterator_traits<iterator>::difference_type과 같다.	보통 ptrdiff_t와 같다
size_type	difference_type의 음이 아닌 값을 나타낼 수 있는 부호 없는 정수 형식	보통 size_t와 같다

Constructor

→ Default constructor ( empty container constructor)

// Description
// Element가 없는 빈 벡터를 구성한다.
explicit vector (const allocator_type& alloc = allocator_type());
C++
복사

→ Fill constructor

// Description
// val의 복사본인 n개의 elements로 컨테이너를 구성하는 constructor
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());
C++
복사

→ Range constructor

// Description
// Parameter로 들어온 first부터 last까지의 범위만큼의 요소를 가진 벡터 컨테이너를 구성
// 기존 범위의 정렬과 동일하게 element의 배치가 이루어진다.
template <class InputIterator>
vector (InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type());
C++
복사

→ Copy constructor

// Description
// Parameter x 내에 있는 각각의 element를 같은 정렬 순으로 복사하여 container를 구성한다.
vector (const vector& x);
C++
복사

→ Parameter

Parameter	Description
alloc	Allocator object로 컨테이너는 이 allocator를 유지하고 사용한다.
n	초기 컨테이너 사이즈
val	컨테이너의 채울 값으로 컨테이너에 있는 n개의 element는 이 값의 복사본으로 초기화 된다.
first, last	input iterator로 범위의 처음과 끝을 가리킨다. 주의 해야할 점은 범위는 처음부터 마지막 사이의 모든 요소를 포함하지만 마지막 요소는 포함하지 않는다.
x	vector object
il	초기 리스트 오브젝트(Initializer_list object) Initializer list 선언자에서 자동으로 생성된다.

Iterator

→ begin

iterator begin();
const_iterator begin() const;
C++
복사

Description 벡터 내의 첫 번째 element를 가리키는 반복자를 반환한다. 요소 하나만을 반환하는 vector::front와는 다르게 random access iterator를 반환한다. 만약 container가 비어있다면, 반환 된 iterator 값은 역참조 되지 않는다. 그리고 만약 vector 객체가 const화 되어있다면, 함수는 const_iterator를 반환한다.

→ end

iterator end();
const_iterator end() const;
C++
복사

Description past-the-element를 참조하는 반복자를 반환하는 iterator past-the-element는 이론적으로 vector의 마지막 요소를 보통 말한다. 이 반복자는 아무 것도 가리키지 않기 때문에 역참조 되어서는 안된다. 보통 begin과 같이 사용되어 특정 범위를 나타낸다. 만약 container가 비어있다면 begin과 같은 값을 반환한다.

rbegin, rend은 위와 반대의 개념을 가진 iterator이다.

Capacity

→ size

// size_type : unsigned integral type
size_type size() const;
C++
복사

vector 안에 있는 요소들의 개수를 반환하는 함수이다.

capacity 함수와는 다르며 실제로 vector안에 존재하는 element의 개수를 반환한다.

→ max_size

size_type max_size() const;
C++
복사

vector가 가질 수 있는 최대의 element 개수를 반환한다.

→ resize

// size_type n : 새로운 컨테이너 사이즈
// value_type val : n이 현재 컨테이너의 사이즈보다 큰 경우 내용이 추가된 vector에 복사 되는 객체
									//지정하지 않은 경우 기본 생성자가 대신 사용된다.
void resize (size_type n, value_type val = value_type());
C++
복사

container가 n개의 elements를 가질 수 있도록 container의 사이즈를 조정한다. 만약, 파라미터로 주어진 n이 현재 container의 사이즈보다 작을 경우, 현재 컨테이너의 첫 번째부터 n개 만큼의 element로 조정된다(줄어든다). 그 뒤의 element들은 삭제되고 파괴된다(removing and destroying them).

→ capacity

size_type capacity() const;
C++
복사

벡터에 현재 할당 된 저장 공간의 크기를 요소 단위로 반환한다.

→ empty

bool empty() const;
C++
복사

벡터가 현재 비어있는 상태인지(size가 0인지)의 여부를 반환한다.

→ reserve

void reserve(size_type n);
C++
복사

vector capacity가 적어도 n개의 element를 수용할 수 있도록 요청한다. 만약, n이 현재 벡터의 크기보다 클 경우 이 함수는 container의 storage를 n 또는 그 이상으로 reallocate 시킨다.

Element access

→ operator[]

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;
C++
복사

벡터 내의 n번째 위치에 있는 element의 reference를 반환 vector::at 함수와 유사하며 vector::at 함수는 bound-checked 하고 만약 범위를 벗어난다면 out_of_range 예외를 던지는 점만 제외하면 동일한 기능을 지닌다.

→ at

reference at (size_type n);
const_reference at (size_type n) const;
C++
복사

벡터 내의 n번째 위치에 있는 element의 reference를 반환 이 함수는 operator[]과 다르게 자동적으로 n이 vector의 적합한 범위 내에 있는지 확인한다. 만약 n이 size와 같거나 더 큰 것과 같이 적합한 값이 아니라면 out_of_range exception을 던진다.

→ front

reference front(); // normal one
const_reference front() const; // if vector qualified as const
C++
복사

vector 내에 있는 첫 번째 요소의 reference를 반환한다. vector::begin 멤버와는 다른 점이 있는데, vector::begin 함수는 iterator를 반환하고 이 함수는 직접적인 reference를 반환한다. 비어있는 vector에서의 이 함수 호출은 undefined behavior을 유발한다.

→ back

reference back();
const_reference back() const;
C++
복사

vector 내에 있는 마지막 요소의 reference를 반환

Modifiers

→ assign

// (1) range function
template <class InputIterator>
void assign (InputIterator first, InputIterator last);

// (2) fill function
void assign (size_type n, const value_type& val);
C++
복사

vector에 있는 기존의 contents를 새로운 contents로 할당하고 이에 따라 size를 수정하는 함수 (1) range function의 경우 새로운 내용은 first부터 last까지 범위의 각 요소로, 동일한 순서로 구성 되어 있다. (2) fill function의 경우 새로운 내용은 n개로, val에서 복사된 요소로 초기화 된다. 기존의 요소는 이 assign 함수의 호출 전에 모두 파괴되고, 새로운 요소로 대체된다. 당연하지만 새로운 요소들의 범위 또는 벡터의 크기가 현재 벡터 컨테이너의 용량을 초과하는 경우 저장 공간이 재 할당된다.

→ push_back

void push_back (const value_type &val);
C++
복사

새로운 element를 vector의 마지막에 추가한다. 이 함수는 효과적으로 container의 size를 하나 증가시키고 기존 vector의 capacity의 크기를 넘어설 경우 자동으로 reallocation을 일으킨다.

→ pop_back

void pop_back();
C++
복사

벡터 안에 있는 마지막 요소를 제거하고 파괴한다. 이 경우 container의 size가 하나 감소한다. container가 비어있는 경우 undefined behavior이다.

→ insert

// (1) single element
iterator insert (iterator position, const value_type& val);
// (2) fill
void insert (iterator position, size_type n, const value_type& val);
// (3) range
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
C++
복사

벡터는 이 insert 함수에 의해 지정된 위치에 요소가 추가되고, 추가된 요소의 개수 만큼 size가 증가한다. 마찬가지로 capacity에 따라 reallocation이 자동으로 진행된다. 벡터는 배열(array)를 기본 저장소로 사용하기 때문에 삽입이 이루어지는 경우 기존의 element의 재배치가 이루어진다.

→ erase

iterator erase (iterator position);
iterator erase (iterator first, iterator last);
C++
복사

vector에서 단일 element를 제거하거나 first와 last로 이루어진 범위만큼의 요소를 제거한다.

→ swap

void swap (vector& x);
C++
복사

받아온 파라미터의

x

의 내용으로 container의 내용을 교환한다. 크기는 다를 수 있지만 유형은 동일하다. 함수 호출 후의 기존의 vector 내용은

x

에 있던 내용이고

x

의 내용은 기존의 vector의 내용과 같다.

→ clear

void clear();
C++
복사

vector의 모든 element들을 제거한다. 그 뒤 container의 size는 0이다. 이 함수는 재할당을 보장하지 않으며 함수의 호출로 벡터 capacity의 변경 또한 보장하지 않는다. reallocation을 사용한 대체재는 swap 함수를 사용하는 것이다.

Allocator

→ get_allocator

allocator_type get_allocator() const;
C++
복사

vector와 연관된 allocator 객체의 복사본을 반환한다.

Stack

Container adaptor로 LIFO 데이터 구조이다. Stack은 기존 컨테이너의 인터페이스를 제한하여 성능이 제한 된 컨테이너이다. 내장 된 LLVM의 CPP STL은 Stack을 deque로 구현하였다. 하지만 위에서 vector를 이미 구현 했기 때문에 vector로 stack을 구현하였다.

Class prototype

template <class _Tp, class _Container /*= deque<_Tp>*/>
class stack;
C++
복사

Member types

public:
    typedef Container                                container_type;
    typedef typename container_type::value_type      value_type;
    typedef typename container_type::reference       reference;
    typedef typename container_type::const_reference const_reference;
    typedef typename container_type::size_type       size_type;

protected:
    container_type c;
C++
복사

Member	Description
Container container_type	The second template parameter (Container) 이 스택의 기반이 되는 underlying container
container_type::value_type value_type	The first template parameter (T) Stack의 elements type
container_type::reference reference	Underlying container의 reference
container_type::const_reference const_reference	Underlying container의 const_reference
container_type::size_type size_type	An unsigned integral type 보통 size_t와 같음

Member functions

→ empty

bool empty() const;
C++
복사

Stack이 비어있는지의 여부를 반환한다. 만약 기반 컨테이너의 사이즈가 0이면 true, 아니면 false를 반환한다.

→ size

size_type size() const;
C++
복사

기반 컨테이너의 element 개수를 반환한다.

→ top

value_type& top();
const value_type& top() const;
C++
복사

Stack의 제일 윗 요소의 레퍼런스를 반환한다.

→ push

void push (const value_type& val);
C++
복사

Stack의 제일 위에 새로운 element를 추가한다.

→ pop

void pop();
C++
복사

Stack의 제일 윗 요소를 제거한다.

map

STL의 map은 red-black tree로 구현되어 있다.

Red-black tree

red-black tree는 이름 그대로 노트의 색이 Red거나 Black인 트리 구조를 말한다. 일반 이진트리와 비슷한 성격을 갖지만 한 쪽으로 치우쳐서 생기는 이진트리의 단점을 보완하기 위해 균형(Balanced) 이진 탐색 트리 형태로 설계된 구조이다.

Red-black tree의 성질은 아래와 같다.

1. Root 노드의 색은 Black이다. 2. 모든 리프 노드는 Black이다. 3. 각 노드의 색은 Red 또는 Black이다. 4. Red 노드의 자식 색은 반드시 Black이다. ( Red - Red로 이어지는 연결은 안 됨. B - B는 가능) 5. 각 노드에서 리프 노드에 다다를 때까지 Black 노드 개수는 모두 같다.

[그림] Red-black 트리의 예시

위 그림에서 알 수 있듯이 Red-black tree는 균형 이진 탐색 트리의 형태이다. 어느 노드를 기준으로 왼쪽에는 자신의 값보다 작은 값을 가진 노드가 오른쪽에는 자신의 값보다 큰 값을 가진 노드가 이어져 있다.

추가적으로 리프 노드의 색이 Black이라고 위에 언급하였는데 그림을 보면 리프 노드가 125, 175, 225, 275 값을 지닌 노드라고 생각할 수 있다. 이 노드의 색은 Red라 옳지 않은 RB Tree라고 생각할 수 있지만 아무런 값을 갖지 않은 NULL(NIL) LEAF도 리프 노드로 간주한다. 그리고 이 NULL LEAF NODE의 색은 Black이다.

Red-black tree의 특징은 약속과 같다. 노드의 삽입과 삭제 연산을 수행 한 뒤에도 위의 다섯가지 특징이 유지되어야 한다는 뜻이다. 아래는 삽입과 삭제 연산을 수행 했을 때 어떻게 노드들의 위치를 조정하고 유효성을 만족시키는지에 대해서 소개한다.

Red-black tree insertion - 삽입 연산

기본적으로 루트를 제외한 삽입되는 노드의 색은 Red이다. 트리가 비어있을 때 처음으로 삽입 되는 노드는 루트 노드이므로 Black이다. 삽입 연산 시 트리의 유효성을 파괴하는 조건은 매우 간단하다. 바로 삽입되는 노드와 부모 노드의 색이 모두 Red 일 때이다. 부모 노드와 삽입 된 자식 노드의 색이 모두 Red이면 대표적으로 4번 특징(성질)을 위배한다.

4. Red 노드의 자식 색은 반드시 Black이다. ( Red - Red로 이어지는 연결은 안 됨. B - B는 가능)

삽입 이후에 트리의 유효성이 파괴 되었다면 적절하게 트리의 구조를 조정해야한다. 이 조정 과정은 크게 두 가지로 나뉜다.

1. Recoloring ( 색상 변경 ) 2. Rotation ( 회전 )

1. Recoloring

노드의 색을 변경하는 과정을 말한다. 이 색상을 변경하는 과정은 부모와 새로 들어온 노드의 색이 모두 Red이고 부모의 형제 즉 Sibling node의 색이 Red일 때 이루어진다.

트리가 위와 같이 구성 되어있다고 할 때 150을 삽입하고자 한다.

이렇게 되면 150과 175 노드 모두 Red이므로 노드를 회전하거나 색을 다시 칠해 줄 필요가 있다. Recoloring을 하는 경우는 Sibling의 색이 Red일 경우에 수행한다.

이해를 돕기 위해 Sibling 노드인 225를 추가했다. 계속해서 Sibling (이하 s) 노드가 Red이고 Parent(이하 p) 노드가 Red라면 p와 s 노드의 색을 Black으로, Parent의 Parent 노드의 색을 Red로 변경하면 된다.

완벽해 보이지만 여기서 생길 수 있는 문제점이 한 가지 더 있다.

pp가 루트 노드라면 pp의 색을 강제로 Black으로 변경시켜 트리의 유효성을 완전하게 할 수 있다. 하지만 pp가 루트 노드가 아니라 상위 트리의 노드 중 하나일 경우라면 문제가 발생할 수 있다.

300의 우측 노드 트리는 생략했다. 이럴 경우 pp의 노드도 Red, 300의 노드도 Red이기 때문에 다시 조정이 필요하다. 마찬가지로 200 값이 담긴 pp 노드를 기준으로 부모 그리고 sibling을 확인하며 재귀적으로 조정을 수행하면 해결된다.

2. Rotation

노드들을 회전하는 과정을 말한다. 노드들을 회전하는 경우는 Sibling 노드의 색이 Black이거나 없는 경우(NIL)에 수행한다.

Rotation의 첫 번째 경우는 새로운 노드 x가 부모의 왼쪽에 삽입 되는 경우이다.

새로 추가 된 노드 x를 기준으로 p노드의 형제인 s노드의 색이 Black인 것을 알 수 있다. Recoloring을 수행 할 때 s의 색이 Red인 경우랑 다르다.

이와 같은 경우 p를 기준으로 right rotate하고 p의 색을 pp로, p의 색을 Black으로 변경 해주면 된다.

Rotation의 두 번째 경우는 새로 추가되는 노드의 위치가 p노드의 오른쪽에 삽입 될 때이다.

이 경우는 Rotation의 첫 번째 경우로 만들어 주는 연산을 수행한다. 그렇게 되기 위해서는 p를 기준으로 left rotate 작업을 수행하면 된다.

결과적으로 p를 기준으로 s의 색이 Black인 첫 번째 경우의 형태가 만들어졌다. 다시 p의 부모인 x를 기준으로 right rotate를 수행한다.

Red-black tree insertion - 삭제 연산

트리에 값을 추가하는 삽입 연산 외에도 값을 삭제하는 연산도 존재한다. 삭제 연산에서는 4번 항목 뿐만 아니라 5번 항목의 위반도 특히 고려를 해보아야 한다.

4. Red 노드의 자식 색은 반드시 Black이다. ( Red - Red로 이어지는 연결은 안 됨. B - B는 가능) 5. 각 노드에서 리프 노드에 다다를 때까지 Black 노드 개수는 모두 같다.

색이 Red인 노드를 삭제하는 것은 큰 문제가 발생하지 않는다. 하지만 색이 Black인 노드의 Black 자식노드를 삭제하게 되면 트리에서 Black 노드가 하나 사라지는 것이기 때문에 5번 특징이 위배되어 밸런스에 큰 문제점을 안겨줄 수 있다. 다시 말하면 부모와 자식 모두 Black일 때 Black 자식 노드를 삭제하면 문제가 발생한다.

위와 같이 삭제하려고 하는 노드를 m, 그 자식을 x라고 했을 때 m을 삭제하는 것은 문제가 없다. pp의 색은 어느 색이 와도 큰 상관이 없다. 왜냐하면 삭제 연산을 진행 한 뒤 rotation이나 coloring 작업을 수행하면 되기 때문이다.

위와 같은 경우 삭제하고자 하는 노드의 색은 Black이고 자식의 노드는 Red이다. 이 경우 대체 된 x의 색을 Black으로 변환시킨다. 당연히 위의 예시는 단일 트리가 아닌 위나 아래에 추가적인 트리가 존재할 수 있다.

문제가 생기는 경우는 m과 x 모두 Black인 경우이다.

다음은 m과 x가 모두 Black일 때 지운 직후의 조정 과정을 소개한다.

먼저 m의 Parent, 위의 그림에서는 pp가 Red일 때의 경우이다. 예시를 조금 수정하면 다음과 같다.

먼저 pp가 p로 변했고, p가 Red일 때의 경우이다.

p가 Red이고 L과 R이 Black, Black일 때 ( S는 당연히 Black일 수 밖에 없다 )

→ 단순히 p와 s의 색을 변경한다.

p가 Red이고 L과 R이 *, Red일 때 ( S는 당연히 Black일 수 밖에 없다 )

여기서 * 와 노드의 색이 White 인 것은 어느 색이든지 올 수 있다는 의미이다.

p를 기준으로 left-rotate → p와 s의 색을 변경 → R의 색을 Black으로 변경

p가 Red이고 L과 R이 Red, Black일 때 ( S는 당연히 Black일 수 밖에 없다 )

여기서 * 와 노드의 색이 White 인 것은 어느 색이든지 올 수 있다는 의미이다.

s를 기준으로 right-rotate → L과 s의 색을 변경 → Case 2로 이동

p를 기준으로 left-rotate → p와 L의 색을 변경 → s의 색을 Black으로 변경

p가 Black이고 S와 L과 R이 Black, Black, Black일 때

모든 노드가 Black일 경우, x의 sibling의 색을 Red로 변경한다. 그러면 x에서 발생 되었던 Black노드의 부족 문제가 p로 전승되는데, 이 경우 p를 기준 노드로 하여 재귀적으로 문제를 해결한다.

p가 Black이고 S와 L과 R이 Black, *, Red일 때

p를 기준으로 left-rotate → p와 s의 색을 바꿈 → R의 색을 Black으로 변경

p가 Black이고 S와 L과 R이 Black, Red, Black일 때

s를 기준으로 right-rotate → L과 s의 색을 바꿈

2번 케이스로 이동하여 진행 조정

p를 기준으로 left-rotate → p와 L의 색을 바꿈 → s의 색을 Black으로 변경

p가 Black이고 S와 L과 R이 Red, Black, Black일 때

p를 기준으로 left-rotate → p와 s의 색을 바꿈.

여기까지 조정을 마쳤을 때 아직 x를 관통하는 경로의 Black 노드는 부족하다. 따라서 x를 기준으로 조정을 계속해야한다. x와 p 그리고 L을 보면 p가 Red일 때의 경우가 떠오른다. 따라서 상단의 1, 2, 3 중 하나를 선택하여 해결하면 된다.

삽입과 삭제 연산 모두 문제가 발생하는 지점을 기준으로 Recoloring, Rotation 등의 연산을 수행한다. 삭제 연산에서는 조정 후에 Black 노드가 부족한 부분이 전이 될 수 있고 이와 같은 현상이 발생 될 시 부족한 부분을 기준으로 재귀적으로 문제를 해결해나가면 된다.

이제 진짜 map의 시작이다.

map은 Associative container로 키와 값 (Key and Value)로 이루어져 있는 구조이다. 이 때 키(Key) 값은 고유하며 중복을 허용하지 않는다. 더해서 STL의 map은 Red-black tree로 구현되어 있기 때문에 자동으로 정렬되어 있고 빠른 검색, 삽입, 삭제 시간을 보장받는다.

Prototype

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;
C++
복사

Member types

public:
    // types:
    typedef Key                                      key_type;
    typedef T                                        mapped_type;
    typedef pair<const key_type, mapped_type>        value_type;
    typedef Compare                                  key_compare;
    typedef Allocator                                allocator_type;
    typedef typename allocator_type::reference       reference;
    typedef typename allocator_type::const_reference const_reference;
    typedef typename allocator_type::pointer         pointer;
    typedef typename allocator_type::const_pointer   const_pointer;
    typedef typename allocator_type::size_type       size_type;
    typedef typename allocator_type::difference_type difference_type;

    typedef implementation-defined                   iterator;
    typedef implementation-defined                   const_iterator;
    typedef std::reverse_iterator<iterator>          reverse_iterator;
    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
C++
복사

Constructor

→ Empty constructor with no element

explicit map (const key_compare& comp = key_compare(),
              const allocator_type& alloc = allocator_type());
C++
복사

→ Range constructor

template <class InputIterator>
map (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());
C++
복사

→ Copy constructor

map (const map& x);
C++
복사

Parameter

Parameter	Description
comp	비교 연산 객체. 두 개의 키를 비교하여 첫 번째 인수가 두 번째 인수보다 작고 앞에 위치한다면 true를, 아니면 false를 반환한다. key_compare()는 container 내에서 사용되는 비교 연산 객체로 template parameter 중 Comp의 별칭으로 사용된다.
alloc	Allocator object로 컨테이너는 이 allocator를 유지하고 사용한다.
first, last	input iterator로 범위의 처음과 끝을 가리킨다. 주의 해야할 점은 범위는 처음부터 마지막 사이의 모든 요소를 포함하지만 마지막 요소는 포함하지 않는다.
x	동일한 유형의 다른 맵 개체(동일한 클래스 템플릿 인수 Key, T, Compare 및 Allocate)로, 이 x의 내용이 복사되거나 획득된다.
il	초기 리스트 오브젝트

Iterators

→ begin

iterator begin();
const_iterator begin() const;
C++
복사

map container의 첫 번째 요소를 참조하는 반복자를 반환한다. 중요한 것은 map은 항상 정렬이 되어 있고 삽입이나 삭제 연산 시 첫 번째 요소가 바뀔 수 있다는 것이다.

→ end

iterator end();
const_iterator end() const;
C++
복사

map container의 마지막 요소를 참조하는 반복자를 반환한다.

→ rbegin

reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
C++
복사

컨테이너의 마지막 요소를 가리키는 역방향 Iterator를 반환한다.

→ rend

reverse_iterator rend();
const_reverse_iterator rend() const;
C++
복사

컨테이너의 첫 번째 요소를 가리키는 역방향 Iterator를 반환한다.

Capacity

→ empty

bool empty() const;
C++
복사

컨테이너가 비어있는지 아닌지의 여부를 반환한다.

→ size

size_type size() const;
C++
복사

map container 내에 있는 요소의 개수를 반환한다.

→ max_size

size_type max_size() const;
C++
복사

map container가 갖고 있을 수 있는 요소의 최대 개수를 반환한다.

Element access

→ operator[]

mapped_type& operator[] (const key_type& k);
C++
복사

k가 컨테이너에 있는 요소의 키와 일치하면 함수는 매핑된 값에 대한 참조를 반환한다.

k가 컨테이너에 있는 요소의 키와 일치하지 않으면 함수는 해당 키로 새 요소를 삽입하고 매핑된 값에 대한 참조를 반환합니다. 이 경우 map에 따로 값을 추가하지 않아도 생성자를 통해 map에 객체가 할당된다.

→ at

mapped_type& at (const key_type& k);
const mapped_type& at (const key_type& k) const;
C++
복사

k로 매핑된 값에 대한 참조를 반환한다. 만약 아무런 값도 매핑 되지 않는다면 out_of_range 오류를 throw한다.

Modifiers

→ insert

//single element	
pair<iterator,bool> insert (const value_type& val);

//with hint
iterator insert (iterator position, const value_type& val);

//range
template <class InputIterator>
void insert (InputIterator first, InputIterator last);
C++
복사

파라미터 position은 val이 삽입 될 위치에 대한 힌트로, val의 키 값보다 앞의 요소를 가리키게 되면 삽입 시간을 최적화 할 수 있다.

pair<iterator, bool>의 pair::first는 새로 삽입된 요소 또는 동일한 키를 갖고 있는 요소를 가리키는 iterator로 설정된다. pair::second는 만약 동일한 키를 가진 요소가 map 내에 있다면 false를, 정상적으로 잘 삽입하였다면 true를 반환한다.

→ erase

void erase (iterator position);
size_type erase (const key_type& k);
void erase (iterator first, iterator last);
C++
복사

범위 혹은 특정 위치의 요소를 삭제한다.

→ swap

void swap (map& x);
C++
복사

컨테이너 요소의 내용을 다른 컨테이너 요소의 내용을 교환한다.

→ clear

void clear();
C++
복사

map container 내의 모든 내용을 삭제한다.

Observers

→ key_comp

key_compare key_comp() const;
C++
복사

키를 비교하기 위해 사용되는 비교 객체의 복사본을 반환한다. 여기서 말하는 비교 객체는 construct 때 결정 되는데 템플릿 매개변수의 세 번째 요소이다. 기본 값은 less이고, operator<와 같은 기능을 수행한다.

이 비교 객체는 요소의 순서를 결정하고 첫 번째 인수가 두 번째 인수보다 먼저 오면 True, 아니면 False를 반환한다. 만약 두 키가 같으면 False를 반환한다.

→ value_comp

value_compare value_comp() const;
C++
복사

map의 value_type을 비교하여 요소의 순서를 비교하는 함수. 여기서 말하는 value_type은 pair<const key_type, mapped_type> 을 말한다. 하지만 이 비교에서 mapped_type은 비교되지 않는다.

Set

Set은 Key값만 갖고 있다는 점에서 map의 Key와 Value의 쌍으로 이루어져있는 특징과 다르다.

이 점을 제외하고는 map과 set의 특징은 같다.

Map과 Set의 연산 별 시간 복잡도

Type	Time complexity
Find	$O(logn)$
Insert	$O(logn)$
Delete	$O(logn)$

Reference

의문의개고수천재 (yongjule’s github)

의문의빡고수천재 (ghan’s github)

컴파일타임

Containers library - cppreference

Iterator -cplusplus

enable_if - cplusplus

Red-black tree

Red-black function

Author	Created	Updated
mcha(Min-jae Cha)	2022. 07. 25.	2022. 08. 25.