STL踩坑防身技巧

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的做法了