vector

概要:動的配列
  • reverse_iteratorはサポートしない
  • assignはサポートしない

throw edition

  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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
template <class TType>
class vector
{
public:
    typedef std::size_t size_type;
//  typedef std::ptrdiff_t difference_type;
    typedef TType value_type;
    typedef TType* iterator;
    typedef const TType* const_iterator;

    struct vector_error {};
    struct out_of_range : vector_error{};
    struct bad_alloc : vector_error{};

    vector() : memory_block_(NULL), size_(0), size_alloc_(0), allocator_() {}
    ~vector() { clear(); }

    iterator begin() { return memory_block_; }
    const_iterator begin() const { return memory_block_; }
    iterator end() { return memory_block_ + size_; }
    const_iterator end() const { return memory_block_ + size_; }

    size_type size() const { return size_; }
    size_type capacity() const { return size_alloc_; }
    bool empty() const { return (size_ == 0); }
    void resize(size_type size, const TType& value = TType())
    {
        if (size_ < size) {
            reserve(size);
            for (; size_ < size; ++size_) {
                memory_block_[size_] = value;
            }
        }
//      if (size < size_) { static_cast<void>(erase(begin() + size, end())); }
    }
    void reserve(size_type size)
    {
        if (size_alloc_ < size) { allocate_(size); }
    }
    void shrink_to_fit()
    {
        if (size_ < size_alloc_) { allocate_(size); }
    }
    void push_back(const TType& value)
    {
        if (size_ == size_alloc_) {
            const size_type size_alloc_new = (size_alloc_ == 0) ? 1 : (size_ * 2);
            reserve(size_alloc_new);
        }
        allocator_.construct(&memory_block_[size_], value);
        ++size_;
    }
    void pop_back()
    {
        allocator_.destroy(end() - 1);
        --size_;
    }
    TType& at(size_type index)
    {
        inrange_(index);
        return memory_block_[index];
    }
    const TType& at(size_type index) const
    {
        inrange_(index);
        return memory_block_[index];
    }
    TType& operator[](size_type index) { return memory_block_[index]; }
    const TType& operator[](size_type index) const { return memory_block_[index]; }
    TType& front() { return memory_block_[0]; }
    const TType& front() const { return memory_block_[0]; }
    TType& back() { return memory_block_[size_ - 1]; }
    const TType& back() const { return memory_block_[size_ - 1]; }
    TType* data() { return memory_block_; }
    const TType* data() const { return memory_block_; }
    iterator insert(iterator position, const TType& value = TType())
    {
        const size_type pos = position - begin();
        insert(position, 1, value);
        return (begin() + pos);
    }
    void insert(iterator position, size_type number, const TType& value)
    {
        for (; number != 0; --number) {
            insert(position, &value, &value + 1);
        }
    }
    template < class TInputIterator >
    void insert(iterator position, TInputIterator F_, TInputIterator L_)
    {
        const size_type size_space = size_alloc_ - size_;
        const size_type size_insert = L_ - F_;
        reserve(size() + size_insert);
        // void* std::memcpy(void* s1, const void* s2, size_t n)
        {
            char* S1_ = reinterpret_cast<char*>(end() + size_insert - 1);
            const char* S2_ = reinterpret_cast<const char*>(position + size_insert);
            const char* E_ = reinterpret_cast<const char*>(position);
            do {
                *S1_-- = *S2_--;
            } while (S2_ != E_);
        }
        // void* std::memcpy(void* s1, const void* s2, size_t n)
        {
            char* S1_ = reinterpret_cast<char*>(position);
            const char* S2_ = reinterpret_cast<const char*>(F_);
            const char* E_ = reinterpret_cast<const char*>(L_);
            do {
                *S1_++ = *S2_++;
            } while (S2_ != E_);
        }
    }

    iterator erase(iterator position) { return erase(position, position + 1); }
    iterator erase(iterator F_, iterator L_)
    {
        iterator position = std_copy_(L_, end(), F_);
        destroy_(position, end());
        size_ = position - begin();
        return F_;
    }
    void clear()
    {
        erase(begin(), end());
        allocator_.deallocate(memory_block_, size_alloc_); // std::free(memory_block_);
        memory_block_ = NULL; //< memory_block_ = std::nullptr;
        size_ = 0;
        size_alloc_ = 0;
    }
    class allocator_type
    {
    public:
        TType* reallocate(TType* P_, size_type SE_, size_type SN_)
        {
            // return static_cast<TType*>(std::realloc(P_, SN_ * sizeof(TType)));
            if (SE_ < SN_) {
                char* alloc_new = allocate_char_(SN_ * sizeof(TType));
                // void* std::memcpy(void* s1, const void* s2, size_t n)
                if (SE_ != 0) {
                    char* dest = static_cast<char*>(alloc_new);
                    const char* src = reinterpret_cast<char*>(P_);
                    const char* terminate = src + (SE_ * sizeof(TType));
                    do {
                        *dest++ = *src++;
                    } while (src != terminate);
                    deallocate(reinterpret_cast<char*>(P_), SE_ / sizeof(char));
                }
                P_ = reinterpret_cast<TType*>(alloc_new);
            }
            return P_;
        }
        template< class TType2>
        void deallocate(TType2* P_, size_type){ operator delete(P_); }
        void construct(TType* P_, const TType& V_) { new (static_cast<void*>(P_)) TType(V_); }
        void destroy(TType* P_){ P_->~TType(); }
    private:
        char* allocate_char_(size_type S_){ if (S_ < 0) { S_ = 0; } return ((char*)operator new((size_t)S_ * sizeof (char))); }
    };
private:
    template<class TInputIterator, class TOutputIterator>
    TOutputIterator std_copy_(TInputIterator F_, TInputIterator L_, TOutputIterator O_)
    {
        for (; F_ != L_; ++O_, ++F_) {
            *O_ = *F_;
        }
        return O_;
    }
    void allocate_(size_type S_)
    {
        TType* const memory_block_new = reinterpret_cast<TType*>(allocator_.reallocate(memory_block_, size_alloc_, S_));
        if (memory_block_new == NULL) {
            throw bad_alloc();
        }
        size_alloc_ = S_;
        memory_block_ = memory_block_new;
    }
    void destroy_(iterator F_, iterator L_) { for (; F_ != L_; ++F_) { allocator_.destroy(F_); } }
    void inrange_(size_type N_) const
    {
        if (N_ >= 0 && N_ < size_) { throw out_of_range(); }
    }
    TType* memory_block_;
    size_type size_;
    size_type size_alloc_;
    allocator_type allocator_;
};

nothrow edition

  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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
template <class TType>
class vector_nothrow
{
public:
    typedef bool return_throw_type; //< void
    typedef std::size_t size_type;
//  typedef std::ptrdiff_t difference_type;
    typedef TType value_type;
    typedef TType* iterator;
    typedef const TType* const_iterator;

    vector_nothrow() : memory_block_(NULL), size_(0), size_alloc_(0), allocator_()  {}
    ~vector_nothrow() { clear(); }

    iterator begin() { return memory_block_; }
    const_iterator begin() const { return memory_block_; }
    iterator end() { return memory_block_ + size_; }
    const_iterator end() const { return memory_block_ + size_; }

    size_type size() const { return size_; }
    size_type capacity() const { return size_alloc_; }
    bool empty() const { return (size_ == 0); }
    return_throw_type resize(size_type size, const TType& value = TType())
    {
        if (size_ < size) {
            if (!reserve(size)) {
                return false;
            }
            for (; size_ < size; ++size_) {
                memory_block_[size_] = value;
            }
        }
//      if (size < size_) { static_cast<void>(erase(begin() + size, end())); }
        return true;
    }
    return_throw_type reserve(size_type size)
    {
        if (size_alloc_ < size) { if (allocate_(size)) { return false; } }
        return true;
    }
    return_throw_type shrink_to_fit()
    {
        if (size_ < size_alloc_) { if (allocate_(size)) { return false; } }
        return true;
    }
    return_throw_type push_back(const TType& value)
    {
        if (size_ == size_alloc_) {
            const size_type size_alloc_new = (size_alloc_ == 0) ? 1 : (size_ * 2);
            if (reserve(size_alloc_new)) { return false; }
        }
        allocator_.construct(&memory_block_[size_], value);
        ++size_;
        return true;
    }
    void pop_back()
    {
        allocator_.destroy(end() - 1);
        --size_;
    }
    TType& operator[](size_type index) { return memory_block_[index]; }
    const TType& operator[](size_type index) const { return memory_block_[index]; }
    TType& front() { return memory_block_[0]; }
    const TType& front() const { return memory_block_[0]; }
    TType& back() { return memory_block_[size_ - 1]; }
    const TType& back() const { return memory_block_[size_ - 1]; }
    TType* data() { return memory_block_; }
    const TType* data() const { return memory_block_; }
    iterator insert(iterator position, const TType& value = TType())
    {
        const size_type pos = position - begin();
        insert(position, 1, value);
        return (begin() + pos);
    }
    void insert(iterator position, size_type number, const TType& value)
    {
        for (; number != 0; --number) {
            insert(position, &value, &value + 1);
        }
    }
    template < class TInputIterator >
    return_throw_type insert(iterator position, TInputIterator F_, TInputIterator L_)
    {
        const size_type size_space = size_alloc_ - size_;
        const size_type size_insert = L_ - F_;
        if (!reserve(size() + size_insert)) {
            return false;
        }
        // void* std::memcpy(void* s1, const void* s2, size_t n)
        {
            char* S1_ = reinterpret_cast<char*>(end() + size_insert - 1);
            const char* S2_ = reinterpret_cast<const char*>(position + size_insert);
            const char* E_ = reinterpret_cast<const char*>(position);
            do {
                *S1_-- = *S2_--;
            } while (S2_ != E_);
        }
        // void* std::memcpy(void* s1, const void* s2, size_t n)
        {
            char* S1_ = reinterpret_cast<char*>(position);
            const char* S2_ = reinterpret_cast<const char*>(F_);
            const char* E_ = reinterpret_cast<const char*>(L_);
            do {
                *S1_++ = *S2_++;
            } while (S2_ != E_);
        }
        return true;
    }

    iterator erase(iterator position) { return erase(position, position + 1); }
    iterator erase(iterator F_, iterator L_)
    {
        iterator position = std_copy_(L_, end(), F_);
        destroy_(position, end());
        size_ = position - begin();
        return F_;
    }
    void clear()
    {
        erase(begin(), end());
        allocator_.deallocate(memory_block_, size_alloc_); // std::free(memory_block_);
        memory_block_ = NULL; //< memory_block_ = std::nullptr;
        size_ = 0;
        size_alloc_ = 0;
    }
    class allocator_type
    {
    public:
        TType* reallocate(TType* P_, size_type SE_, size_type SN_)
        {
            // return static_cast<TType*>(std::realloc(P_, SN_ * sizeof(TType)));
            if (SE_ < SN_) {
                char* alloc_new = allocate_char_(SN_ * sizeof(TType));
                // void* std::memcpy(void* s1, const void* s2, size_t n)
                if (SE_ != 0) {
                    char* dest = static_cast<char*>(alloc_new);
                    const char* src = reinterpret_cast<char*>(P_);
                    const char* terminate = src + (SE_ * sizeof(TType));
                    do {
                        *dest++ = *src++;
                    } while (src != terminate);
                    deallocate(reinterpret_cast<char*>(P_), SE_ / sizeof(char));
                }
                P_ = reinterpret_cast<TType*>(alloc_new);
            }
            return P_;
        }
        template< class TType2>
        void deallocate(TType2* P_, size_type){ operator delete(P_); }
        void construct(TType* P_, const TType& V_) { new (static_cast<void*>(P_)) TType(V_); }
        void destroy(TType* P_){ P_->~TType(); }
    private:
        char* allocate_char_(size_type S_){ if (S_ < 0) { S_ = 0; } return ((char*)operator new((size_t)S_ * sizeof (char))); }
    };
private:
    template<class TInputIterator, class TOutputIterator>
    TOutputIterator std_copy_(TInputIterator F_, TInputIterator L_, TOutputIterator O_)
    {
        for (; F_ != L_; ++O_, ++F_) {
            *O_ = *F_;
        }
        return O_;
    }
    return_throw_type allocate_(size_type S_)
    {
        TType* const memory_block_new = reinterpret_cast<TType*>(allocator_.reallocate(memory_block_, size_alloc_, S_));
        if (memory_block_new == NULL) {
            return false;
        }
        size_alloc_ = S_;
        memory_block_ = memory_block_new;
        return true;
    }
    void destroy_(iterator F_, iterator L_) { for (; F_ != L_; ++F_) { allocator_.destroy(F_); } }
    return_throw_type inrange_(size_type N_) const
    {
        return (N_ >= 0 && N_ < size_);
    }
    TType* memory_block_;
    size_type size_;
    size_type size_alloc_;
    allocator_type allocator_;
};