企业网站标签页是什么,建个什么网站赚钱,南京网站设计公司济南兴田德润优惠吗,免费海报制作数组
github地址
数组基础
数组最大的有点#xff1a;快速查询。索引快数组最好应用于 “索引有语义” 的情况但并非所有有语义的索引都适用于数组#xff08;身份证号#xff09;数组也可以处理 ”索引没有语义“ 的情况
封装数组类
数组类该具备的功能#xff1a;增…数组
github地址
数组基础
数组最大的有点快速查询。索引快数组最好应用于 “索引有语义” 的情况但并非所有有语义的索引都适用于数组身份证号数组也可以处理 ”索引没有语义“ 的情况
封装数组类
数组类该具备的功能增 删 改 查
使用泛型
让我们的数据结构可以放置 “任何” 数据类型
实现
构造函数
我们希望有两个构造函数可以支持给定容量和默认容量这里默认容量我们设置成 10 :
templatetypename T
MyArrayT::MyArray() {size_ 0;capacity_ 10;data_ new T[capacity_];std::cout 调用 MyArray() 构造. std::endl;
}templatetypename T
MyArrayT::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;
}
析构函数
templatetypename T
MyArrayT::~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 {}MyArrayint my_array_;
};// 拷贝构造测试
TEST_F(ArrayTest, CopyConstructorTest) {MyArrayint my_array(my_array_);EXPECT_EQ(10,my_array.GetSize());EXPECT_EQ(9,my_array.Get(9));
}这里出现了 TEST_F在TDD实例有例子。
拷贝构造函数和赋值函数
templatetypename T
MyArrayT::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;
}templatetypename T
MyArrayT MyArrayT::operator(const MyArrayT 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) {//如果是自定义的复杂数据类型必须对 运算赋进行重载, operatorthis-data_[i] arr.data_[i];}std::cout 调用 赋值操作 std::endl;return* this;
}移动构造和移动赋值
首先添加测试用例
// 移动构造和移动赋值测试
TEST_F(ArrayTest, MoveTest) {// 移动拷贝构造MyArrayint 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));MyArrayint 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());
}移动构造和移动赋值
templatetypename T
MyArrayT::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;
}templatetypename T
MyArrayT MyArrayT::operator(MyArrayT 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) {//如果是自定义的复杂数据类型必须对 运算赋进行重载, operatorthis-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, MyArrayT 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]);
}实现
templatetypename T
T MyArrayT::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) {MyArrayint 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());
}我们希望提供三个接口在指定位置插入元素在头部和尾部插入元素
后两个方法可以通过第一个方法实现我们先实现第一个方法如下
templatetypename T
void MyArrayT::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_;
}后两个方法在此基础上:
templatetypename T
void MyArrayT::AddFirst(T t) {Add(0, t);
}templatetypename T
void MyArrayT::AddLast(T t) {Add(size_, t);
}判断空满
测试用例
TEST(ArrayTestNoF, IsEmpty) {MyArrayint my_array(10);EXPECT_TRUE(my_array.IsEmpty());
}templatetypename T
bool MyArrayT::IsFull() const {return size_ capacity_;
}templatetypename T
bool MyArrayT::IsEmpty() const {return size_ 0;
}获取容量和大小
测试用例
TEST_F(ArrayTest, GetSizeAndGetCapacity) {EXPECT_EQ(10,my_array_.GetCapacity());EXPECT_EQ(10,my_array_.GetSize());
}实现
templatetypename T
int MyArrayT::GetSize() const {return size_;
}templatetypename T
int MyArrayT::GetCapacity() const {return capacity_;
}对指定位置元素赋值
测试用例
TEST_F(ArrayTest, Set) {my_array_.Set(0,11);EXPECT_EQ(11,my_array_.GetFirst());
}实现
templatetypename T
void MyArrayT::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));
}实现
templatetypename T
int MyArrayT::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;
}templatetypename T
bool MyArrayT::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(11)O(1)。
在这个例子中这样均摊计算比计算最坏情况更有意义。
但是会出现这么一种情况
复杂度振荡
当 size 为 n 时我们先后执行 addLast , removeLast , addLast , removeLast , 每一次的操作时间复杂度都是 O(n) 的出现问题的原因在于 removeLast 的 resize 过于着急 (Eager) 。
解决方案Lazy
当 size capacity / 4 时才将 capacity 减半。
测试是否有内存泄露
使用 valgrind 测试测试用例是否存在内存泄露
valgrind --leak-checkfull --show-reachableyes --trace-childrenyes ./ArraysTest使用 Valgrind 分析 C 程序时有一些问题需要留意。例如这个程序并没有发生内存泄漏但是从 HEAP SUMMARY 可以看到程序分配了 303 次内存但却只释放了 303 次内存为什么会这样呢 实际上这是由于 C 在分配内存时为了提高效率使用了它自己的内存池。当程序终止时内存池的内存才会被操作系统回收所以 Valgrind 会将这部分内存报告为 reachable 的需要注意reachable 的内存不代表内存泄漏例如从上面的输出中可以看到有 72704 个字节是 reachable 的但没有报告内存泄漏。
