VisualStudio/C++

[C++] STL(Standard Template Library)

usingsystem 2023. 7. 25. 17:55
728x90

STL 이란?

C++로 프로그래밍할 때 필요한 자료구조나 알고리즘들을 템플릿으로 제공하는 라이브러리이다.

 

컨테이너(Container)

데이터를 저장하는 객체 (자료구조 Data Structure)를 포함한다.

시퀀스 컨테이너 - vector, list, deque 3가지를 제공한다.

vector

vector는 동적 배열로 동적으로 커지는 배열을 의미한다. 미리 여분의 공간을 생성하며 여분의 공간을 모두 소모하면 추가로 여분의 공간을 지속적으로 생성하면서 동적으로 배열을 만든다.

vector는 원소가 하나의 메모리 블록에 연속하게 저장돼야 하는 특징을 가지고 있다.

size 

동적 배열 안에 실제로 사용하고 있는 크기를 리턴하며 데이터가 삭제되면 함께 줄어든다.

capacity

실제사용하고 있는 크기뿐 아니라 여분의 공간의 크기도 합하여 리턴한다. 초반에 빈번하게 일어나는 capacity를 줄이기 위해서 미리할당하는 reserve와 resize가 존재하며 한번 증가한 capacity는 size와 다르게 줄어들지 않는다. 하지만 capacity를 줄이기 위해 swap을 사용할 수 있다.

vector<int>() v(1000);
vector<int>().swap(v);

reserve와 resize

동적배열을 미리 할당하는 방법에서 동일하지만 resize는 데이터를 함께 초기화하여 size와 capacity의 크기가 동일하지만 reserve는 capacity만 늘리기 때문에 size와 capacity의 크기가 다르다.

 

iterator(반복자)

포인터와 유사한 개념으로 컨테이너 데이터를 가리키고 컨테이너의 다음 이전 원소로 이동 가능하다.

단순히 컨테이너의 주소뿐 아니라 데이터등 정보도 포함한다.

size_type을 사용하여 반복자의 타입으로 변환할 수 있다.

vector<int>::size_type

begin()과 end

begin은 vector의 첫 번째 원소 주소를 반환하고 end는 끝나는 마지막 원소의 다음 주소를 반환한다.

vector<int>::interator itBegin = v.begin();
vector<int>::interator endBegin = v.end();

begin과 end를 사용하여 vector의 반복문에 응용할 수 있다. iterator로 반복문을 돌릴 때는 ++it처럼 ++을 앞에 사용하는 게 성능 면에서 더 월등하다. ++이 뒤로 가있을 경우 임시적으로 복사를 한번 더 하기 때문이다.

	vector<int> v(10);
	for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
		cout << *it << endl;

다양한 iterator

  • const_iterator
    • const int* 느낌으로 수정을 하지 않고 읽기만 하고 싶을 때 사용한다
  • reverse_iterator
    • 역방향으로 interator 한다.

vector 삽입과 삭제

vector는 원소가 하나의 메모리 블록에 연속하게 저장돼야 하는 특징을 가지고 있다.

중간 삽입 삭제 처음 삭제나 삽입은 위특징으로 인해 vector의 중간 삽입 삭제는 매우 비효율 적이며 끝 삽입 삭제는 효율 적이다. 그렇기 때문에 문법에서도 push_back과 pop_back만을 제공한다.

중간 삽입/삭제

중간 삽입 방법

	vector<int> v(10);
	v.insert(v.begin() + 2, 5); //두번공간에 데이터를 5 추가

중간 삭제 방법

	vector<int> v(10);
	v.erase(v.begin() + 2); //두번 째 데이터를 삭제

반복 삭제 방법

	//홀수인 데이터를 일괄삭제
		for (vector<int>::iterator it = v.begin(); it != v.end();)
		{
			if (//조건)
			{
				it = v.erase(it);
			}
			else
			{
				++it;
			}
		}

임의 접근

배열 형태 index로 접근할 수 있다.

	vector<int> v(10);
	v[2] = 3;

Vector구현

#include <iostream>
#include <iomanip>
#include "CPP_Study.h"
#include <vector>
using namespace std;

template<typename T>
class Iterator
{
public:
	Iterator() : _ptr(nullptr)
	{
	}

	Iterator(T* ptr) : _ptr(ptr)
	{
	}

	Iterator& operator++()
	{
		_ptr++;
		return *this;
	}

	Iterator operator++(int)
	{
		Iterator temp = *this;
		_ptr++;
		return temp;
	}

	Iterator& operator--()
	{
		_ptr--;
		return *this;
	}

	Iterator operator--(int)
	{
		Iterator temp = *this;
		_ptr--;
		return temp;
	}
	Iterator operator+(const int count)
	{
		Iterator temp = *this;
		temp._ptr += count;
		return temp;
	}
	Iterator operator-(const int count)
	{
		Iterator temp = *this;
		temp._ptr -= count;
		return temp;
	}

	bool operator==(const Iterator& right)
	{
		return _ptr == right._ptr;
	}
	bool operator!=(const Iterator& right)
	{
		return _ptr != right._ptr;
	}

	T& operator*()
	{
		return *_ptr;
	}

public:
	T* _ptr;
};

template<typename T>
class Vector
{
public:
	Vector() : _data(nullptr), _count(0), _size(0), _capacity(0)
	{

	}
	~Vector() {
		if (_data)
			delete[] _data;
	}


	void push_back(const T& val)
	{
		if (_size == _capacity)
		{
			//증설작업
			int newCapacity = static_cast<int>(_capacity * 1.5);

			if (newCapacity == _capacity)
				newCapacity++;

			reserve(newCapacity);
		}

		_data[_size] = val;
		_size++;
	}

	void reserve(int capacity)
	{
		_capacity = capacity;

		T* newData = new T[_capacity];

		for (int i = 0; i < _size; i++)
			newData[i] = _data[i];

		if (_data)
			delete[] _data;

		_data = newData;
	}

	T& operator[](const int pos)
	{
		return _data[pos];
	}

	int size() { return _size; }
	int capacity() { return _capacity; }

public:
	typedef Iterator<T> iterator;

	iterator begin() { return iterator(&_data[0]); }
	iterator end() { return begin() + _size; }

private:
	T* _data;
	int _count;
	int _size;
	int _capacity;
};


int main()
{
	Vector<int> v;

	v.reserve(100);
	for (int i = 0; i < 100; i++)
	{
		v.push_back(i);
		cout << v.size() << " " << v.capacity() << endl;
	}

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	for (Vector<int>::iterator it = v.begin(); it != v.end(); ++it)
	{
		cout << *it << endl;
	}
	return 0;
}

list(연결리스트)

list는 연결리스트로 동적배열과 차이점이 존재한다. 임의 접근인 인덱스로 접근이 허용되지 않으며 노드를 기반으로 동작한다. 노드기반으로 동작한다는 것 은 Node안에 다른 Node의 주소를 가지고 있어 주소를 연결 연결하여 이어지는 방법으로 노드가 어떻게 이어져있느냐에 따라 단일 연결리스트,  이중연결리스트, 원형 연결리스트 3가지가 존재한다. 다음노드의 주소값을 단순히 가지고 있기 때문에 동적리스트처럼 연속적인 주소를 가지고 있지 않는다. 그렇기 때문에 삽입 삭제에서 vector와 다르게 맨 앞 삽입을 뿐 아니라 중간에 삽입 삭제 또 한 빠르게 가능하다. 

 

정리

- 동적 배열과 다르게 빠르게 삽입 삭제가 가능하며 인덱스 접근이 허용되지 않기 때문에 select를 위해서는 전체를 확인해야 한다. 결국 select는 느리다. 그러면 여기서 모순점이 존재한다. 삭제하기 위해서는 위치를 찾아 삭제를 해야 하는데 그러면 검색을 해야 하기 때문이다. 결국 찾고자 하는 대상을 위해 select를 한 후 자리를 찾아서 지워야 한다. 이런 부분을 방지하기 위해 iterator에 내가 찾고자 하는 주소를 저장하고 있다면 빠르게 삭제가 가능하다.

 

  • 단일 연결리스트

[1]->[2]->[3]->[4]

  • 이중 연결리스트

[1]<->[2]<->[3]<->[4]

  • 원형 연결리스트

[1]<->[2]<->[3]<->[4]<->[4]

deque

deque는 동적리스트(vector)와 연결리스트(list)의 중간의 성질을 갖는다. 

deque의 여분의 공간이 모두 찬다면 동적리스트처럼 연속해서 옆으로 공간을 할당하는 것 이 아닌 연결리스트처럼 새로운 영역을 새로 추가로 할당하지만 데이터를 하나만 저장하는 것이 아니다. vector처럼 여러 개를 가지고 있다. 즉 필요할 때마다 새로운 공간을 할당하기 때문에 연결리스트처럼 capacity 또한 존재하지 않는다.

 

연관 컨테이너(Associate Container)

앞에서 설명한 vector와 list는 검색에 매우 취약하다. 그래서 나온 게 연관 컨테이너로 데이터를 밀어 넣는 순서가 아닌 데이터가 실질적으로 가지고 있는 값에 따라서 움직이게 된다.

map

map은 균형이진트리(AVL)로 만들어져 있으며 노드 기반으로 개발되어 있다. pair을 사용하여 key, value의 상을 가지고 양 옆 노드의 주소를 가지고 있다. C#의 Dictionary, HashTable과 동일한 형태이지만 차이점이 있다면 C# Dictionary는 중복키를 허용하지 않고 정렬되지 않은 HashMap이고 C++의 map은 중복키를 허용하지는 않지만 오류를 표시하지는 않고 정렬된 Map이다.

삽입

  • insert
    • 중복 key값을 넣어도 오류를 발생시키지 않지만 수정도 되지 않는다. pair iterator을 사용해서 insert의 반환 값을 받으면 first에는 key, value가 들어있고 second에는 insert 성공을 알려준다.
	map<int, int> m;
	m.insert(pair<int, int>(1, 9999)); //insert
	pair<map<int, int>::iterator, bool> ok;
	ok = m.insert(make_pair(2, 100));
    ok = m.insert(make_pair(2, 200));

	if (ok.second == true)
	{
		cout << "Insert 성공" << endl;
	}

없으면 추가 있으면 수정

  • find
//없으면 추가, 있으면 수정1
	map<int, int>::iterator findIt = m.find(10000);
	if (findIt != m.end())
	{
		findIt->second = 200;
	}
	else
	{
		m.insert(make_pair(100000, 200));
	}
  • [ ]
    • []를 사용하여 해당 키값이 없다면 추가하고 있다면 수정할 수 있다.
m[10000] = 200;

[]를 사용하면 대입을 하지 않더라도 key value 값이 초기값으로 insert 된다.

	//대입을 하지 않더라도 key/value 형태의 데이터가 추가된다.
	for (int i = 0; i < 10; i++)
	{
		cout << m[i] << endl; 
	}

삭제

  • erase
	m.erase(1);

set

map과 비슷 하지만 약간의 차이점이 존재한다. key값과 value값이 같기 때문에 사용이 편리하지만 []를 사용하여 key값에 접근하여 수정하는 것 은 불가능하다. map처럼 key값과 value값이 다를 때 성립하기 때문이다.

multimap

map과 유사하며 차이점은 중복 key값을 허용한다.

multiSet

set과 유사하며 차이점은 중복 key값을 허용한다.

알고리즘(algorithm)

  • find
    • vector 범위에 사이에 원하는 값을 찾아준다.
		vector<int>::iterator it;
		vector<int>::iterator it = find(v.begin(), v.end(), number);
  • find_if
    • vector 범위에  조건에 맞는 값을 찾아준다.
//짝수인 지 
		struct CanDivideBy11 {
			bool operator()(int n) {
				return  (n % 2) == 0;
			}
		};
		find_if(v.begin(), v.end(), CanDivideBy11());
  • count_if
    • vector 범위에 조건에 맞는 카운터 개수를 찾아준다.
//홀수의 개수
int n = count_if(v.begin(), v.end(), [](int n) {return (n % 2) != 0; });
  • all_of
    • 모든 데이터가 조건에 만족하는지
vector v;
bool b1 = all_of(v.begin(), b.end(), [](int n){ return (n%2) !=0;})
  • any_of
    • 조건에 맞는 데이터가 하나라도 존재하는지
vector v;
bool b1 = any_of(v.begin(), b.end(), [](int n){ return (n%2) !=0;})
  • none_of
    • 조건에 맞는 데이터가 하나라도 존재하지 않는지
vector v;
bool b1 = none_of(v.begin(), b.end(), [](int n){ return (n%2) !=0;})
  • for_each
    • 모든 데이터 스캔
vector v;
for_each(v.begin(), b.end(), [](int n){ return n*3;})
  • remove_if
    • 삭제를 하는 것 이 아니라. 조건에 따라 순서를 제정의 하여 불필요한 데이터들의 첫 번째 주소 값을 반환한다. 이렇게 얻은 주소값을 통해 erase를 사용하여 완전히 삭제해 준다.
//버전1
	vector<int> v;
	vector<int>::iterator it = remove_if(v.begin(), v.end(), [](int n) {return n = 4; });
	v.erase(it, v.end());
    
 //버전2
 	vector<int> v;
	v.erase(remove_if(v.begin(), v.end(), [](int n) {return n = 4; }, v.end());

 

728x90
저작자표시

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

[C++] 포인터와 참조  (0) 2024.05.13
[C++] 스마트 포인터 (shared_ptr, weak_ptr, unique_ptr)  (0) 2023.07.31
[C++] 형변환 (static_cast, dynamic_cast, const_cast, reinterpret_cast)  (0) 2023.07.24
[C++] 타입변환에서 소멸자 Virtual 사용  (0) 2023.07.24
[C++] 얕은복사 VS 깊은복사  (0) 2023.07.24

'VisualStudio/C++'의 다른글

  • 현재글[C++] STL(Standard Template Library)

관련글

티스토리툴바