數組
github地址
數組基礎
- 數組最大的有點：快速查詢。索引快
- 數組最好應用于 “索引有語義” 的情況
- 但并非所有有語義的索引都適用于數組（身份證號）
- 數組也可以處理 ”索引沒有語義“ 的情況
封裝數組類
- 數組類該具備的功能：增 刪 改 查
使用泛型：
- 讓我們的數據結構可以放置 “任何” 數據類型
實現
構造函數
我們希望有兩個構造函數，可以支持給定容量和默認容量，這里默認容量我們設置成 10 :
template<typename T>
MyArray<T>::MyArray() {size_ = 0;capacity_ = 10;data_ = new T[capacity_];std::cout << "調用 MyArray() 構造." << std::endl;
}template<typename T>
MyArray<T>::MyArray(int capacity) {if (capacity <= 0) {std::cout << "MyArray(int) error. Capacity is illegal." << std::endl;throw "MyArray(int) error. Capacity is illegal.";}size_ = 0;capacity_ = capacity;data_ = new T[capacity_];std::cout << "調用 MyArray(int capacity) 構造." << std::endl;
}析構函數
template<typename T>
MyArray<T>::~MyArray() {if (nullptr != data_) {delete[] data_;data_ = nullptr;}size_ = 0;capacity_ = 0;std::cout << "調用 ~MyArray() 析構." << std::endl;
}
拷貝構造和拷貝賦值
首先添加拷貝構造測試：
// 初始化
class ArrayTest : public testing::Test {protected:void SetUp() override {for (int i = 0; i < 10; ++i) {my_array_.AddLast(i);}}void TearDown() override {}MyArray<int> my_array_;
};// 拷貝構造測試
TEST_F(ArrayTest, CopyConstructorTest) {MyArray<int> my_array(my_array_);EXPECT_EQ(10,my_array.GetSize());EXPECT_EQ(9,my_array.Get(9));
}
這里出現了 TEST_F，在TDD實例有例子。
拷貝構造函數和賦值函數：
template<typename T>
MyArray<T>::MyArray(const MyArray &arr) {this->size_ = arr.size_;this->capacity_ = arr.capacity_;this->data_ = new T[capacity_];for (int i = 0; i < size_; ++i) {this->data_[i] = arr.data_[i];}std::cout << "調用 MyArray(const MyArray &arr) 拷貝構造" << std::endl;
}template<typename T>
MyArray<T> &MyArray<T>::operator=(const MyArray<T> &arr) {assert(this != &arr);if (this->data_ != nullptr) {delete[] this->data_;this->data_ = nullptr;}//分配內存this->size_ = arr.size_;this->capacity_ = arr.capacity_;this->data_ = new T[capacity_];//拷貝數據for (int i = 0; i < size_; i++) {//如果是自定義的復雜數據類型，必須對 = 運算賦進行重載, operator=this->data_[i] = arr.data_[i];}std::cout << "調用 = 賦值操作 " << std::endl;return* this;
}
移動構造和移動賦值
首先添加測試用例：
// 移動構造和移動賦值測試
TEST_F(ArrayTest, MoveTest) {// 移動拷貝構造MyArray<int> my_array(std::move(my_array_));// 移動賦值傳入本身 會報錯
// my_array = std::move(my_array);
// EXPECT_EQ(10,my_array.GetSize());
// EXPECT_EQ(9,my_array.Get(9));MyArray<int> my_array1;// 移動賦值my_array1 = std::move(my_array);EXPECT_EQ(10,my_array1.GetSize());EXPECT_EQ(0,my_array.GetSize());EXPECT_EQ(0,my_array_.GetSize());
}
移動構造和移動賦值：
template<typename T>
MyArray<T>::MyArray(MyArray &&arr) noexcept {assert(this != &arr);capacity_ = std::exchange(arr.capacity_, 0);size_ = std::exchange(arr.size_, 0); // 非類類型成員的顯式移動data_ = std::move(arr.data_); // 類類型成員的顯式移動arr.data_ = nullptr;std::cout << "調用 MyArray(const MyArray &&arr) 移動構造函數" << std::endl;
}template<typename T>
MyArray<T> &MyArray<T>::operator=(MyArray<T> &&arr) noexcept {assert(this != &arr);if (this->data_ != nullptr) {delete[] this->data_;this->data_ = nullptr;}//分配內存this->size_ = std::exchange(arr.size_, 0);this->capacity_ = std::exchange(arr.capacity_, 0);this->data_ = new T[capacity_];//拷貝數據for (int i = 0; i < size_; i++) {//如果是自定義的復雜數據類型，必須對 = 運算賦進行重載, operator=this->data_[i] = std::move(arr.data_[i]);}std::cout << "調用 = 移動賦值操作 " << std::endl;return * this;
}
<< 重載
測試用例：
// 測試 << 重載
TEST_F(ArrayTest, OperatorTest) {std::cout << my_array_ << std::endl;
}
實現：
// 內部友元函數實現 重載輸出 << 操作符,這里必須定義成友元
friend std::ostream &operator<<(std::ostream &out, MyArray<T> &obj) {out << "MyArray size = " << obj.size_ << ", Capacity = " << obj.capacity_ << std::endl;out << "MyArray: [";for (int i = 0; i < obj.size_; ++i) {out << obj.data_[i];if (i != obj.size_ - 1)out << ", ";}out << "] ";return out;
}
[] 重載
測試用例：
// [] 測試
TEST_F(ArrayTest, SquareBracketsTest) {EXPECT_EQ(0,my_array_[0]);EXPECT_EQ(1,my_array_[1]);
}
實現：
template<typename T>
T &MyArray<T>::operator[](int index) {if (index < 0 || index >= size_) {std::cout << "[] fail. Index is illegal." << std::endl;throw "[] fail. Index is illegal.";}std::cout << "[] 調用" << std::endl;return this->data_[index];
}
添加元素
首先添加測試：
TEST(ArrayTestNoF, AddAndGet) {MyArray<int> my_array;my_array.Add(0,1);my_array.Add(1,2);my_array.Add(2,3);EXPECT_EQ(1,my_array.Get(0));EXPECT_EQ(2,my_array.Get(1));EXPECT_EQ(3,my_array.Get(2));my_array.AddFirst(4);EXPECT_EQ(4,my_array.Get(0));EXPECT_EQ(4,my_array.GetFirst());my_array.AddLast(5);EXPECT_EQ(5,my_array.Get(4));EXPECT_EQ(5,my_array.GetLast());
}
我們希望提供三個接口：在指定位置插入元素，在頭部和尾部插入元素
后兩個方法可以通過第一個方法實現，我們先實現第一個方法，如下：
template<typename T>
void MyArray<T>::Add(int index, T t) {if (index < -1 || index > size_) {std::cout << "Add fail. Index is illegal." << std::endl;throw "Add fail. Index is illegal.";}if (IsFull()) { Resize(capacity_ * 2);}for (int i = size_; i > index; --i) {data_[i] = data_[i - 1];}data_[index] = t;size_++;
}
后兩個方法在此基礎上:
template<typename T>
void MyArray<T>::AddFirst(T t) {Add(0, t);
}template<typename T>
void MyArray<T>::AddLast(T t) {Add(size_, t);
}
判斷空滿
測試用例：
TEST(ArrayTestNoF, IsEmpty) {MyArray<int> my_array(10);EXPECT_TRUE(my_array.IsEmpty());
}
template<typename T>
bool MyArray<T>::IsFull() const {return size_ == capacity_;
}template<typename T>
bool MyArray<T>::IsEmpty() const {return size_ == 0;
}
獲取容量和大小
測試用例：
TEST_F(ArrayTest, GetSizeAndGetCapacity) {EXPECT_EQ(10,my_array_.GetCapacity());EXPECT_EQ(10,my_array_.GetSize());
}
實現：
template<typename T>
int MyArray<T>::GetSize() const {return size_;
}template<typename T>
int MyArray<T>::GetCapacity() const {return capacity_;
}
對指定位置元素賦值
測試用例：
TEST_F(ArrayTest, Set) {my_array_.Set(0,11);EXPECT_EQ(11,my_array_.GetFirst());
}
實現：
template<typename T>
void MyArray<T>::Set(int index, T t) {if (index < 0 || index >= size_) {std::cout << "Set Fail. Index is illegal." << std::endl;throw "Set fail. Index is illegal.";}if (IsEmpty()) {std::cout << "Set Fail. Array is empty." << std::endl;throw "Set fail. Array is empty.";}data_[index] = t;
}
查找元素
測試用例：
TEST_F(ArrayTest, FindAndContain) {EXPECT_EQ(0,my_array_.Find(0));EXPECT_TRUE(my_array_.Contain(1));EXPECT_FALSE(my_array_.Contain(111));
}
實現：
template<typename T>
int MyArray<T>::Find(T t) const {if (IsEmpty()) {std::cout << "Find fail. Array is empty." << std::endl;throw "Find Fail. Array is empty";}for (int i = 0; i < size_; ++i) {if (data_[i] == t) {return i;}}return -1;
}template<typename T>
bool MyArray<T>::Contain(T t) const {return Find(t) != -1;
}
調整空間
測試用例：
TEST_F(ArrayTest, Resize) {EXPECT_EQ(10,my_array_.GetSize());EXPECT_EQ(10,my_array_.GetCapacity());my_array_.AddLast(10);EXPECT_EQ(11,my_array_.GetSize());EXPECT_EQ(20,my_array_.GetCapacity());for (int j = 0; j < 6; ++j) {my_array_.RemoveLast();}EXPECT_EQ(5,my_array_.GetSize());EXPECT_EQ(20,my_array_.GetCapacity());my_array_.RemoveLast();EXPECT_EQ(4,my_array_.GetSize());EXPECT_EQ(10,my_array_.GetCapacity());
}
全部的源碼傳送門
時間復雜度分析
- 添加操作?????? O(n)
- addLast(e)????? O(1)
- addFirst(e)????? O(n)
- add(index,e)???O(n/2)=O(n)
最壞情況：O(n) , resize() 時間復雜度 O(n)
- 刪除操作 O(n)
- removeLast()?????O(1)
- removeFirst()?????O(n)
- remove(index)????O(n/2)=O(n)
最壞情況：O(n) , resize() 時間復雜度 O(n)
-
修改操作 O(1)
- set(index,e)????O(1)
-
查找操作
- get(index)??? O(1)
- contains(e)??O(n)
- find(e) ? ? ? ? ? O(n)
均攤復雜度分析
由于 resize() O(n) 的存在，所以每次 addLast 和 removeLast 時間復雜度依然是 O(n) ?
resize()復雜度分析
假設當前 capacity 為 8 ，并且每次添加操作都是 addLast , 9 次添加操作觸發一次 resize()， 總共進行了 9 次基本操作， n 次操作才會觸發一次時間復雜度為 O(n) 的操作，平攤到前 n 次操作，相當于前 n 次操作每次復雜度為 O(1+1)=O(1)。
在這個例子中，這樣均攤計算，比計算最壞情況更有意義。
但是會出現這么一種情況：
復雜度振蕩
當 size 為 n 時，我們先后執行 addLast , removeLast , addLast , removeLast , 每一次的操作時間復雜度都是 O(n) 的，出現問題的原因在于 removeLast 的 resize 過于著急 (Eager) 。
解決方案：Lazy
當 size == capacity / 4 時，才將 capacity 減半。
測試是否有內存泄露
使用 valgrind 測試測試用例是否存在內存泄露
valgrind --leak-check=full --show-reachable=yes --trace-children=yes ./ArraysTest
使用 Valgrind 分析 C++ 程序時，有一些問題需要留意。例如，這個程序并沒有發生內存泄漏，但是從 HEAP SUMMARY 可以看到，程序分配了 303 次內存，但卻只釋放了 303 次內存，為什么會這樣呢？
實際上這是由于 C++ 在分配內存時，為了提高效率，使用了它自己的內存池。當程序終止時，內存池的內存才會被操作系統回收，所以 Valgrind 會將這部分內存報告為 reachable 的，需要注意，reachable 的內存不代表內存泄漏，例如，從上面的輸出中可以看到，有 72704 個字節是 reachable 的，但沒有報告內存泄漏。
