Vector 자료구조

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
using namespace std;
 
template<typename T>
class Vector
{
public:
    Vector() {}
    ~Vector() {}
 
    void push_back(const T& value)
    {
    // 증설 작업
        
    // 데이터 저장
        
    // 데이터 개수 증가                
    }
 
    // 메모리를 증설
    void reserve(int capacity)
    {
        // capacity만큼의 메모리를 할당
        
        // 데이터 복사
 
        // 교체
    }
 
    T& operator[]() { }
 
    int size() {  }         // 실제 방의 개수
    int capacity() {  }   // 할당받은 방의 개수
 
    void clear() {  }
 
private:
    T*        _data = nullptr;
    int        _size = 0;
    int        _capacity = 0;
};
 
int main()
{
   Vector<int> v;
 
    for (int i = 0; i < 100; i++)
    {
        v.push_back(i);
        cout << v[i] << " " << v.size() << " " << v.capacity() << endl;
    }
 
    v.clear();
    cout << v.size() << " " << v.capacity() << endl;
}
 
 
 cs

 

 

데이터 증설 작업

1
2
3
4
5
6
7
8
9
10
11
void push_back(const T& value)
    {
        if (_size == _capacity)
        {
            // 증설 작업
            int newCapacity = static_cast<int>(_capacity * 1.5);
            if (newCapacity == _capacity)
                newCapacity++;
 
            reserve(newCapacity);
        }
 cs

- push_back()으로 데이터를 밀어넣어준다.

- _capacity의 용량이 꽉 찼을때 증설작업을 통해 1.5배 증가시켜서 newCapacity로 다시 할당을 받는다.

- _capacity = 0인 경우를 고려하여 if (newCapacity == _capacity)  newCapacity++; 를 넣어준다.

 

메모리 증설 작업

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 메모리를 증설
    void reserve(int capacity)
    {
        if (_capacity >= capacity)
            return;
 
        // 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;
    }
 cs

 

 

전체코드

더보기 
#include <iostream>
#include <vector>
using namespace std;

template<typename T>
class Vector
{
public:
    Vector() {}
    ~Vector() 
    {
        if (_data)
            delete[] _data;
    }

    // [ ][ ][ ][ ][ ][ ][ ]
    void push_back(const T& value)
    {
        if (_size == _capacity)
        {
            // 증설 작업
            int newCapacity = static_cast<int>(_capacity * 1.5);//특정비율에 맞춰 증설. *1.5일 필요는 없다.
            if (newCapacity == _capacity)
                newCapacity++;

            reserve(newCapacity);
        }

            // 데이터 저장
            _data[_size] = value;

            // 데이터 개수 증가
            _size++;        
    }

    // 메모리를 증설
    void reserve(int capacity)
    {
        if (_capacity >= capacity)
            return;

        // 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; } // 할당받은 방의 개수

    void clear()
    {
        if (_data)
        {
            delete[] _data;
            _data = new T[_capacity];
        }

        _size = 0;
    }

private:
    T*        _data = nullptr;
    int        _size = 0;
    int        _capacity = 0;
};

int main()
{
    vector<int> v;

    v.reserve(100);  // vector의 사이즈를 알고 있으면 reserve로 설정해주는게 좋다. capacity가 변화하는것을 방지할 수 있다.
    cout << v.size() << " " << v.capacity() << endl;

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

    v.clear();
    cout << v.size() << " " << v.capacity() << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <vector>
using namespace std;
 
template<typename T>
class Vector
{
public:
    Vector() {}
    ~Vector() 
    {
        if (_data)
            delete[] _data;
    }
 
    // [ ][ ][ ][ ][ ][ ][ ]
    void push_back(const T& value)
    {
        if (_size == _capacity)
        {
            // 증설 작업
            int newCapacity = static_cast<int>(_capacity * 1.5);
            if (newCapacity == _capacity)
                newCapacity++;
 
            reserve(newCapacity);
        }
 
            // 데이터 저장
            _data[_size] = value;
 
            // 데이터 개수 증가
            _size++;        
    }
 
    // 메모리를 증설
    void reserve(int capacity)
    {
        if (_capacity >= capacity)
            return;
 
        // 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; } // 할당받은 방의 개수
 
    void clear()
    {
        if (_data)
        {
            delete[] _data;
            _data = new T[_capacity];
        }
 
        _size = 0;
    }
 
private:
    T*        _data = nullptr;
    int        _size = 0;
    int        _capacity = 0;
};
 
int main()
{
    vector<int> v;
 
    v.reserve(100);  // vector의 사이즈를 알고 있으면 reserve로 설정해주는게 좋다. capacity가 변화하는것을 방지할 수 있다.
    cout << v.size() << " " << v.capacity() << endl;
 
    for (int i = 0; i < 100; i++)
    {
        v.push_back(i);
        cout << v[i] << " " << v.size() << " " << v.capacity() << endl;
    }
 
    v.clear();
    cout << v.size() << " " << v.capacity() << endl;
}
 
 
 cs

 

 

 

-  v.reserve(100) : vector의 capacity값을 100으로 설정한다.

- vector의 사이즈를 알고 있으면 reserve로 설정해주는게 좋다. reserve로 vector의 capacity를 미리 설정해주면 capacity가 vector의 변경에 의해 capacity가 실시간으로 변화하는것을 방지할 수 있다.

- reserve : vector의 capacity 조작

 

-  v.resize(10) : vector 데이터 개수를 10으로 설정한다.

- 만약 vector의 데이터 개수가 10이 넘는 상태에서  v.resize(10)을 해주면 10 뒤에 있는 값들은 날라간다.

-  resize : vector의 size 조작

'⭐ Programming > 자료구조와 알고리즘' 카테고리의 다른 글

[자료구조] Stack 스택  (0) 2022.07.11
[자료구조] 연결 리스트  (0) 2022.07.10
[자료구조] 동적 배열  (0) 2022.07.03
[자료구조] 배열, 동적 배열, 연결 리스트  (0) 2022.07.03
[자료구조] 선형 vs 비선형 구조  (0) 2022.07.03

티스토리툴바