C++ 数据结构

1.vector

容量/capacity

初始capacity = 0，然后capacity = 1，2，3，4，*1.5扩容

扩容

其中有一个指针指向一片连续的内存空间。当装不下时，系统会自动申请一片更大的空间，把原来的数据拷贝过去，并释放原来的空间

2.智能指针/Smart Pointer

智能指针主要用于管理在堆上分配的内存，它将普通的指针封装为一个栈对象。当栈对象的生存周期结束后，会在析构函数中释放掉申请的内存，从而防止内存泄漏。

为什么要使用智能指针：

智能指针的作用是管理一个指针，因为存在以下这种情况：申请的空间在函数结束时忘记释放，造成内存泄漏。使用智能指针可以很大程度上的避免这个问题，因为智能指针就是一个类，当超出了类的作用域是，类会自动调用析构函数，析构函数会自动释放资源。所以智能指针的作用原理就是在函数结束时自动释放内存空间，不需要手动释放内存空间。

unique_ptr

实现独占式拥有或严格拥有概念
保证同一时间内只有一个智能指针可以指向该对象。它对于避免资源泄露(例如“以new创建对象后因为发生异常而忘记调用delete”)特别有用

unique_ptr<int> p1 (new int[100]); 
//unique_ptr<string> p1 (new string("Hello")); 
unique_ptr<int> p2;                       
p1 = p2;//Error! cannot be referenced, this is a deleted function

C++有一个标准库函数std::move()，让你能够将一个unique_ptr赋给另一个。尽管转移所有权后还是有可能出现原有指针调用（调用就崩溃）的情况。但是这个语法能强调你是在转移所有权，让你清晰的知道自己在做什么，从而不乱调用原有指针。

unique_ptr<string> ps1, ps2;
//临时右值，允许赋值
ps1 = unique_ptr<string>(new string("World!"));
ps2 = move(ps1);
ps1 = unique_ptr<string>(new string("Hello "));
cout << *ps1 << *ps2 << endl;

shared_ptr

shared_ptr 是为了解决 unique_ptr 在对象所有权上的局限性(unique_ptr 是独占的), 在使用引用计数的机制上提供了可以共享所有权的智能指针。

成员函数：

use_count()：返回引用技术个数
unique()：返回是否独占
swap()：交换两个shared_ptr对象（即交换所拥有的对象）
reset()：放弃内部对象所有权，引用计数会减少
get()：返回内部对象（指针），和直接使用对象一样的

string *s1 = new string("Hello ");

shared_ptr<string> ps1(s1);
shared_ptr<string> ps2;
ps2 = ps1;

cout << ps1.use_count() << endl;	//2
cout << ps2.use_count() << endl;	//2
cout << ps1.unique() << endl;	        //0

string *s2 = new string("World!");
shared_ptr<string> ps3(s2);

cout << (ps1.get()) << endl;	        //0123E940
cout << ps1 << endl;	                //0123E940
cout << ps3.get() << endl;		//0123EA18
swap(ps1, ps3);	//交换所拥有的对象
cout << (ps1.get()) << endl;	        //0123EA18
cout << ps3.get() << endl;		//0123E940

cout << ps1.use_count() << endl;	//1
cout << ps2.use_count() << endl;	//2
ps2 = ps1;
cout << ps1.use_count() << endl;	//2
cout << ps2.use_count() << endl;	//2
ps1.reset();	//放弃ps1的拥有权，引用计数的减少
cout << ps1.use_count() << endl;	//0
cout << ps2.use_count() << endl;	//1

weak_ptr

share_ptr智能指针还是有内存泄露的情况，当两个对象相互使用一个shared_ptr成员变量指向对方，会造成循环引用，使引用计数失效，从而导致内存泄漏。

class B;
class A
{
public:
	shared_ptr<B> pb_;
	~A()
	{
		cout << "A delete\n";
	}
};

class B
{
public:
	shared_ptr<A> pa_;
	~B()
	{
		cout << "B delete\n";
	}
};

void fun()
{
	shared_ptr<B> pb(new B());
	shared_ptr<A> pa(new A());
	cout << pb.use_count() << endl;	//1
	cout << pa.use_count() << endl;	//1
	pb->pa_ = pa;
	pa->pb_ = pb;
	cout << pb.use_count() << endl;	//2
	cout << pa.use_count() << endl;	//2
}

int main()
{
	fun();
	return(0);
}

输出：

weak_ptr的一些概念：

是一种不控制对象生命周期的智能指针, 它指向一个 shared_ptr 管理的对象
只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造
它的构造和析构不会引起引用记数的增加或减少
用来解决shared_ptr相互引用时的死锁问题
和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr

成员函数：

expried()：检测所管理的对象是否已经释放 true/false
lock()：获取所管理对象的强引用（shared_ptr），若expried()为true，返回空的share_ptr
use_count()：返回与 shared_ptr 共享对象的引用技术
reset()：将weak_ptr()置为空

cclass B;
class A
{
public:
	shared_ptr<B> pb_;
	~A()
	{
		cout << "A delete\n";
	}
	void print()
	{
		cout << "This is A" << endl;
	}
};

class B
{
public:
	weak_ptr<A> pa_;
	~B()
	{
		cout << "B delete\n";
	}
};

void fun()
{
	shared_ptr<B> pb(new B());
	shared_ptr<A> pa(new A());
	cout << pb.use_count() << endl;	//1
	cout << pa.use_count() << endl;	//1
	pb->pa_ = pa;
	pa->pb_ = pb;
	cout << pb.use_count() << endl;	//2
	cout << pa.use_count() << endl;	//1

	shared_ptr<A> p = pb->pa_.lock();
	p->print();
}

int main()
{
	fun();
	return(0);
}

输出：

1
1
2
1
This is A
A delete
B delete

weak_ptr不能直接访问对象，可通过lock()实现

shared_ptr<A> p = pb->pa_.lock();
p->print();

3. 实现String类

要求：实现String类，实现构造函数，析构函数，拷贝构造函数，赋值函数，和operator==函数。

class String
{
public:
	String(const char* input = nullptr)
	{
		if (input == nullptr)
			data[0] = '\0';
		else
		{
			char* temp = data;
			while (*input != '\0')
			{
				*temp = *input;
				temp++;
				input++;
			}
			*temp = '\0';
		}
	}

	String(const String& input)
	{
		char *temp = input.data;
		char *p = this->data;

		while (*temp != '\0')
		{
			*p = *temp;
			temp++;
			p++;
		}

		*p = '\0';
	}

	String& operator=(const String &input)
	{
		char *temp = input.data;
		char *p = this->data;

		while (*temp != '\0')
		{
			*p = *temp;
			temp++;
			p++;
		}

		*p = '\0';

		return(*this);
	}

	virtual void print()
	{
		char* temp = data;

		while (*temp != '\0')
		{
			cout << *temp;
			temp++;
		}
	}

	bool operator == (const String& input) const
	{
		char* p1 = input.data;
		char* p2 = this->data;

		while (*p1 != '\0' && *p2 != '\0')
		{
			if (*p1 != *p2)
				return(false);
			p1++;
			p2++;
		}

		return(*p1 == *p2);
	}

	~String()
	{
		delete data;
	}

private:
	char* data = new char[100];
};

C++ 数据结构

Comments | NOTHING

取消回复