可变参数

可变参数的笔记参考的这里。

所谓可变参数指的是函数的参数个数可变，参数类型不定的函数。为了编写能处理不同数量实参的函数，C++11提供了两种主要的方法：如果所有的实参类型相同，可以传递一个名为initializer_list的标准库类型；如果实参的类型不同，我们可以编写可变参数模板。另外，C++还有一种特殊的省略符形参，可以用它传递可变数量的实参，不过这种一般只用于与C函数交互的接口程序。

可变参数函数

initializer_list形参

如果函数的实参数量未知但是全部实参的类型都相同，我们可以使用initializer_list类型的形参（C++11新标准）。和vector一样，initializer_list也是一种模板类型。下面看看initializer_list提供的一些操作：

#include<initializer_list>  // 头文件
initializer_list<T> lst;    // 默认初始化，T类型元素的空列表
initializer_list<T> lst{a,b,c...}; // 初始化为初始值列表的副本
lst2(lst)     // 拷贝或赋值不会拷贝列表中的元素；拷贝后，
lst2 = lst    // 原始列表和副本共享元素
lst.size()    // 列表中的元素数量
lst.begin()   // 返回指向lst中首元素的指针
lst.end()     // 返回指向lst中尾元素下一位置的指针

下面给出一个例子，需要注意的是，含有initializer_list形参的函数也可以同时拥有其他形参。另外，如果想给initializer_list形参传递一个实参的序列，必须把序列放在一对花括号内：

string func(initializer_list<string> li)
{
	string str("");
	for(auto beg=li.begin(); beg!=li.end(); ++beg)
		str += *beg;
	return str;
}

int main()
{
	cout << func({"This"," ","is"," ","C++"}) << endl;
	return 0;
}

省略符形参

函数可以用省略符形参”…”表示不定参数部分，省略符形参只能出现在形参列表的最后一个位置，它的形式如下：

void foo(parm_list, ...);
// 典型例子
int printf(const char* format, ...)

省略符形参应该仅仅用于C和C++通用的类型，因为大多数类类型的对象在传递给省略符形参时都无法正确拷贝。下面是**< cstdarg >**头文件中的几个宏定义：

#include<cstdarg>  // C中是<stdarg.h>

// va_list是一种数据类型，args用于持有可变参数。
// 定义typedef char* va_list;
va_list args;

// 调用va_start并传入两个参数：第一个参数为va_list类型的变量
// 第二个参数为"..."前最后一个参数名
// 将args初始化为指向第一个参数（可变参数列表）
va_start(args, paramN);

// 检索参数，va_arg的第一个参数是va_list变量，第二个参数指定返回值的类型
// 每一次调用va_arg会获取当前的参数，并自动更新指向下一个可变参数。
va_arg(args,type);

// 释放va_list变量
va_end(args);

下面给出一个例子：

int add_nums(int count,...)
{
	int result = 0;
	
	va_list args;
	va_start(args, count);
	for(int i=0; i<count; ++i)
		result += va_arg(args, int);
	va_end(args);
	return result;
}

int main()
{
	cout << add_nums(4, 25, 25, 50, 50) << endl;
	return 0;
}

编译器是将参数压入栈中进行传递的。传递实参的时候，编译器会从实参列表中，按从右到左的顺序将参数入栈，对于add_nums(4, 25, 25, 50, 50)的调用，则入栈的顺序是 50, 50, 25, 25, 4 (注意没有可变参数与不可变参数之分)。由于栈的地址是从高到低的，所以在知道了第一个参数地址和参数的类型之后，就可以获取各个参数的地址。

可变参数模板

一个可变参数模板（variadic template）就是一个接受可变数目参数的模板函数或模板类。可变数目的参数被称为参数包（parameter packet）。存在两种参数包：模板参数包（表示零个或多个模板参数）和函数参数包（表示零个或多个函数参数）。

上述说到我们可以使用一个initializer_list来定义一个可接受可变数目实参的函数，但是所有实参必须具有相同的类型。当我们既不知道要处理的实参数目也不知道它们的类型时，我们就需要使用可变参数的函数模板了。我们用一个省略号来指出一个模板参数或函数参数表示一个包：在一个模板参数列表中，class...或typename...指出接下来的参数表示零个或多个类型的列表；一个类型名后面跟一个省略号表示零个或多个给定类型的非类型参数的列表。在函数参数列表中，如果一个参数的类型是一个模板参数包，则此参数也是一个函数参数包。

// Args是一个模板参数包；rest是一个函数参数包
template <typename T, typename...Args>
void foo(const T &t, const Args&...rest);

可变参数函数模板通常是递归的。第一步调用处理包中的第一个实参，然后用剩余的实参调用自身。为了终止递归，我们还需要定义一个非可变参数的函数模板：

// 用来终止递归并处理包中最后一个元素
template <typename T>
void print(const T &t)
{
	cout << t;
}

// 包中除了最后一个元素之外的其他元素都会调用这个版本的print
template <typename T, typename...Args>
void print(const T &t, const Args&...rest)
{
	cout << t << " ";     // 打印第一个实参
	print(rest...);       // 递归调用，打印其他实参
}

// 测试
int main()
{
	print("string1", 2, 3.14f, "string2", 42);
	cout << endl;
	return 0;
}

非可变参数版本的print负责终止递归并打印初始调用中的最后一个实参。对于最后一次递归调用print(42)，两个print版本都是可行的。但是，非可变参数模板比可变参数模板更特例化，因此编译器选择非可变参数版本。

矢量（Vector）容器

基本概念

  • 能够存放任意类型
  • 一个矢量的元素只能是同一个类型
  • 其大小是动态变化的
  • 是一个顺序序列（即可以用索引方式访问元素）
  • 可以理解为一个动态数组

构造函数

  • vector()：创建一个空的vector
  • vector(int nSize)：创建一个vector，元素个数为nSize
  • vector(int nSize, const t& t)：创建一个vector，元素个数为nSize，且值均为t
  • vector(const vector&)：复制一个vector创建新的vector构造函数
  • vector(begin, end)：复制[begin,end)区间内另一个数组的元素到vector中创建矢量

增加函数

  • void push_back(const T& x):矢量尾部增加一个元素X
  • iterator insert(iterator it,const T& x):矢量中迭代器指向元素前增加一个元素x
  • iterator insert(iterator it,int n,const T& x):矢量中迭代器指向元素前增加n个相同的元素x
  • iterator insert(iterator it,const_iterator first,const_iterator last):矢量中迭代器指向元素前插入另一个相同类型矢量的[first,last)间的数据

删除函数

  • iterator erase(iterator it):删除矢量中迭代器指向元素
  • iterator erase(iterator first,iterator last):删除矢量中[first,last)中元素
  • void pop_back():删除矢量中最后一个元素
  • void clear():清空矢量中所有元素

遍历函数

  • reference at(int pos):返回pos位置元素的引用
  • reference front():返回首元素的引用
  • reference back():返回尾元素的引用
  • iterator begin():返回矢量头指针，指向第一个元素
  • iterator end():返回矢量尾指针，指向矢量最后一个元素的下一个位置
  • reverse_iterator rbegin():反向迭代器，指向最后一个元素
  • reverse_iterator rend():反向迭代器，指向第一个元素之前的位置

判断函数

  • bool empty() const:判断矢量是否为空，若为空，则矢量中无元素

大小函数

  • int size() const:返回矢量中元素的个数
  • int capacity() const:返回当前矢量所能容纳的最大元素值
  • int max_size() const:返回最大可允许的vector元素数量值

其他函数

  • void swap(vector&):交换两个同类型矢量的数据
  • void assign(int n,const T& x):设置矢量中前n个元素的值为x
  • void assign(const_iterator first,const_iterator last):矢量中[first,last)中元素设置成当前矢量元素

示例

#include <iostream>
#include <vector>
#include <string>
#include <initializer_list>

using namespace std;

// 打印矢量
string printVector(vector<string> v){
  string s = "[";
  for(auto it=v.begin(); it != v.end(); ++it){
    s += *it;
    if(it+1 != v.end()){
      s += ", ";
    }
  }
  s += "]";
  return s;
}

// 打印所有矢量
void printAllVectors(initializer_list< vector<string> > vs){
  int i = 0;
  for(auto it = vs.begin(); it != vs.end(); ++it){
    cout << "V" << i << ":";
    cout << printVector(*it) << endl;
    ++i;
  }
}


int main (int argc, char *argv[])
{
  //========================================================
  // 创建矢量
  //========================================================
  // 创建时初始化矢量
  vector<string> v0 = {"apple", "orange", "banana"};
  // 创建一个空矢量
  vector<string> v1;
  // 创建一个元素个数为5的矢量
  vector<string> v2(5);
  // 创建一个元素个数为6，且所有元素初始值均为haha的矢量
  vector<string> v3(6, "haha");
  // 复制一个vector创建新矢量
  vector<string> v4(v3);
  // 从数组的一部分创建矢量
  string a[] = {"a1", "b2", "c3", "d4", "e5"};
  vector<string> v5(a+1, a+4);
  // 显示所有矢量的初始值
  cout << "矢量初始值为：" << endl;
  printAllVectors({v0, v1, v2, v3, v4, v5});

  //========================================================
  // 增加元素
  //========================================================
  // 在矢量末尾添加元素
  v0.push_back("grape");
  // 在矢量的某个位置之前插入一个元素
  v3.insert(v3.begin()+3, "fruit");
  // 在矢量的某个元素之前插入4个apple
  v2.insert(v2.begin(), 4, "apple");
  // 在矢量的某个元素之前插入多个元素（取自其他矢量）
  v4.insert(v4.begin()+2, v0.begin(), v0.begin()+2);
  // 显示增加操作后所有矢量的值
  cout << "增加操作后矢量值：" << endl;
  printAllVectors({v0, v1, v2, v3, v4, v5});

  //========================================================
  // 删除元素
  //========================================================
  // 删除矢量中迭代器指向元素
  v0.erase(v0.begin()+1);
  // 删除矢量中[first, last)中的元素
  v2.erase(v2.begin()+1, v2.begin()+3);
  // 删除矢量末尾的一个元素
  v3.pop_back();
  // 清空矢量中的所有元素
  v4.clear();
  // 显示删除操作后所有矢量的值
  cout << "删除操作后矢量值：" << endl;
  printAllVectors({v0, v1, v2, v3, v4, v5});

  //========================================================
  // 遍历vector
  //========================================================
  cout << "遍历操作显示矢量值：" << endl;
  // 返回pos位置元素的引用遍历
  cout << "v0:" << "[";
  for(int i=0; i<v0.size(); ++i){
    cout << v0.at(i);
    if(i+1 != v0.size()){
      cout << ", ";
    }
  }
  cout << "]" << endl;

  // foreach遍历
  cout << "v2:" << "[";
  for(auto var : v2)
  {
    cout << var << ", ";
  }
  cout << "]" << endl;

  // 正向迭代器遍历
  cout << "v3:" << "[";
  for(vector<string>::iterator it = v3.begin(); it != v3.end(); ++it){
    cout << *it;
    if(it+1 != v3.end()){
      cout << ", ";
    }
  }
  cout << "]" << endl;

  // 反向迭代器遍历
  cout << "v5:" << "[";
  for(vector<string>::reverse_iterator rit = v5.rbegin(); rit != v5.rend(); ++rit){
    cout << *rit;
    if(rit+1 != v5.rend()){
      cout << ", ";
    }
  }
  cout << "]" << endl;

  return 0;
}

哈希表

#include <unordered_map>                // 0. 包含库
#include <iostream>
#include <string>

using namespace std;

int main() {
    // 1. 声明哈希表
    unordered_map<int, string> hashtable;
    // 2. 通过(key, value)的方式添加哈希表数据
    hashtable.insert(make_pair(0, "苹果"));
    hashtable.insert(make_pair(2, "橘子"));
    // 3. 通过另一种方式添加哈希表键值对或更新值
    hashtable[1] = "芭蕉";
    hashtable[1] = "香蕉";
    // 4. 获取某个键的值
    cout << "键 1 的值为: " << hashtable[1] << endl;
    // 5. 删除某个键值对
    hashtable.erase(2);
    // 6. 在哈希表中查找键2是否存在
    if (hashtable.count(2) <= 0) {
        cout << "键 2 不存在哈希表中" << endl;
    }
    // 7. 获取哈希表的大小
    cout << "哈希表的大小为: " << hashtable.size() << endl; 
    // 8. 遍历哈希表(此处hashtable.begin()类型为unordered_map<int, string>::iterator迭代器)
    for (auto it = hashtable.begin(); it != hashtable.end(); ++it) {
        // it->first表示键，it->second表示值
        cout << "(" << it->first << "," << it->second << ") ";
    }
    cout << "为哈希表的数据." << endl;
    // 9. 用find方式在哈希表中查找键0是否存在,不存在会返回hashtable.end()
    auto it = hashtable.find(0);
    if(it != hashtable.end()){
        cout << "(" << it->first << "," << it->second << ") 存在于哈希表中！" << endl;
    }
    // 10. 清理哈希表的所有数据
    hashtable.clear();
    // 11. 确认哈希表是否为空
    if (hashtable.empty()) {
        cout << "哈希表已清空!" << endl;
    }
}

结构与链表

链表简介

  • 链表单个节点一般包含数据成员与指针成员
  • 链表一般采用结构体来构造
  • 尾节点的指针指向nullptr
  • 链表插入与删除的效率相对于vector和数组要更高

结构体的实现

#include <iostream>

using namespace std;

// 链表结构体定义
struct ListNode{
  int val; // 数据成员
  ListNode *next; // 指针成员
  ListNode(): val(0), next(nullptr){} // 无参数构造函数
  ListNode(int val): val(val), next(nullptr){} // 数据成员构造函数
  ListNode(int val, ListNode *next): val(val), next(next){} // 数据与指针构造函数
};

// 另一种链表结构体的构造函数定义
struct ListNode1{
  int val;
  ListNode1 *next;
  ListNode1(){
    val = 0;
    next = nullptr;
  }
  ListNode1(int val){
    val = val;
    next = nullptr;
  }
  ListNode1(int val, ListNode1 *next){
    val = val;
    next = next;
  }
};

int main (int argc, char *argv[])
{
  // 定义第一个链表节点
  ListNode *l1 = new ListNode(1);
  // 定义第二个链表节点
  ListNode *l2 = new ListNode(2);
  l1->next = l2;
  // 第一种遍历链表方式
  ListNode *ptr = l1;
  while(ptr != nullptr){
    cout << ptr->val << " " << endl; // 处理节点
    ptr = ptr->next; // 移动到下一个节点
  }
  delete(l1, l2);
  
  // 生成一个含十个节点的链表
  ListNode *l3 = new ListNode();
  ListNode *lptr = l3;
  for(int i=0; i<10; ++i){
    lptr->val = i;
    lptr->next = new ListNode(i+1);
    lptr = lptr->next;
  }

  // 第二种遍历链表的方式
  for(ListNode *lptr = l3; lptr != nullptr; lptr=lptr->next){
    cout << lptr->val << endl;
  }
  delete(l3);
  return 0;
}