본문 바로가기
개인공부/Rookiss C++ 프로그래밍 입문

Chapter 11 - STL

by 하고싶은건많은놈 2023. 3. 29.

vector #1

STL(Standard Template Library) : 프로그래밍할 때 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리

  • 컨테이너(Container) : 데이터를 저장하는 객체 (자료구조, Data Structure)
  • 벡터(vector)는 컨테이너의 하위 개념
#include <vector>
using namespace std;

vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);

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

vector : 동적 배열
동적 배열은 어떻게 배열을 유동적으로 사용하는가?

  • 메모리 할당시 여유분을 두고 할당함
  • 여유분까지 꽉 찼을시 메모리를 증설함

여유분은 얼마나? 증설은 얼마나? 기존 데이터 처리는?

vector<int> v;
v.size(); // 실제 사용 데이터 개수
v.capacity(); // 어유분을 포함한 용량 개수

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

v.push_back() : 마지막 배열이 가리키는 메모리에 값 저장
v.pop_back() : 마지막 배열이 가리키는 메모리의 값을 제거
v.front, v.back() : 처음 / 마지막 데이터 확인

capacity는 컴파일러에 따라 1.5 ~ 2배씩 늘어남
메모리 증설시 여유분을 늘린 메모리 공간을 확보 후 기존의 메모리를 옮김

v.reserve() 함수를 사용하여 capacity를 지정할 수 있음

  • v.clear()등으로 메모리에 저장된 값을 삭제해도 capacity는 줄어들지 않음
  • 임시 벡터 생성 후 스왑하는 것으로 capacity로 할당된 메모리까지 확실하게 날릴 수는 있음

v.resize() 함수를 사용하여 size를 지정할 수 있음

  • 이 때 capacity도 자동으로 늘어남
  • v.push_back() 함수 사용시 size로 지정한 메모리 이후에 값이 저장되기 때문에 v.resize()로 지정한 메모리에는 각각 값을 대입해주어야 함
  • vector<int> v(1000)과 같이 생성과 동시에 사이즈를 변경할 수 있음

벡터에 다른 벡터를 대입시 벡터가 가지고있던 모든 특성과 데이터가 복사됨

vector #2

반복자(Iterator) : 포인터와 유사한 개념, 컨테이너의 원소(데이터)를 가리키고 다음/이전 원소로 이동 가능

  • 값 참조, 증감 연산자들이 연산자 오버로딩을 통해 지원됨
  • v.begin()은 벡터의 시작 원소를, v.end()는 벡터의 마지막 원소 바로 다음 주소를 가리키는 이터레이터를 반환함
  • 복사 과정을 거치지 않는 전위증감이 후위증감보다 성능이 좋음
  • iterator는 vector 뿐 아니라 다른 컨테이너에도 공통적으로 있는 개념이기 때문에 일반화하여 사용할 수 있음
int main()
{
    vector<int> v(10);

    for (vector<int>::size_type i = 0; i < v.size(); i++)
        v[i] = i;

    vector<int>::iterator it;
    int* ptr;

    it = v.begin();
    ptr = &v[0];

    cout << (*it) << endl;
    cout << (*pt) << endl;

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

    return 0;
}

vector<int>::const_iterator cit = v.cbegin()의 형태로 const처럼 사용 가능
for (vector<int>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it)의 형태로 역순으로 사용 가능

vector #3

vector같은 배열 구조의 경우 처음/중간 위치의 삽입/삭제가 상당히 비효율적임
끝 위치의 삽입/삭제는 아무런 문제 없이 효율적으로 작동함
모든 데이터들이 연속되어있기 때문에 임의 접근(random access)이 가능

v.insert(v.begin() + 2, 5);의 형태로 중간에 삽입할 수 있음
v.erase(v.begin() + 2);의 형태로 중간 데이터를 삭제할 수 있음 

for (vector<int>::iterator it = v.begin(); it != v.end(); )
{
    int data = *it;
    if (data = 3)
        it = v.erase();
    else
        ++it;
}

위와 같이 이터레이터를 사용하는 도중에 erase(), clear() 함수 등으로 조작할 경우 주의가 필요함

vector #4

#include <iostream>
#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 !(*this == right); }
        T& operator*() { return *_ptr; }

    public:
        T* _ptr;
};


template<typename T>
class Vector
{
    public:
        Vector() : _data(nullptr), _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 _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;

    cout << "-------------------" << endl;

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

list #1

#include <list>

int main()
{
    list<int> li;

    for (int i = 0; i < 100; i++)
        li.push_back(i);

    int size = li.size();
    int first = li.front();
    int last = li.back();

    list<int>::iterator itBegin = li.begin();
    list<int>::iterator itEnd = li.end();

    for (list<int>::iterator it = li.begin(); it != li.end(); ++it)
    {
        cout << (*it) << endl;
    }

    li.insert(itBegin, 100);
    li.erase(li.begin());
    li.pop_front();
    li.remove(10);

    return 0;
}

list는 연결 리스트 구조
연결 리스트의 원소는 노드(node)라고 부름
각각의 노드가 불연속한 메모리 위치에 존재하며, 각 노드에 다음 노드의 위치를 가리키는 포인터가 존재함 

class Node
{
    public:
        Node* _next;
        int data;
};

연결 리스트에는 단일 / 이중 / 원형 연결 리스트가 있음
이중 연결 리스트는 Node* _prev 데이터가 추가된 형태
원형 연결 리스트는 head 노드와 tail 노드가 연결되어있는 형태

list #2

데이터들이 연속되어있을 필요가 없으므로, 노드를 연결하는 포인터들의 주소를 변경하는 것으로 간단하게 중간 삽입/삭제가 가능함
마찬가지로 처음/끝 부분의 삽입/삭제 역시 어렵지 않음
단, 임의 접근시 데이터들이 연속되어있지 않기 때문에 해당 데이터를 한번에 찾아갈 수 없으며 따라서 노드를 타고 이동해야한다는 비효율이 발생함

벡터와는 달리 원소 삭제시 노드들을 새롭게 이어주기만 하면 되므로 remove() 함수를 지원함
STL에서의 list에는 마지막 노드 다음에 더미 노드가 존재하여 end()를 가리킴
이터레이터의 + 오퍼레이터가 정의되어있지 않음

중간 삽입/삭제의 처리 자체는 빠르지만, 해당 위치의 노드로 찾아가는 임의 접근은 느림
따라서 이미 특정 위치의 이터레이터가 존재하는 경우에만 중간 삽입/삭제가 빠르다고 할 수 있음

list #3

#include <iostream>
#include <vector>
#include <list>
using namespace std;

template<typename T>
class Node
{
    public:
        Node() : _next(nullptr), _prev(nullptr), _data(T()) {}
        Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value) {}
    public:
        Node* _next;
        Node* _prev;
        T _data;
};

template<typename T>
class Iterator
{
    public:
        Iterator() : _node(nullptr) {}
        Iterator(Node<T>* node) : _node(node) {}

        Iterator& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        Iterator operator++(int)
        {
            Iterator<T> temp = *this;
            _node = _node->_next;
            return temp;
        }

        Iterator& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Iterator operator--(int)
        {
            Iterator<T> temp = *this;
            _node = _node->_prev;
            return temp;
        }

        T& operator*()
        {
            return _node->_data;
        }
        bool operator==(const Iterator& right)
        {
            return _node == right._node;
        }
        bool operator!=(const Iterator& right)
        {
            return _node != right._node;
        }

    public:
        Node<T>* _node;
};

template<typename T>
class List
{
    public:
        List() : _size(0) 
        {
            _header = new Node<T>();
            _header->_next = _header;
            _header->_prev = _header;
        }
        ~List()
        {
            while (_size > 0)
                pop_back();

            delete _header;
        }

        void push_back(const T& value)
        {
            AddNode(_header, value);
        }
        Node<T>* AddNode(Node<T>* before, const T& value)
        {
            Node<T>* node = new Node<T>(value);
            Node<T>* prevNode = before->_prev;

            prevNode->_next = node;
            node->_prev = prevNode;
            node->_next = before;
            before->_prev = node;

            _size++;

            return node;
        }

        void pop_back()
        {
            RemoveNode(_header->_prev);
        }
        Node<T>* RemoveNode(Node<T>* node)
        {
            Node<T>* prevNode = node->_prev;
            Node<T>* nextNode = node->_next;

            prevNode->_next = nextNode;
            nextNode->_prev = prevNode;

            delete node;
            _size--;

            return nextNode;
        }

        int size() { return _size; }

    public:
        typedef Iterator<T> iterator;
        iterator begin() { return iterator(_header->_next); }
        iterator end() { return iterator(_header); }
        iterator insert(iterator it, const T& value)
        {
            return iterator(AddNode(it._node, value));
        }
        iterator erase(iterator it)
        {
            return iterator(RemoveNode(it._node));
        }

    public:
        Node<T>* _header;
        int _size;
};

int main()
{
    List<int> li;
    List<int>::iterator eraseit;

    for (int i = 0; i < 10; i++)
    {
        if (i == 5)
            eraseit = li.insert(li.end(), i);
        else
            li.push_back(i);
    }

    li.pop_back();
    li.erase(eraseit);

    for (List<int>::iterator it = li.begin(); it != li.end(); ++it)
        cout << (*it) << endl;
}

deque

deque : double-ended queue

  • vector, list와 마찬가지로 시퀀스 컨테이너(Sequence Contatiner)에 속함
    • 시퀀스 컨테이너 : 데이터가 삽입 순서대로 나열되는 형태
  • 블록별로 메모리가 저장되는 구조를 가지고있으며, 블록 내의 원소들은 메모리가 연속되어있으나 블록끼리는 메모리가 불연속적임 
int main()
{
    deque<int> dq;

    dq.push_back(1);
    dq.push_front(2);
    cout << dq[0] << endl;
    return 0;
}

처음/끝 부분의 삽입/삭제가 벡터보다 빠르게 동작함
중간 삽입/삭제는 벡터와 같이 비효율적으로 동작
블록별로 카운트를 할 수 있기 때문에 임의접근이 가능함

map #1

벡터, 리스트같은 선형 자료구조는 원하는 조건에 해당하는 데이터를 빠르게 찾을 수 없다는 단점이 있음
따라서 연관 컨테이너 형태의 자료구조를 사용

map : 균형 이진 트리(AVL) 구조, 노드 기반

class Player
{
    public:
        Player() : _playerid(0) {}
        Player(int playerid) : _playerid(playerid) {}
    public:
        int _playerid;
}

class Node
{
    public:
        Node* _left;
        Node* _right;
        int _key;
        Player* _value;
};

int main()
{
    map<int, int> m; // (Key, Value)

    for (int i = 0; i < 100000; i++)
        m.insert(pair<int, int>(i, i * 100));

    for (int i = 0; i < 50000; i++)
    {
        int randomValue = rand() % 50000;
        m.erase(randomValue);
    }

    map<int, int>::iterator findit = m.find(10000);
    if (findit != m.end())
        cout << "찾음" << endl;
    else
        cout << "못찾음" << endl;
}

map #2

erase()의 경우 삭제한 횟수를 리턴값으로 반환
같은 키의 값을 중복 삭제시에도 카운트값만 달라질 뿐 문제는 발생하지 않음

insert()의 경우 중복된 키값을 생성할시 요청이 무시됨
pair<map<datatype, datatype>::iterator, bool>을 반환

  • iterator는 삽입한 키에 해당하는 이터레이터
  • bool은 삽입의 성공 혹은 실패 여부
for (map<int, int>::iterator it = m.begin(); it != m.end(); ++it)
{
    pair<const int, int>* p = (*it);
    int key = p.first; // == it->first
    int value = p.second; // == it->second
}

map<int, int>::iterator findit = m.find(10000);
if (findit !- m.end())
    findit->second = 20000;
else
    m.insert(make_pair(10000, 200));

m[5] = 500;
for (int i = 0; i < 10; i++)
    cout << m[i] << endl;

[] 연산자 사용시 대입을 하지 않더라도 (Key, Value) 형태의 데이터가 추가됨

set, multimap, multiset

multimap : map에서 중복키를 허용 

int main()
{
    multimap<int, int> mm;

    mm.insert(make_pair(1, 100));
    mm.insert(make_pair(1, 200));
    mm.erase(1);

    pair<mulitimap<int, int>::iterator, multimap<int, int> itPair;
    itPair = mm.equal_range(1);
    for(mulitimap<int, int>::iterator it = itPair.first, it != itPair.second, ++it)
        cout << it->fisrt << " " << it->second << endl;

    return 0;
}

multimap에서 erase()할시 해당 키에 속하는 모든 값을 삭제함
equal_range() 함수로 특정 키에 해당하는 첫번째 값의 이터레이터와 마지막 값 다음 이터레이터를 구할 수 있음
따로 구할 경우에는 lower_bound(), upper_bound() 함수 사용 

int main()
{
    multiset<int> ms;

    ms.insert(100);
    ms.insert(100);

    multiset<int>::iterator findit = mm.find(100);
    pair<mulitiset<int, int>::iterator, multimap<int, int> itPair; ms.equal_range(100);
    for (multiset<int>::iterator it = itPair.first, it != itPair.second, ++it)
        cout << *it << endl;
}

set : map과 거의 동일하나 Key값이 Value가 됨
multiset : set에서 중복키를 허용

연습문제

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    srand(static_cast<unsigned int>(time(nullptr)));
    vector<int> v;

    for (int i = 0; i < 100; i++)
    {
        int num = rand() % 100;
        v.push_back(num);
    }

    cout << "-----------------------------\n";

    {
        int number = 50;
        bool found = false;
        vector<int>::iterator it;
        for (it = v.begin(); it != v.end(); ++it)
        {
            if ((*it) == number)
            {
                found = true;
                cout << "found" << endl;
                break;
            }
        }
        cout << (*it) << endl;
    }

    cout << "-----------------------------\n";

    {
        bool found = false;
        vector<int>::iterator it;
        for (it = v.begin(); it != v.end(); ++it)
        {
            if ((*it) % 11 == 0)
            {
                found = true;
                cout << "found" << endl;
                break;
            }
            cout << (*it) << endl;
        }
    }

    cout << "-----------------------------\n";

    {
        int count = 0;
        vector<int>::iterator it;
        for (it = v.begin(); it != v.end(); ++it)
        {
            if ((*it) % 2 == 1)
                count++;
        }
        cout << count << endl;
    }

    cout << "-----------------------------\n";

    {
        vector<int>::iterator it;
        for (it = v.begin(); it != v.end(); ++it)
            cout << (*it) << endl;
        cout << "---------------after change-------------\n";
        for (it = v.begin(); it != v.end(); ++it)
        {
            (*it) *= 3;
            cout << (*it) << endl;
        }
    }
}
저작자표시

'개인공부 > Rookiss C++ 프로그래밍 입문' 카테고리의 다른 글

Chapter 12 - Modern C++  (0) 2023.03.29
Chapter 10 - 콜백 함수  (0) 2023.03.29
Chapter 9 - 디버깅  (0) 2023.03.29
Chatper 8 - 실습  (0) 2023.03.29
Chapter 7 - 동적 할당  (0) 2023.03.29

관련글

댓글

티스토리툴바