1
#include <cstddef>
2
#include <stdexcept>
3

4
const size_t DEFAULT = 10;
5

6
template <typename Elem> class DynamicArray {
7
private:
8
  size_t _size;
9
  size_t _capacity;
10
  Elem *_data;
11

12
  void _expand() {
13
    size_t newCapacity = (_capacity == 0) ? 1 : _capacity * 2;
14
    Elem *data = new Elem[newCapacity];
15
    for (size_t i = 0; i < _size; i++) {
16
      data[i] = _data[i];
17
    }
18
    delete[] _data;
19
    _data = data;
20
    _capacity = newCapacity;
21
  }
22

23
public:
24
  // 构造函数
25
  DynamicArray() : _size(0), _capacity(DEFAULT), _data(new Elem[DEFAULT]) {}
26
  DynamicArray(size_t capacity)
27
      : _size(0), _capacity(capacity), _data(new Elem[capacity]) {}
28
  // 构造拷贝函数
29
  DynamicArray(const DynamicArray &other) {
30
    _size = other._size;
31
    _capacity = other._capacity;
32
    _data = new Elem[_capacity];
33
    for (size_t i = 0; i < _size; i++)
34
      _data[i] = other._data[i];
35
  }
36
  ~DynamicArray() { delete[] _data; }
37

38
  // 实现队尾元素的添加
39
  void push_back(const Elem &elem) {
40
    if (_size == _capacity)
41
      _expand();
42
    _data[_size] = elem;
43
    _size++;
44
  }
45

46
  // 实现队尾元素的删除
47
  void pop_back() {
48
    if (_size == 0)
49
      return;
50
    _size--;
51
  }
52

53
  // 使用 operator 关键字，重载 [] 符号，实现对输入下标的访问
54
  Elem &operator[](size_t idx) { return _data[idx]; }
55
  const Elem &operator[](size_t idx) const { return _data[idx]; }
56
  // 使用 operator 关键字，重载 = 符号，实现通过已有数组的复制操作
57
  DynamicArray &operator=(const DynamicArray &other) {
58
    if (this == &other)
59
      return *this;
60
    delete[] _data;
61
    _size = other._size;
62
    _capacity = other._capacity;
63
    _data = new Elem[_capacity];
64
    for (size_t i = 0; i < _size; i++)
65
      _data[i] = other._data[i];
66
    return *this;
67
  }
68

69
  // 传参引用 实现对输入下标合法性的判断
70
  Elem &at(size_t idx) {
71
    if (idx >= _size)
72
      // 当出现不合法的情况下，使用 throw 抛出异常，并终止当前函数的执行
73
      throw std::out_of_range("No that position!");
74
    return _data[idx];
75
  }
76
  const Elem &at(size_t idx) const {
77
    if (idx >= _size)
78
      throw std::out_of_range("No that position");
79
    return _data[idx];
80
  }
81

82
  // 返回当前元素个数
83
  // 使用 const 来修饰隐含的传递参数
84
  size_t size() const { return _size; }
85

86
  // 返回当前的最大容量
87
  size_t capacity() const { return _capacity; }
88

89
  // 返回当前数组是否为空
90
  bool empty() const { return _size == 0; }
91

92
  // 输出一个元素
93
  Elem &front() {
94
    if (empty())
95
      throw std::out_of_range("DynamicArray is Empty");
96
    return _data[0];
97
  }
98
  // 适应 const
99
  const Elem &front() const {
100
    if (empty())
101
      throw std::out_of_range("DynamicArray is Empty");
102
    return _data[0];
103
  }
104

105
  // 输出一个元素
106
  Elem &back() {
107
    if (empty())
108
      throw std::out_of_range("DynamicArray is Empty");
109
    return _data[_size - 1];
110
  }
111
  const Elem &back() const {
112
    if (empty())
113
      throw std::out_of_range("DynamicArray is Empty");
114
    return _data[_size - 1];
115
  }
116

117
  // 清空 DynamicArray 操作
118
  void clear() { _size = 0; }
119

120
  // 在指定位置插入元素
121
  void insert(size_t pos, const Elem &val) {
122
    if (pos > _size)
123
      throw std::out_of_range("Illegal location");
124
    if (_size == _capacity)
125
      _expand();
126
    if (pos == _size) {
127
      push_back(val);
128
      return;
129
    }
130
    for (size_t i = _size++; i > pos; i--)
131
      _data[i] = _data[i - 1];
132
    _data[pos] = val;
133
  }
134

135
  // 在指定位置删除元素
136
  void erase(size_t pos) {
137
    if (pos >= _size)
138
      throw std::out_of_range("Illegal location");
139
    if (pos == _size - 1) {
140
      pop_back();
141
      return;
142
    }
143
    --_size;
144
    for (size_t i = pos; i < _size; i++)
145
      _data[i] = _data[i + 1];
146
  }
147
};