前几天，在进行C++机试的时候遇到一些小问题和小技巧，在这里记录一下。
getline()和cin>>
ACM模式的机试需要自己从标准输入stdin读入，从标准输出stdout输出结果。在涉及到字符串读入的时候，遇到了cin>>和getline()交替的情况，但是没有符合预期的输入输出，代码如下：
#include <iostream>
int main()
{
char temp;
string input;
std::cin >> temp;
std::getline(cin, input);
return 0;
}当输入字符然后回车输入另一个字符串后，input并没有拿到对应的第二次输入的字符串。原因在于cin>>并不会处理white-space和换行符，当读完第一个字符后，第一行的换行符被留在cin里，第二次getline()就把它读了，没有读到想要的。
一个解决方法是，显式处理掉cin>>留下来的垃圾。
#include <iostream>
int main()
{
char temp;
string input;
std::cin >> temp;
std::getline(cin>>std::ws, input);
return 0;
}这样getline()就能读到想要的字符串了。
set的使用
在C++标准库STL里，提供了vector、set、map三种线性数据结构。我个人平时用set和map比较少，但是这两个在有些情况下能够大大节省时间。
std::set（std::multiset）的底层实现是红黑树，key值有序但是不能修改，查询和增删的复杂度都是O(logn)。在初始化的时候可以指定排序的函数（std::set::key_comp）。std::unordered_set的底层实现是哈希表，key值也不能修改，查询和增删的复杂度都是O(1)。
std::map（std::multimap）的底层实现也是红黑树，只不过相对于set而言，这里是key-value键值对作为存储最小元素。value值可以修改。std::unordered_map的底层实现也是哈希表，查询和增删的复杂度都是O(1)。
std::lower_bound方法可以用来查找set中对应target值第一个key_comp(iter, target)返回false的索引。key_comp(v1, v2)定义为，当v1应该排在v2前面时候，返回true，否则返回false。
相对应的std::upper_bound方法则是找到第一个key_comp(target, iter)返回true的索引。