C++ でのベクトル実装
この記事では、C++ で std::vector に似たクラスを実装する方法を示します。
C++ で malloc および realloc 関数を使用してカスタム vector クラスを実装する
std::vector コンテナは、要素を連続して格納する動的 C スタイルの配列として知られています。正確な実装は実施されていませんが、仕様ではコンテナの一部の機能が必要です。つまり、ベクトルは順序付けられたデータ構造であり、その要素へのランダムアクセスを提供する必要があります。その他の機能は、インターフェイスとして公開されるパブリックメンバー関数として表現できます。その一部を次の例で実装します。実際の std::vector の実装は非常に広範囲に及ぶ可能性があるため、読者が機能を追加する可能性のある出発点を示しているにすぎないことに注意してください。
最初に、MyVector クラスを任意のジェネリック型を格納できる関数テンプレートとして定義する必要があります。次に、要素配列へのポインタや整数オブジェクトなどのコアデータメンバーを含めて、それに応じてサイズ/容量を格納できます。std::vector は、パフォーマンスを向上させるために保存された要素が必要とするよりも大きなメモリチャンクを割り当てる可能性があることに注意してください。この割り当てられたメモリサイズはベクトルの容量と呼ばれ、cap データメンバーに格納されます。新しい MyVector オブジェクトが構築され、現在の要素がゼロに設定されると、固定量（20 オブジェクト）が割り当てられます。
malloc 関数を使用していることに注意してください。これは、現代の C++ では有害と見なされる可能性がありますが、注意して使用すると柔軟性と優れたパフォーマンスを提供します。さらに、malloc で割り当てられたメモリは、realloc 関数で拡張できます。これは、配列のサイズ変更を管理する必要があります。
合計で、このクラスには、動的ベクトルの基礎を形成する 3つのメンバー関数と [] 演算子が含まれています。次のサンプルコードは、push_back、size、および operator[] 関数の実装を示しています。後者の 2つは非常に直感的で理解しやすいものですが、push_back には説明が必要な場合があります。
要素の数が容量を超えたときにオブジェクトが構築された後でのみ、新しいメモリ領域を割り当てる必要があることに注意してください。したがって、push_back 関数のシナリオごとに 2つの個別のパスが必要であり、そのうちの 1つは realloc 関数を呼び出して現在のメモリブロックを拡張します。realloc は、前のメモリ領域へのポインタと新しい領域のサイズ（バイト単位）の 2つのパラメータを受け入れます。呼び出しが成功すると、同じブロックに十分なメモリが見つかったかどうかに応じて、前のポインタと同じか、新しいポインタのいずれかで有効なポインタが返されます。それ以外の場合は、要求が失敗したことを示すために NULL ポインタが返されます。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
template <typename T>
class MyVector {
public:
MyVector() {
cap = alloc;
vector = (T *)malloc(sizeof(T) * alloc);
elem_num = 0;
};
void push_back(const T &data);
void pop_back();
[[nodiscard]] bool empty() const;
[[nodiscard]] size_t size() const;
[[nodiscard]] size_t capacity() const;
T &operator[](size_t pos);
~MyVector();
private:
T *vector = nullptr;
size_t cap;
size_t elem_num;
const int alloc = 20;
};
template <typename T>
MyVector<T>::~MyVector() {
free(vector);
}
template <typename T>
void MyVector<T>::push_back(const T &data) {
if (elem_num < cap) {
*(vector + elem_num) = data;
elem_num++;
} else {
vector = (T *)realloc(vector, sizeof(T) * cap * 2);
cap *= 2;
if (vector) {
*(vector + elem_num) = data;
elem_num++;
}
}
}
template <typename T>
void MyVector<T>::pop_back() {
if (empty()) return;
elem_num--;
}
template <typename T>
T &MyVector<T>::operator[](size_t pos) {
if (pos >= 0 && pos <= elems) return *(this->arr + pos);
throw std::out_of_range("Out of bounds element access");
}
template <typename T>
size_t MyVector<T>::capacity() const {
return cap;
}
template <typename T>
bool MyVector<T>::empty() const {
return elem_num == 0;
}
template <typename T>
size_t MyVector<T>::size() const {
return elem_num;
}
struct MyClass {
int num;
double num2;
};
int main() {
MyVector<MyClass> m1;
m1.push_back({1, 1.1});
m1.push_back({1, 1.2});
m1.push_back({1, 1.3});
m1.push_back({1, 1.4});
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].num << ", " << m1[i].num2 << endl;
}
cout << "/ ------------------- /" << endl;
m1.pop_back();
m1.pop_back();
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].num << ", " << m1[i].num2 << endl;
}
return EXIT_SUCCESS;
}
出力：
1, 1.1
1, 1.2
1, 1.3
1, 1.4
/ ------------------- /
1, 1.1
1, 1.2
MyVector クラスをテストするために、main 関数にいくつかのドライバーコードを含め、要素として格納する MyClass カスタムオブジェクトを定義します。最後に、ベクトルの後ろにある要素を削除する pop_back 関数を追加します。pop_back 関数は、要素の内容の割り当てを解除したり削除したりする必要はありません。呼び出しごとに elem_num メンバーを 1つずつデクリメントするだけで、次の push_back 呼び出しは破棄された要素の位置を書き換えます。オブジェクトがスコープから外れたら、メモリブロックの割り当てを解除することも重要です。したがって、クラスのデストラクタに free 関数の呼び出しを含める必要があります。
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
template <typename T>
class MyVector {
public:
MyVector() {
arr = new T[default_capacity];
cap = default_capacity;
elems = 0;
};
void push_back(const T &data);
void pop_back();
[[nodiscard]] bool empty() const;
[[nodiscard]] size_t size() const;
[[nodiscard]] size_t capacity() const;
T &operator[](size_t pos);
~MyVector();
private:
T *arr = nullptr;
size_t cap;
size_t elems;
const int default_capacity = 20;
};
template <typename T>
MyVector<T>::~MyVector() {
delete[] arr;
}
template <typename T>
void MyVector<T>::push_back(const T &data) {
if (elems < cap) {
*(arr + elems) = data;
elems++;
} else {
auto tmp_arr = new T[cap * 2];
cap *= 2;
for (int i = 0; i < elems; i++) {
tmp_arr[i] = arr[i];
}
delete[] arr;
arr = tmp_arr;
*(arr + elems) = data;
elems++;
}
}
template <typename T>
T &MyVector<T>::operator[](size_t pos) {
if (pos >= 0 && pos <= elems) return *(this->arr + pos);
throw std::out_of_range("Out of bounds element access");
}
template <typename T>
size_t MyVector<T>::size() const {
return elems;
}
template <typename T>
size_t MyVector<T>::capacity() const {
return cap;
}
template <typename T>
void MyVector<T>::pop_back() {
if (empty()) return;
elems--;
}
template <typename T>
bool MyVector<T>::empty() const {
return elems == 0;
}
struct MyClass {
string name;
double num;
};
int main() {
MyVector<MyClass> m1;
m1.push_back({"one", 1.1});
m1.push_back({"two", 1.2});
m1.push_back({"three", 1.3});
m1.push_back({"four", 1.4});
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].name << ", " << m1[i].num << endl;
}
cout << "/ ------------------- /" << endl;
m1.pop_back();
m1.pop_back();
for (size_t i = 0; i < m1.size(); ++i) {
cout << m1[i].name << ", " << m1[i].num << endl;
}
return EXIT_SUCCESS;
}
出力：
one, 1.1
two, 1.2
three, 1.3
four, 1.4
/ ------------------- /
one, 1.1
two, 1.2
