반응형

push_back이 필요한 상황에서 vector clear를 간략히 구현한 코드(메모리 할당은 해지되지 않지만 시간이 짧게 걸림)


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
class vector {
public:
    int capacity, sz;
    int *vc;
 
    vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~vector() {
        delete[] vc;
    }
    void push_back(int val) {
        if (capacity == sz) {
            capacity *= 2;
            int *tmp = new int[capacity];
            for (register int i = 0; i < sz; i++)
                tmp[i] = vc[i];
            delete[] vc;
            vc = tmp;
        }
        vc[sz++= val;
    }
    int size() {
        return sz;
    }
    bool empty() {
        return !sz;
    }
    void clear() {
        sz = 0;
    }
    int &operator[](int i) {
        return vc[i];
    }
cs



vector clear를 온전히 구현한 코드(메모리 할당은 해지되나 시간이 오래 걸림)


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
#include <iostream>
 
class _vector {
public:
    int sz;
    int capacity;
    int *vc;
    _vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~_vector() {
        delete[] vc;
    }
    void push_back(int val) {
        if (sz == capacity) {
            int *tmp = new int[capacity];
            for (int i = 0; i < capacity; i++)
                tmp[i] = vc[i];
 
            capacity *= 2;
 
            delete[] vc;
            vc = new int[capacity];
 
            for (int i = 0; i < capacity; i++)
                vc[i] = tmp[i];
        }
        vc[sz++= val;
    }
 
    void clear() {
        capacity = 8;
        sz = 0;
 
        delete[] vc;
 
        vc = new int[capacity];
    }
 
    int size() {
        return sz;
    }
    bool empty() {
        return !sz;
    }
    int &operator [](int i)  {
        return vc[i];
    }
    /*
        여기서 그냥 int operator [](int i) { return vc[i] };를 하면
        값 참조는 되지만 대입이 되지 않는다.
    */
};
 
int main() {
    _vector vc;
    vc.push_back(1);
    printf("%d", vc[0]);
    vc[0= 2;
    printf("%d", vc[0]);
    
    return 0;
}
 
 
 
cs




일반 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/*
This "_vector" class doesn't supply iterator.
Only use dynamic arrays.
*/
template <typename T>
class _vector {
private:
    int _capacity = 0;
    int _size = 0;
    T *vc;
 
public:
    _vector(int size = 1) {
        _capacity = size;
        vc = new T[size];
    }
    ~_vector() {
        delete[] vc;
    }
    int size() { return _size; }
    bool empty() { return !_size; }
    void resize(int size) {
        _capacity = size;
        T *tVc = new T[size];
        for (int i = 0; i < _size; i++)
            tVc[i] = vc[i];
        delete[] vc;
 
        vc = tVc;
    }
    void clear() {
        delete[] vc;
        _capacity = 1;
        _size = 0;
 
        vc = new T[1];
    }
    void push_back(T val) {
        if (_size == _capacity) {
            _capacity *= 2;
            resize(_capacity);
        }
 
        vc[_size++= val;
    }
 
    void pop_back() {
        if (_size == 0)
            return;
 
        vc[--_size] = 0;
    }
    
    void reverse() {
        for (int i = 0; i < _size / 2; i++
        {
            T tmp = vc[i];
            vc[i] = vc[(_size - 1- i];
            vc[(_size - 1- i] = tmp;
        }
    }
    T &operator[](const int &i) constreturn vc[i]; }
    void operator=(const _vector<T> &tVc) {
        _capacity = tVc._capacity;
        _size = tVc._size;
        delete[] vc;
        vc = new T[_capacity];
        for (int i = 0; i < _size; i++)
            vc[i] = tVc[i];
    }
    /*
    If you want use STL std::sort or your own sort
    sort(&vc[0], &vc[vc.size()]);
    */
};
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus




* Iterator은 따로 구현하지 않았습니다.


위의 내용에서 

T &operator[](const int &i) const{ return vc[i]; }를 

T &operator[](const int &i) { return vc[i]; }로 바꾸면 에러가 난다.


https://msdn.microsoft.com/ko-kr/library/ys0bw32s.aspx




반응형

'Applied > 자료구조' 카테고리의 다른 글

[STL] list 구현  (2) 2018.02.28
[STL] Pair 구현  (0) 2018.01.26
트라이(Trie) 자료구조  (6) 2017.10.18
SCC(Strongly Connected Component)  (0) 2017.07.21
우선 순위 큐 소스 코드  (0) 2017.03.24