iterator
/ container
/ algorithm
/ traits
,该有的都没有
对退化的字符串字面值使用range-based-for
问题
int main() {
const char str[] = "abcde";
for(auto c : str) { // ok
std::cout << c << ' ';
}
// ...
const auto ptr = str; // decay
for(auto c : ptr) { // ptr不能这么干
std::cout << c << ' ';
}
return 0;
}
如何解决
struct View {
const char *str;
View(const char *str): str(str) {}
struct Iterator: std::string::const_iterator {
using Base = std::string::const_iterator;
using Base::Base;
bool operator!=(const Iterator&) { return !!**this; }
};
Iterator begin() const { return Iterator(str); }
Iterator end() const { return {}; }
};
用例
int main() {
const char str[] = "abcde";
for(auto c : str) { // ok
std::cout << c << ' ';
}
// ...
const auto ptr = str;
for(auto c : View(ptr)) { // ok
std::cout << c << ' ';
}
return 0;
}
更多
同样的适配器套路可以用于支持一个反向迭代的range-based loop
stateful std::for_each
注意到
template<typename _InputIterator, typename _Function>
_Function
for_each(_InputIterator __first, _InputIterator __last, _Function __f)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
__glibcxx_requires_valid_range(__first, __last);
for (; __first != __last; ++__first)
__f(*__first);
return __f; // 这里
}
可以应用
struct Functor {
long sum{};
int count{};
void operator()(int v) { sum += v; count++; }
operator double() { return 1.0 * sum / count; }
};
int main() {
std::vector<int> nums {1, 2, 3, 4, 5, 6};
auto avg = std::for_each(nums.begin(), nums.end(), Functor{});
std::cout << avg << std::endl;
}
vector trick - 返回最后元素
示例
int main() {
std::vector<int> vec {1, 2, 3, 4};
std::cout << vec.end()[-1] << std::endl;
}
然而
其实可以直接vec.back()/ rbegin() / --end()
但是
如果是返回倒数第$N$个,这种写法非常直观(某种意义上,如要求1-based)
注:LLVM很喜欢用这个技巧
启发式合并
思路
void mergeSet(std::set<int> &a, std::set<int> &b) {
if(a.size() < b.size()) std::swap(a, b); // simple but useful
a.insert(b.begin(), b.end());
}
void nativeMergeSet(std::set<int> &a, std::set<int> &b) {
a.insert(b.begin(), b.end());
}
跑分
auto bench = [](size_t times, bool native = false) {
auto start = std::chrono::system_clock::now();
size_t used = 0;
std::set<int> large;
while(used < times) {
std::set<int> small;
int roll = std::min(::rand() % (times>>1), times - used);
bool useSmall = ::rand() & 1;
if(useSmall) std::swap(large, small);
while(roll--) small.insert(used++);
if(native) nativeMergeSet(large, small);
else mergeSet(large, small);
}
auto end = std::chrono::system_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "merge cost: " << duration.count() << "ms." << '\n'
<< "set size: " << large.size() << std::endl;
};
// gcc -O3
int main() {
int times = 1e7;
bench(times, true); // native method, 2528ms
bench(times, false); // 1373ms
}
泛型擦除 - lambda递归
提出问题:用lambda写个递归形式的斐波那契
int main() {
auto fib = [&fib](int n) { // 淦不能捕获自己
return n < 2 ? 1 : fib(n-1) + fib(n-2);
};
}
善用多态
int main() {
std::function<int(int)> fib = [&fib](int n) {
return n < 2 ? 1 : fib(n-1) + fib(n-2);
};
std::cout << fib(5) << std::endl;
FIXME
C++14可用到Y组合子的技巧,但是C++11似乎只能靠类似std::function
的做法了