程序复杂度判断

时间复杂度

空间复杂度

命名空间 namespace

在c++中，名称（name）可以是符号常量、变量、函数、结构、枚举、类和对象等等。工程越大，名称互相冲突性的可能性越大。为了避免，在大规模程序的设计中，以及在程序员使用各种各样的C++库时，这些标识符的命名发生冲突，标准C++引入关键字namespace（命名空间/名字空间/名称空间）。

用法：using namespace xxxx

关键字 new

new创建类对象，使用完后需使用delete删除，跟申请内存类似。

释放单个空间直接用delete，连续释放多个空间用delete[].

CTest* pTest = new CTest();
delete pTest;
1）A  a；在栈(stack)上分配空间；
2）A  *a；只是声明，还没有分配空间；
3）A  *a= new A；在堆(heap)上分配空间；

C++有三种方法创建对象

#include <iostream>  
using namespace std;  
class  Test {   
  private:  
  public:  
      add()
      {
         int x,y,sum;
         x=5;
         y=5;
         sum=x+y;
         cout<<sum<<endl;
     }
 };  
 void main()  
 {  
    Test test1;              //栈中分配  ，由操作系统进行内存的分配和管理
    Test test2 = Test();       //栈中分配  ，由操作系统进行内存的分配和管理
    Test *test3=new Test();  //堆中分配  ，由管理者进行内存的分配和管理，用完必须delete()，否则可能造成内存泄漏
    test1.add();
    test2.add();             //"." 是结构体成员引用
    test3->add();            //"->"是指针引用
    delete(test3);
    system("pause"); 
}

第一种和第二种没什么区别，一个隐式调用，一个显式调用，两者都是在进程虚拟地址空间中的栈中分配内存。栈是系统数据结构，对于线程/进程是唯一的，它的分配和释放由操作系统决定，不需要由开发者来管理。在执行函数时，函数内局部变量的存储单元可以在栈上创建，函数执行完毕，系统会自动释放这些存储单元。

第三种使用了new，在堆中分配了内存，堆上的内存分配，亦称动态内存分配。程序在运行的期间用malloc申请的内存，这部分内存由程序员自己负责管理，其生存期由开发者决定：在何时分配，分配多少，并在何时用free来释放该内存。这是唯一可以由开发者参与管理的内存。使用的好坏直接决定系统的性能和稳定。注意：栈中内存的分配和管理由操作系统决定，而堆中内存的分配和管理由管理者决定。

我们需要的内存很少，你又能确定你到底需要多少内存时，用栈。当你需要在运行时才知道你到底需要多少内存时，请用堆。

下面是自己总结的一些关于new创建类对象特点：

new创建类对象需要指针接收，一处初始化，多处使用
new创建类对象使用完需delete销毁
new创建对象直接使用堆空间，而局部不用new定义类对象则使用栈空间
new对象指针用途广泛，比如作为函数返回值、函数参数等
频繁调用场合并不适合new，就像new申请和释放内存一样

参考：【C++】创建对象之new关键字_c++ new一个对象-CSDN博客

结构体

普通的结构体

如下代码所示，引用的时候直接使用变量名+“.”+元素名称。例如sqList.elem

typedef struct{
	elemtype* elem;
	int size;
	int length;
}sqList;

结构体指针

创建方法：

typedef struct A{
    int x;
    A* next;
}A;

引用该结构体时候，需要定义一个A类型的指针变量，该指针变量就是结构体指针。可以调用该结构体里的所有成员变量。例如

A* test
test -> x;//访问结构体中的x变量，也就是数据域
text - > next // 访问结构体中的指针变量，也就是指针域。

容器

概念

所谓容器，就是可以承载，包含元素的一个器件，它是STL六大组件之一，是容器、算法、迭代器中最重要也是最核心的一部分。

结构与分类

顺序性容器

概念

顺序性容器就是将一组具有相同类型的元素以严格的线性形式组织起来。

分类

容器	简介说明
vector	可变大小数组。相当于数组，可动态构建，支持随机访问，无头插和尾插，仅支持inset插入，除尾部外的元素删除比较麻烦。但使用最为广泛
deque	双端队列。支持头插、删，尾插、删，随机访问较vector容器来说慢,但对于首尾的数据操作比较方便
list	双向循环链表。使用起来很高效，对于任意位置的插入和删除都很快，在操作过后，以后指针、迭代器、引用都不会失效
forward_list	单向链表。只支持单向访问，在链表的任何位置进行插入/删除操作都非常快
array	固定数组。vector的底层即为array数组，它保存了一个以严格顺序排列的特定数量的元素

vector使用

头文件	#include
push_back()/insert()	存入数据，尾部插入
pop_back()	尾部删除
begin()	起始位置
end()	结束后+1
printvector()	打印容器元素
assign()	幅值操作
erase()	删除指定位置
clear（）	清空数组
capacity()	查询容量
size()	查询大小
empty()	查询容器是否为空
resize()	改变容器大小

使用场合

一般大多数的题目都可以使用vector容器，除非有特定需求使用其他容器更加合理方便；如果需要在一串数字的头尾进行操作，偏向deque，对于较中间的元素操作，不推荐；

对于中间的元素插入或删除，可采用forward_list（单向链表）或list（双向链表），不需要移动元素，只需改变相关结点的指针域即可；

关联式容器

概念

关联式容器每一个元素都有一个键值（key），对于二元关联容器，还拥有实值（value）容器中的元素顺序不能由程序员来决定，有set（集合）和map（映射）这两大类，它们均是以RB-Tree（red-black tree，红黑树）为底层架构。

分类

容器	简介说明
set/mutliset	集合/多重集合。对于set，在使用insert插入元素时，已插入过的元素不可重复插入，这正好符合了集合的互异性，在插入完成显示后，会默认按照升序进行排序，对于multiset，可插入多个重复的元素
map/mutlimap	映射/多重映射。二者均为二元关联容器（在构造时需要写两个参数类型，前者对key值，后者对应value值），因为有两个参数，因此在插入元素的时候需要配合对组pair进行插入，具体见深入详解

使用场合

如果只负责查找内容，具体到某个单位，使用场景比如对手机游戏的个人的计分的存储，可以使用set或mutliset。

如果需要同时放入容器的数据不止一个，并且是不同类型，比如一个为整型int,一个为string字符串型，就可以考虑使用map或mutlimap。

容器适配器

概念

容器适配器是一个封装了序列容器的一个类模板=，它在一般的序列容器的基础上提供了一些不同的功能。之所以称为容器适配器，是因为它是适配容器来提供其它不一样的功能。通过对应的容器和成员函数来实现我们需要的功能。

分类

容器	简介说明
stack	堆栈。其原理是先进后出（FILO），其底层容器可以是任何标准的容器适配器，默认为deque双端队列
queue	队列。其原理是先进先出（FIFO），只有队头和队尾可以被访问，故不可有遍历行为，默认也为deque双端队列
pirority_queue	优先队列。它的第一个元素总是它所包含的元素中优先级最高的，就像数据结构里的堆，会默认形成大堆，还可以使用仿函数来控制生成大根堆还是生成小根堆，若没定义，默认使用vector容器