1. 入门并实践STL——vector篇

此笔记整理自《算法笔记》电子版下载 密码：yhpimb
其他资料：STL教程：C++ STL快速入门（非常详细）

1. vector

1. How to use?

#include<vector>
using namespace std; // 这样就可以在代码中使用vector了

2. vector的定义

• 单独定义一个vector:
  vector<typename> name; 相当于定义一个一维数组name[SIZE]， 不过其长度可以根据需要进行变化。
  typename可以是int, double, char, 结构体, vector, set, queue...
  注意：如果typename为stl，则在>>之间要加空格vector<vector<int> > name;否则会报错。

• 定义vector数组
  两个维度都可变长：vector<vector<int> > name;
  只有一个维度可变长：vector<int> arrayName[100]

3. vector容器内元素的访问

   1. 下标访问：name[index] 如 name[0], 访问范围为0~size-1
   2. 迭代器访问:
      • 定义迭代器（一种类似指针的东西）
        vector<typename>::iterator it; typename是定义vector时填写的类型。
      • 使用迭代器

      vector<int> vi;
      // init
      for(int i = 0; i < 5; i++) {
          vi.push_back(i);
      }
      
      vector<int>::iterator it = vi.begin();
      for(int i = 0; i < 5; i++) {
          printf("%d", *(it+1)); // 输出vi[i]
      }
      

      • 使用迭代器+自增

      // vector的迭代器不支持it<vi.end()的写法，因此循环条件只能使用下方的方式
      for(vector<int>::iterator it; it != vi.end(); it++) {
           printf("%d", *it); 
      }
      

      从这里看出vi[i]和*(vi.begin() + i)是等价的
      • 特殊函数
        • vi[i].begin(): 获取首元素的地址
        • vi[i].end(): 获取尾元素地址的下一个地址，end()作为迭代器末尾标志，不存储任何元素。（美国人的思维比较习惯左闭右开）
        • 此外迭代器还可以it++, ++it
      • 注意：只有在vector和string中，才允许使用vi.begin()+1这种迭代器加上整数的写法

4. vector常用函数

   1. push_back()
      在vector后面添加一个元素，时间复杂度为O(1).

   #include<vector>
   using namespace std;
   
   int main() {
       vector<int> vi;
   
       for(int i = 0; i < 5; i++) {
           vi.push_back(i);
       }
       for(int j = 0; j < vi.size(); j++) {
           printf("%d ", vi[j]);
       }
       system("pause");
       return 0;
   }
   

   输出结果：1 2 3

   2. pop_back()
      删除尾元素，O(1)
   3. size()
      返回类型是unsigned，获得vector中的元素个数，O(1)
   4. clear()
      清楚vector中所有的元素，O(n)
   5. insert()
insert(it, x)用来向vector的任意迭代器it处插入一个元素，O(n)
      vi.insert(vi.begin()+1, -1); // -1将插入vi[1]的位置
   6. erase()
      • 删除单个元素: vi.erase(it.begin() + 1) // 删除vi[1]
      • 删除一个区间内的所有元素:
        erase(first, last): 删除[first, last)内的所有元素
        vi.erase(it.begin() + 1, it.begin() + 3) // 删除vi[1], vi[2]
      • 复杂度都为O(n)

5. vector的常见用途

   1. 存储数据
   2. 用邻接表存储图

练题网址-vector

• 注意点：

  1. 数组长度使用变量，对大多数编译器是非法的
  2. 如何使用scanf读取string
  3. 不定长的二维vector，如何进行vi[i].push_back操作前，需要进行第一维的初始化vi.resize(size);
  4. vector<vector <int> > ivec(m ,vector<int>(n)); //m*n的二维vector
  5. 多维数组的初始化

• A题优解

  • 思路：
    将姓名不以string类型存储,将姓名以每个字母的ASCII码的形式计算转换为int类型（ t = (((name[0] - 'A') * 26 + (name[1] - 'A')) * 26 + name[2] - 'A') * 26 + name[3] - '0';
    ）.

  • 改进后的代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int getkey(char *name) {
    int key = 0;
    for(int i = 0; i < 3; i++)
        key= 26 * key+ (name[i] - 'A');
    key= key * 10 + (name[3] - '0');
    return key;
}
int main() {
    
    vector<vector<int> > students(182800); 
    int N, K;
    scanf("%d%d", &N, &K);

    // For each course, round up all students who sign up this course. 
    for(int h = 1; h <= K; h++) {
        int i, Ni; // i means the course id, Ni means how many students choose this course
        scanf("%d%d", &i,&Ni);
        char name[5];
        for(int j = 0; j < Ni; j++) {
            scanf("%s", name);
            //printf("[%s]", name);
            students[getkey(name)].push_back(i);
        }
    }

    for(int a = 0; a < N; a++) {
        char name[5];
        scanf("%s", name);
        int name_id = getkey(name);
        int nr = students[name_id].size();
        printf("%s %d ", name, nr);
        // sort
        sort(students[name_id].begin(), students[name_id].end());
        for(vector<int>::iterator it = students[name_id].begin(); it != students[name_id].end(); it++) {
            if(it == students[name_id].end()) {
                        printf("%d", *it);  
                    }
                else {
                    printf("%d ", *it);
                }
        }
        
        printf("\n");
        
    }
    return 0;
}