STL

원본 참고 링크_C++ STL 이란?

  1. 개념 : Standard Template Library의 약자 이다. 프로그래머가 자료구조와 알고리즘을 알지 못해도 사용할 수 있도록 제공되는 라이브러리이며, 편의도구라고 생각하면 될 듯 싶다.
  • 즉, 가이드라인에서 명시하는 내용은, 해당 ‘라이브러리’만 잘 쓰면 된다- 로 해석하면 될 것으로 보입니ㅏㄷ.

“당신에게는 모듈 08 안에서 STL의 사용만을 허락받습니다. 이 의미는 컨테이너(벡터, 리스트, 맵, 그 외에 것들)들은 안되며, 알고리즘(<algorithm> 헤더를 포함할 필요가 있는 어떤 것들)도 마찬가지입니다. 이것들을 사용하면 -42를 받게 됩니다.”

  1. 내부 개념

    • 컨테이너 : 특정 타입의 원소들을 담아 다루기 위한 객체 ex) list, vector, map, deque, multimap 등…
    • 반복자iterator
      • 컨테이너가 보유한 내부 데이터 순회 가능한 객체, 컨테이너의 특정 위치를 나타냅니다.
      • 근래의 객체지향 언어에서 편리한 자료구조가 지원 되지만, C++은 아직 포인터 단위로 이를 관리하고, 따라서 그 위치 접근 및 사용을 위한 읽기 전용 도구가 필요하며, 이를 반복자 가 수행합니다.
      • begin() : 컨테이너의 첫번째 위치를 가리키는 반복자를 반환한다.
      • end() : 컨테이너의 마지막 위치를 가리키는 반복자를 반환한다.(마지막 원소 다음 위치)
      • 반복자 재 정의 연산자
        • * 연산자 : 지금 현재 위치의 원소를 반환
        • ++ 연산자 : 컨테이너의 다음 원소를 가리키는 위치로 반복자가 이동
        • --연산자 : 컨테이너의 이전 원소를 가리키는 위치로 반복자가 이동
        • = 연산자 : 반복자가 참조하는 원소의 위치를 다른 반복자에 할당한다(원소의 위치만 반환한다.)
        • ==, != 연산자 : 두 반복자가 같은 위치를 가리키는지에 대한 비교 연산자.
    • 알고리즘 : 컨테이너 객체의 원소를 다루기 위한 여러 알고리즘으로 검색, 정렬, 수정 등의 역할을 수행한다. (STL 내부 객체의 메소드가 이런 알고리즘을 지원한다. )
    • 결론 : STL = 컨테이너 + 반복자 + 알고리즘

  2. STL 내부요소

    1. vector : 자신의 원소를 동적 배열을 이용하여 관리한다. (heap 영역에 관리되는 영역으로 보인다.) 시스템마다의 차이는 있지만, 추가, 삭제가 비교적 삽입(중간에 값을 추가)하는 것보단 ‘빠르다’.
      • 느리다~ 라는 표현을 하지 않는 이유는, 메모리 관리와 커널의 특성을 생각하면 된다. 메모리 관리 방식에 따라 동적으로 할당된 영역을 관리하는 방법이 다르고, 그러다보면 추가, 삭제, 삽입의 작업이 다를 수 있다.
      • 사용 예시
#include <vector> //중요
#include <iostream>

using namespace std;

int main(void)
{
	vector<int> Vect;

    for(int i = 0; i < 7; i++)
    {
    	Vect.push_back(i);//값을 뒤에 추가
    }

    for(int i = 0; i < (int)Vect.size(); i++)
    {
    	cout << Vect[i] << endl;//보통 배열처럼 값에 접근 가능.
    }

    Vect.clear();//벡터 해제

    return 0;
}
// 기존 예시에서 커스텀인지 모르는 헤더와 자료 타입이 사용되어 빼고 다소 수정했다.
// 반복자로 벡터 조회 예시
#include <vector> //중요
#include <iostream>

using namespace std;

int main(void)
{
	vector<int> Vect;
    vector<int>::iterator pos;//STL 객체 안에는 해당 컨테이너 접근을 위한 반복자가 있다.

    for(int i = 0; i < 7; i++)
    {
    	Vect.push_back(i);//값을 뒤에 추가
    }

    for(pos = Vect.begin(); pos != Vect.end(); pos++)
    {
    	cout << *pos << endl;//이터레이터를 사용하여 벤터 내 원소들에 접근
    }

    Vect.clear();//벡터 해제

    return 0;
}
  1. list : 벡터와 유사하지만 다른 동적 배열
    • 동적 배열이며, 차이점은 존재한다.
    • 벡터는 연속적인 메모리 구조 상에, 단위 만큼 주욱 미리 나열된 배열 공간에서 쓰다가, 부족할 경우 커널이 알아서 더 추가하는 구조이다.
    • 그러나 리스트는 Node라는 각 데이터의 저장공간을 만들고 그 포인터를 연결하여 연속적인 값의 배열처럼 보이게 만든다.
    • 이러한 특성으로 실제 노드 포인터의 삽입이나 생성, 삭제 등이 유연하게 작동하나, 하나의 데이터마다 한개의 포인터를 필요로 한다는 점에서 메모리적 이점이 생길 수도 있다.
    • 하지만 이 부분은 불명확하다. 왜냐면 시스템에서 어떤 식으로 메모리 관리와 할당 내역을 관리하느냐에 따라 상당히 다르게 동작할수도 있고, 벡터 배열의 사이즈 크기가 커진다고 한다면, 쓸데 없이 할당해서 대기하고 있는 공간도 생기게 된다. 이에 비해 필요한 만큼 포인터로 할당하는 구조는, 오히려 더 효율적일 수도 있다.
    • 단 전반적으로 생각해볼 때, 원소만 가지고 있는 벡터보다 포인터 변수가 가진 포인터를 읽어서 다시 재 접근 하는 리스트 방식이 속도면에서나, 효율 면에서 좋지 못하다고 볼 수 있다.
    • 이런 구조로 [] 연산자를 제공하진 않고, 중간 탐색이 한번에 되진 않기에, 처음부터 포인터를 일일히 확인하는 구조로 구현이 되어 있다.
#include <list>
#include <iostream>

using namespace std;

int main(void)
{
	int nNum;
	list<int> lis;
	list<int>::iterator pos;

	for (int i = 0; i < 10; i++)
	{
		lis.push_back(i); // 값을 뒤에 추가
	}
	cout << "현재 배열 값" << endl;
	for (pos = lis.begin(); pos != lis.end(); pos++)
	{
		cout << *pos << endl;
	}
	cout << "0 ~ 9 사이에 삭제할 값을 선택하시오." << endl;
	cin >> nNum;
	for (pos = lis.begin(); pos != lis.end(); pos++)
	{
		if (*pos == nNum)
		{
			lis.erase(pos); // 현 반복자 위치의 노드 삭제
			break ;
		}
	}
	cout << "삭제 후 배열 값" << endl;
	for (pos = lis.begin(); pos != lis.end(); pos++)
	{
		cout << *pos << endl;
	}
	lis.clear();
	return (0);
}
//예시로 제공되는 코드가 정상 작동이 안되서 다시 만들었습니당...

  1. 컨테이너 메소드

    1. size() : 원소 개수를 반환하는 함수
    2. empty() : 컨테이너가 비어 있는지 알려준다.
    3. max_size() : 컨테이너가 가질 수 있는 최대 원소 개수를 반환한다.
    4. reserve() : 용량을 재할당하는 함수
    5. insert() : 인자로 넣어준 반복자 위치에 데이터를 삽입한다.
    6. push_back() : 뒷 부분 데이터를 추가한다.
    7. pop_back() : 마지막 원소를 반환하고 제거한다.
    8. erase() : 인자로 넣어준 반복자 위치의 원소를 제거한다.
    9. clear() : 모든 원소를 제거한다.
    10. resize() : 원소의 개수를 변경한다.
    11. sort() : 오름차순으로 정렬한다.

  2. 알고리즘 메소드 : 자료구조에 관련된 알고리즘을 컨테이너가 메소드로 제공한다.

    1. min_element() : 최소값을 검색하여 반복자 위치를 반환한다.
    2. max_element() : 최대값을 검색하면 반복자 위치를 반환한다.
    3. find() : 값으로 검색하며 있으면 반복자 위치를, 없으면 end() 위치를 반환한다.
    4. reverse() : 역순으로 배열(정렬이 아니라, 지금 원소 위치를 역순으로 바꾸는 것이다. )
    5. sort() : 오름차순으로 정렬한다.