《程序员面试宝典》学习记录5

voctor<noDefault> v2(10) 错误，必须要提供一个原始初始化器
vector<int>v1(100)       初始化size为100 避免数组动态增长时候不断分配内存
v1.reserve(100)          功能同上

c.back()            传回最后一个数据，不检查这个数据是否存在
c.front()           传回第一个数据
c.push_back(elem)   在尾部加入一个数据
c.pop_back()        删除最后一个数据
c.reserve()         保留适当的容量
c.at(idx)           返回索引idx所指向的数据，如果idx越界，抛出out of range

vector<string> svec;
cout << svec[0];    运行是错误，因为svec中没有元素
cout << svec.at(0); 抛出一个out_of_range异常

c.erase(pos)        删除pos位置的数据，传回下一个数据的位置
c.erase(beg,end)    删除[beg,end)区间的数据，传回下一个数据的元素
c.erase(remove(c.begin(), c.end(), 6), c.end())  删除容器中所有的6

补充说明：STL中remove()只是把待删除移动到vector的末尾，并不是删除，要正在删除还需要结合erase，但是对于vector，任何插入删除操作都会引起迭代器失效，所有连续删除的时候需要注意。需要注意删除操作，删除之后传回下一个数据的位置，如果继续iter++的话，会导致错过某个数。
考点5：浅拷贝和深拷贝
C++默认的拷贝构造函数是浅拷贝
浅拷贝：对象的数据成员之间的简单赋值，如你设计了一个没有类而没有提供它的复制构造函数，当用该类的一个对象去给令一个对象赋值时所执行的过程就是浅拷贝。

class A {
public: 
    A(int  _data) : data(_data){} 
    A(){}
private: 
    int data; 
};
int main()
{ 
  A a(5)；
  A b = a; // 仅仅是数据成员之间的赋值 
}

浅拷贝，执行完之后b.data = 5
如果对象中没有其他的资源（如：堆，文件，系统资源等），则深拷贝和浅拷贝没有什么区别，但当对象中有这些资源时，例子：

class A { 
public: 
    A(int  _size) : size(_size)
    {
        data = new int[size];
    } // 假如其中有一段动态分配的内存 
    A(){}; 
    ~A(){delete [] data;} // 析构时释放资源private: 
     int* data;
     int size; 
}
int main()
{ 
      A a(5);
      A b = a; // 注意这一句
 }

运行会产生崩溃的现象
这里b的指针data和a的指针指向了堆上的同一块内存，a和b析构时，b先把其data指向的动态分配的内存释放了一次，而后a析构时又将这块已经被释放过的内存再释放一次。
对同一块动态内存执行2次以上释放的结果是未定义的，所以这将导致内存泄露或程序崩溃。
所以必须采用深拷贝来解决这个问题：
深拷贝：当拷贝对象中有对其他资源（如堆、文件、系统等）的引用时候，对象的另开辟一块新的资源，而不再对拷贝对象中有对其他资源的引用的的指针或者引用单纯的赋值。

class A { 
public: A(int _size) : size(_size)
{
    data = new int[size];
} // 假如其中有一段动态分配的内存
 A(){};
 A(const A& _A) : size(_A.size)
{
    data = new int[size];
} // 深拷贝
 ~A()
{
delete [] data;
} // 析构时释放资源private: 
    int* data; 
    nt size; 
}
int main() 
{ 
    A a(5);
    A  b = a; // 这次就没问题了 
}

9.2 泛型编程

考点1：如何理解泛型编程？
泛型编程是一种基于发现高效算法的最抽象表示的编程方法，主要作用是在函数的参数调用中将具体的数据类型隐去，能够给通过模板（template）的方式，只是通过泛型指针来对数据进行调用操作，进而达到增加函数重复利用，以及代码简洁的目的。
泛型编程主要特点：
1）泛型编程集中的应用体现STL库的调用，STL主要由容器、算法、迭代器三部分组成，迭代器iterator是连接不同容器和算法之间的桥梁

2）泛型算法主要的操作对象是不同的容器，但一般都是通过传址方式调用，传入参数的前两个一般都是first iterator和last iterator；find(),sort(),replace(),merge()等都是泛型算法。
3）采用泛型算法和采用传统面向过程风格的区别主要是一个函数可以使用的弹性更大，解决同样的问题，采用泛型算法代码会更加简洁
考点2：如何把普通的函数改成泛型函数的问题？
普通的函数：

const int *find1(const int* array, int n, int x)
{
    const int *p = array;
    for(int i = 0; i < n; i++)
    {
        if(*p == x)
        {
            return p;
        }
        ++p;
    }
    return 0;
}

template<typename T>
const T *find1(T* array, T n, T x)
{
    const T *p = array;
    for(int i = 0; i < n; i++)
    {
        if(*p == x)
        {
            return p;
        }
        ++p;
    }
    return 0;
}

方法：
对于容器的变量需要将原来的参数改为泛型指针传递；
对于数据的变量需要将原参数模板化，采用template定义；
对于函数指针，则需要通过定义函数对象来传递原指针；
对于泛型函数内部的操作，则必须避免出现底层的数据，用指针和函数对象来代替。

9.3 模板

考点1：认识模板
模板是C++支持参数化多态的工具，使用模板可以使用户为类或者函数声明一种一般模式，使得类中的某些数据成员或者成员函数的参数、返回值取得任意类型。
模板通常有两种形式：函数模板、类模板
函数模板仅参数类型不同的函数；类模板针对仅数据成员和成员函数类型不同的类。
模板的声明或定义只能在全局，命名空间或类范围内进行。即不能在局部范围，函数内进行，比如不能在main函数中声明或定义一个模板。
考点2：模板的形参
模板的形参表示的是一个未知的类型。
模板的形参：类型形参、非类型形参和模板形参
类型形参：T 前面一般是class或者typename
非类型形参：在模板定义的内部是常量值，也就是说非类型形参在模板的内部是常量；非类型模板的形参只能是整型，指针，引用；调用非类型模板形参必须是一个常量表达式，任何局部对象，局部变量，局部对象的地址都不是一个常量表达式，都不能用作非类型模板形参的实参。但是全局变量的地址或引用，全局对象的地址或引用const类型变量是常量表达式，可以用非类型模板形参的实参；非类型模板形参的形参和实参间允许转换。
考点3：用模板把指针作为参数传递到其他函数

#include<stdio.h>
//比较函数
int jug(int x, int y)
{
    if(x>=0)
    {
        return 0;
    }
    else if(y==0)
    {
        return x;
    }
    else
        return x/y;
}
//求和函数
int sub(int x, int y)
{
    return(x+y);
}
//求差函数
int minus(int x, int y)
{
    return(x-y);
}
//函数指针
void test(int (*p)(int,int), int a, int b)
{
    int Int1;
    Int1 = (*p)(a,b);
    printf("a=%d,a=%d %d
",a,b,Int1);
}
int main()
{
    int a=1,b=2,c=3,d=4,e=-5;
    test(sub,a,b); //求和
    test(minus,c,d); //求差

    test(jug,e,b);//判断
    return 0;
}

考点4：利用枚举法
1~9的9个数字，每个数字只能出现一次，要求这样一个9位的整数；其第一位能被1整除，前两位能被2整除，前三位能被3整除……依次类推，前9位能被9整除
代码：

#include<iostream>using namespace std;
bool use[10];//标记是否使用过void dfs(int k, long long val)
{
    if(k==9)//9位则输出
    {
        cout << val << endl;
        return;
    }
    for(int i=1;i<=9;++i)
    {
        if(!used[i])
        {
            used[i]=1;
            long long temp = val*10+i;
            if(temp%(i+1)==0)
                dfs(i+1,tmp);
            used[i]=0;
        }
    }
}
int main()
{
    dfs(0,0);
    return 0;
}

《程序员面试宝典》学习记录5