std :: vector 클래스 구현
벡터 클래스 기능을 복제하려는 시도에 대한 귀하의 의견을 기다리겠습니다. 특히 복사 생성자 및 크기 조정 방법에 대해 의구심이 있습니다. 복사 생성자가 잠재적으로 메모리 누수를 일으킬 수 있다고 생각하지만 더 나은 방법을 모르겠습니다. 두 가지 크기 조정 방법을 구현했는데 둘 다 작동하는 것 같지만 실제로 어느 것이 더 낫습니까?
#include <iostream>
#include <type_traits>
#include <math.h>
template <typename T>
class Vector {
private:
T* m_Data;
size_t m_Size, m_Capacity;
public:
Vector(size_t cap = 2)
: m_Size(0), m_Capacity(cap) {
m_Data = new T[cap];
}
Vector(size_t size, size_t cap)
: m_Size(size), m_Capacity(cap) {
m_Data = new T[cap];
}
Vector(const std::initializer_list<T>& il)
: Vector(il.size(), il.size() * 2) {
int cnt = 0;
for (const auto& el : il)
m_Data[cnt++] = el;
}
// copy constructor, makes deep copy
Vector(const Vector& v)
: m_Size(v.size()), m_Capacity(v.capacity()) {
m_Data = new T[m_Capacity];
for (size_t i = 0; i < m_Size; i++) {
m_Data[i] = v[i];
}
}
~Vector() {
delete[] m_Data;
}
// void resize(size_t newCapacity) {
// T* newData = new T[newCapacity];
// m_Size = std::min(m_Size, newCapacity);
//
// for (size_t i = 0; i < m_Size; i++)
// newData[i] = std::move(m_Data[i]);
//
// delete[] m_Data;
// m_Data = newData;
// m_Capacity = newCapacity;
// }
void resize(size_t newCapacity) {
char* newData = new char[sizeof(T) * newCapacity];
m_Size = std::min(m_Size, newCapacity);
T* dst = reinterpret_cast<T*>(newData);
for (size_t i = 0; i < m_Size; i++)
new (dst + i) T(m_Data[i]);
delete[] m_Data;
m_Data = reinterpret_cast<T*>(newData);
m_Capacity = newCapacity;
}
void push_back(const T& n) {
if (m_Capacity <= m_Size)
resize(m_Capacity * 2);
m_Data[m_Size++] = n;
}
void push_back(const T&& n) {
if (m_Capacity <= m_Size)
resize(m_Capacity * 2);
m_Data[m_Size++] = std::move(n);
}
void pop_back() {
if (m_Size > 0)
m_Data[--m_Size].~T();
}
void clear() {
for (size_t i = 0; i < m_Size; i++)
m_Data[i].~T();
m_Size = 0;
}
size_t size() const {
return m_Size;
}
size_t capacity() const {
return m_Capacity;
}
bool empty() const {
return m_Size == 0;
}
const T& operator[](size_t index) const {
if (index >= m_Size)
throw "Index out of bounds";
return m_Data[index];
}
T& operator[](size_t index) {
if (index >= m_Size)
throw "Index out of bounds";
return m_Data[index];
}
Vector<T> operator+(const Vector& other) {
if (m_Size != other.size())
throw "Vectors are of different size";
Vector<T> v(m_Size);
for (size_t i = 0; i < m_Size; i++) {
v.push_back(m_Data[i] + other[i]);
}
return v;
}
};
template <
typename T,
typename = typename std::enable_if<std::is_arithmetic<T>::value, T>::type>
int norm(const Vector<T> v) {
int nrm = 0;
size_t n = v.size();
for (int i = 0; i < n; i++) {
nrm += v[i]*v[i];
}
return sqrt(nrm);
}
template <typename T>
std::ostream& operator<<(std::ostream& s, const Vector<T>& v) {
s << "[";
size_t n = v.size();
for (size_t i = 0; i < n; i++) {
s << v[i] << (i < n - 1 ? ", " : "");
}
s << "]";
return s;
}
int main(int argc, const char * argv[]) {
Vector<int>* a = new Vector<int> {1, 2, 3, 4, 5};
Vector<int> b = {5, 4, 3, 2, 6};
Vector<int> c = b;
return 0;
}
감사합니다.
답변
복사 생성자 및 resize()
복사 생성자 (및 다른 생성자 포함)에서를 사용하여 메모리를 할당 new T[...]하지만을 사용하여 메모리를 resize()할당 new char[sizeof(T) * ...]한 다음 new 배치를 사용하여 이전 요소를 복사합니다. 전자는 안전하지만 예상보다 더 많은 생성자를 호출 할 수 있으며, 후자는 제대로 초기화되지 않은 사용되지 않은 용량을 가질 수 있다는 문제가 있지만, delete모든 예약 된 요소에 대해 소멸자를 호출하게됩니다.
안전하고 T예약 된 요소 에 대한 생성자를 호출 하지 않으려면 다음을 일관되게 수행하십시오.
char *m_Data할당 된 메모리를 추적하는 데 사용 합니다 (으로 유지할 수T *m_Data있지만delete[] m_Data직접 호출하지 않도록주의해야 함 )new벡터에 실제 요소를 추가 할 때 항상 배치 사용- 벡터에서 실제 요소를 삭제할 때 항상 "배치 delete"를 사용 합니다.
또한 이상적으로 는 std::move동안 요소 를 원 resize()하지만 특히 T의 이동 생성자가 예외를 throw 할 수있는 경우 까다 롭습니다 .
발산 std::vector
주석에서 이미 논의했듯이 벡터 클래스는 std::vector. 이것은 과제의 요구 사항 때문입니다. 수업 과제 외에를 사용할 수 없지만 std::vector직접 구현해야하는 실제 시나리오도 있습니다 . 이 경우 인터페이스를 최대한 동일 std::vector하게 유지하여 자신의 클래스가 드롭 인 교체인지 확인하고 놀라운 일이 없습니다.
공간을 예약하는 생성자 vs. 요소 할당
size_t인수를 사용 하는 생성자는이를 사용하여 공간을 예약하지만 벡터에 요소를 추가하지 않습니다. 그러나의 해당 생성자 std::vector는 인수를 사용하여 기본적으로 초기화되는 실제 요소를 할당합니다. 또한 수업과 함께 :
Vector<int> v(4, 2);
이렇게하면 초기화되지 않은 두 요소에 대한 공간 만 할당 m_Size되고 4로 설정 되어 크기가 서로 일치하지 않게되며 후속 호출에서 operator[]()오류없이 범위를 벗어납니다. 이것을 다음과 대조하십시오.
std::vector<int> v(4, 2);
이렇게하면 모두 값으로 초기화 된 4 개의 요소로 구성된 벡터가 할당 2됩니다. 그래서 아주 다른 행동입니다.
size_t카운터에 사용
이니셜 라이저 목록, 사용됩니다 생성자에서 int cnt하지만,이 int큰 충분하지 않을 수 있습니다. size_t크기, 개수 및 색인에 일관되게 사용하십시오 .
멤버 이니셜 라이저 목록에서 메모리를 할당 할 수 있습니다.
메모리 할당과 같은 부작용이있는 식을 포함하여 멤버 이니셜 라이저 목록에 더 복잡한 식을 포함 할 수 있습니다. 따라서 다음과 같이 작성할 수 있습니다.
Vector(size_t size, size_t cap)
: m_Data(new T[cap]), m_Size(size), m_Capacity(cap) {}
이 경우에는 실제로 중요하지 않지만 경우에 따라 이점이 있으므로 이렇게 하는 것이 좋습니다 .
적절한 예외 유형을 사용하여 던져
throw임의의 문자열을 사용 하지 말고 예외에 적절한 유형을 사용하십시오. 표준 라이브러리를 사용하려면에서 적합한 유형을 선택하십시오.
if (index >= m_Size)
throw std::out_of_range("Index out of bounds");
표준 라이브러리를 사용할 수없는 경우 최소한 고유 한 예외 유형을 정의하여 호출자가 특정 catch 블록을 사용할 수 있도록합니다. 예를 들어 다음을 수행 할 수 있습니다.
try {
Vector<int> v(100000); // might throw std::bad_alloc if `new` fails
Vector<int> w(10000);
v[100000] = 10; // out of range error
v += w; // vectors of different size
}
catch (std::bad_alloc &e) {
// out of memory
}
catch (std::out_of_bounds &e) {
// handle index out of bounds
}
catch (std::invalid_argument &e) {
// handle operator+[] with an argument of the wrong size
}
문자열을 던지면 하나의 catch-블록 만 가질 수 있으며 ,이 블록은 문자열을 구문 분석하여 무슨 일이 일어나고 있는지 파악해야합니다.
경계 체크인을하지 않는 것을 고려하십시오. operator[]()
표준 라이브러리는 operator[]()성능에 상당한 영향을 미치기 때문에를 사용할 때 경계 검사를 수행하지 않습니다 . at()경계 검사를 수행 하는 별도의 함수 가 있습니다.
Vector<T>내부 에 쓸 필요가 없습니다Vector
당신이 쓰기에 필요하지 않은 클래스 정의 내부 Vector<T>, 단지 쓰기 Vector.
반복기 누락
클래스는 반복자를 구현하지 않으므로 다음과 같이 작성할 수 없습니다.
Vector<int> v(10);
...
for (auto el: v) {
std::cout << el << "\n";
}
클래스에 대한 반복자를 구현하는 것은 좋은 연습입니다.