TopCoder-Power Up C++ with the standard Template Library

Posted on |

Top coder/ Power up C++ with the standard Template Library

vector 基本操作

  1. 对于STL中的容器，判断是否为空的时候，最好使用empty函数，而不是通过size来进行，这是因为size操作并不总是O(1)的操作

  2. Vector resize之后再使用push_back，开始的位置是resize的最后的位置，而不是包含的元素位置。比如vector有20个元素，之后resize到25,再push_back的时候会从26开始，而不是21

  3. 因为vector的复制操作很占空间。因此在作为参数传入的时候，尽量使用引用

    1
    2
    void func(const vector<int>& v)
    void func(vector<int>& v)

    ​

  4. 对于迭代器，最好使用!=来比较而不是<，因为在某些类型里面，比较前后关系不高效

  5. algorithms中有min_element 和 max_element俩个函数

  6. sort函数如何descending排序呢？（默认是ascending）

    1. 这里有比较多的方法，一种是使用greater()， 默认是less()
    2. 还有一种是sort(v.rbegin(), v.rend())，这个比较巧妙

  7. c++ typeof关键字，个人感觉现在支持C++ 11之后可以完美使用auto代替

  8. vector中的insert和erase都有单个元素版本和interval 版本

String

string.substr(start, end)

这里需要注意的是unsigned(0)-1 可能产生的问题

Set

基于RB-tree实现，可以实现在log(N)的时间内完成add, remove, check

check使用函数find()函数。这里的find不是全局的find,全局的find函数时间复杂度是O(N)，这里使用check的memeber func,时间复杂度是log(N)。 set.find()

当然check也可以使用memeber func count， set.count()判断是否为0，同样时间复杂度为log(N)

还有一个重要的点在于set中的元素(可排序的comparable)都是排序的。所以一个巧妙的应用是，将vector中的元素去重，并且排序。那么可以这么做：

1
2
3
vector<int> v1;
set<int> s(v1.begin(), v1.end());
vector<int> v2(s.begin(), s.end());

Map

map与set都是基于RB-tree来实现的，因此唯一的区别就是map中存储的是pair

还有一点map定义了[]的操作。但是[]与member func find()的区别在于：

find不会改变map的元素，[]当没有这个key时，会创建一个元素。

为什么尽量不要改变Map和set的key值，原因在于，map和set都是由rb-tree实现的，内部会一直保持一个ascending的order, 如果不停改变内部key值（循环里不停使用map[]），一来对效率是一个影响，二来许多依据顺序的member func的行为会异常。

algorithm

比较常用的函数有min, max, swap 这些都是作用与俩个元素上

find(start,end, ele), count(start,end, ele), 时间复杂度是O(N)，所以set, map不要使用std::find, std::count而是应该使用set::find(), set::count()

next_permutation(start, end) prev_permutation(start,end). 使用这个函数之前，需要确保的是容器已经排好序，不然会丢失某些组合。

sstream

这个库在string processing/input/output上很方便

包括istringstream, ostringstream

1
2
3
4
5
6
7
8
9
10
11
void f(const string& s){
  // Construct an object to parse strings
  istringstream is(s);
  vector<int> v;
  
  // Read int while possible and add it to the vector
  int tmp;
  while(is >> tmp){
    v.push_back(tmp);
  }
}

这段代码从一个string中parse出来所有的int，并且将所有的数字都读入vector中，这比起自己逐个字符来处理int要方便快捷得多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string f(const vector<int>& v){
  // Construct an object to do formatted output
  ostringstream os;
  
  // Copy all eles from vector to string stream as text
  tr(v, it){ // This is a macro to traverse a container
    os << ' ' << *it;
  }
  
  // Get string from string stream
  string s = os.str();
  
  if(!s.empty()){
    s = s.substr(1);
  }
  return s;
}

Creating Vector from Map

1
2
map<string,int> M;
vector<pair<string,int> > v(M.begin(), M.end());

这样v里面的元素是排序的，并且是map的一份copy

Copying data between containers

1
copy(from_begin, from_end, to_begin);
1
2
3
4
vector<int> v1, v2;
// Now copy v2 to the end of v1
v1.resize(v1.size() + v2.size());
copy(v2.begin(), v2.end(), v1.end()-v2.size());

copy数据中还经常有的一个操作就是如何从vector向set copy，这里有一个东西叫inserter(在iterator库里)

1
2
3
4
5
6
7
vector<int> v;
set<int> s;
copy(v.begin(), v.end(), inserter(s));
// Last sentence equals to 
// tr(v, it){
//  s.insert(*it);
// }

可以使用back_inserter向vector插入元素，使用front_inserter向deque插入元素。copy的前俩个参数换成rbegin, rend之后可以逆向copy

Merging lists

一个常用的操作是对俩个有序的链表。

所以STL提供了对集合的交集，并集，差集，对称差集

set_union(), set_intersection(), set_difference(), set_symmetric_difference()

使用这四个函数需要一个前提条件，就是有序。 意味着使用之前必须要排序。

以一个为例

1
end_result = set_intersectiion(begin1,end1, begin2, end2, begin_result)

最后一个参数是要存储的容器的启始位置，还需要注意一个点就是这个函数的返回值，因为在执行intersection操作之前是不知道长度的，因此这个函数返回最后结果的最后一个位置。

1
2
3
4
5
6
vector<int> v1;
vector<int> v2;
// ... //
vector<int> tmp(max(v1.size(), v2.size()));
vector<int> res = vector<int>(tmp.begin(), set_intersection(v1.begin(), v1.end(), v2.begin(),v2.end(),tmp.begin());

这里最后一行直接利用了函数的返回值是end iterator，所以直接新建了一个包含结果的vector.

Computing algorithm

这里介绍俩个操作，一个accumulate,一个inner_product

1
int sum = accumulate(v.begin(),v.end(), 0);

最后一个参数是累加的初值。

默认是累加，也可以做累乘

1
double product = accumulate(v.begin(), v.end(), double(1), multiplies<double>());

这里使用functional库里面的multiplies来完成

1
int r = inner_product(v1.begin(), v1.end(), v2.begin(), 0);

这个操作将v1 v2逐个元素相乘，最后再相加。最后的参数是相加的初值。

然后再介绍一个跟accumulate类似的操作，是partial_sum可以实现逐次输出相加和(逐次相乘),具体可以查看docs,利用这个函数可以实现！操作。

Nontrivial sorting

一种是重载运算符<，这样就不需要给sort函数第三个参数。或者就是重载运算符(),这样可以给sort第三个参数。

一个主意点：当重载运算符<，一定要保证对相等值返回值是false