embrace POD type util they die

type_traits

C++03的POD type，在C++11后由三个type_traits替代，standard layout, trivial, trivial copyable。 standard layout关注数据成员布局，而trivial关注行为。 我们首先看standard layout,

Read More

what you can learn from being too cute

idiom

daisy在其pure virtual cpp的演讲中讲解了一段非常有趣的代码

auto impl(std::string_view v = "") {
  static std::string stored;
  static int _ = (stored = v, []{ throw 0; }(), 0);
  __builtin_unreachable();  // since _ initializer throws
  return []{ return stored; };  // spooky access
}
void set(auto value) {
  try { impl(value); } catch (int) {}
}
auto get = decltype(impl()){};
int main() {
  set("hello ");
  std::cout << get();
  set("world!\n");
  std::cout << get();
}
Read More

如何使用kdiff3处理merge时的冲突

kdiff3 git

kdiff3是天下最好用的比较和merge工具，支持linux windows和mac。下文我们将通过例子介绍如何使用kdiff3 来处理git merge时的冲突。 我们以工程https://github.com/jiayuehua/kdiff3-demo 为例说明如何使用kdiff3解决冲突 开始时master中的kdiff3-demo.cpp内容如下，

Read More

Argument Dependent Lookup puzzle

adl

adl是指函数通过其参数所在的名字空间来寻找，对于模板函数，其行为和普通函数略有不同。 比如如下代码 int h;

template<class i>
void g();

namespace N {
  struct A {};
  template<int i> int f(A);
  template<int i> int g(A);
  template<class T> int h(T);
}

int main(){
// OK in C++20: lookup of `f` finds nothing, `f` treated as a template name
// fail in C++17: lookup of `f` finds nothing, `f` is NOT treated as a template name
auto a = f< 0>(N::A{});
// OK : lookup of `g` finds a function, `g` treated as a template name

auto b = g<0>(N::A{});
// error: `h` is a variable, not a template function
//auto c = h<N::A>(N::A{});
// OK, `N::h` is qualified-id
auto d = N::h<N::A>(N::A{});

N::f是一个函数模板，在C++17中，main函数中f<0>(N::A{})将失败，这是因为在C++17中，一个非限定标识f要被解析为函数模板，必须在当前空间或者全局空间能找到一个函数模板f；否则对于f< 0 >(N::A{})，这里的<解析为小于号，而>解析为大于号，整条语句解析为表达式而不是函数调用，因为找不到f的定义，所以报错。 相对的g因为在全局名字空间中有g的模板，所以g被解析为模板，所以g<0>(N::A{})可以正确的使用ADL找到名字空间N中的函数模板N::g。

在C++20中，只要当前或者全局名字空间没有定义同名的非函数及非函数模板的标识，那么便可将类似f<0>()等中的f解析为模板。因此在C++20中,f< 0>(N::A{} )， f将解析为函数模板，通过ADL调用N::f。 对于h，因为全局定义h为int变量，所以h<N::A>(N::A{})中h解析为变量而不是函数模板，在c++20中也会报错。

adl godbolt

Read More

Don’t design function that return rvalue reference

rvalue

设计函数和lambda时，尽量不要返回右值引用。这是因为1 可能返回dangling reference，2可能导致self move。返回dangling reference的情况大家比较熟悉，这里重点讨论self move。 一个对象self move前后，并不能保证该对象的状态不变。详细论述参看eric niebler的post-conditions on self move。比如如下代码，在clang上将输出空行:

std::string sb("BBBBBBBBBBBBBBBBBBBB");
sb=std::move(sb);
std::cout<<sb<<std::endl

我们想实现一个高效的拼接字符串的lambda，实现如下

#include <iostream>
#include <string>
#include <utility>
int main()
{
auto concat=
[](std::string&& l,const std::string &r)->std::string&&
{
     l+=r;
     return std::move(l);
};
std::string sa("AAAAAAAAAAAAAAAAAAAA");
std::string sb("BBBBBBBBBBBBBBBBBBBB");
sa=concat(std::move(sa),sb);
std::cout<<sa<<std::endl;
}

这里concat拼接后再赋值回原来的sa，因为返回lambda参数的右值引用，还是存在self move的风险，上述代码也一样输出空行。 你或许会说只要小心使用concat不self move就没有类似问题。可是lambda常用于回调，这导致即便你的代码中没有self move，可是库调用你的返回右值引用的lambda可能会发生self move。例如我们想拼接一组string

#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <numeric>
int main()
{
auto concat=
[](std::string&& l,const std::string &r)->std::string&&
{
     l+=r;
     return std::move(l);
};
std::string sa("AAAAAAAAAAAAAAAAAAAA");
std::vector<std::string>v(10,sa);
auto r=std::accumulate(v.begin(),v.end(),std::string{},concat);
std::cout<<r<<std::endl;
}

上述代码也会输出空行。 如何解决该问题呢，将lambda改写为返回value。如concat改写为

auto concat=
[](std::string&& l,const std::string &r)->std::string
{
     l+=r;
     return std::move(l);
};

便可避免self move的问题，程序将正确输出结果，不再是空行。

Read More

Do Runtime polymorphism correctly

polymorphism

C++的运行时多态历史上使用继承和虚函数的方法，可是继承有很多缺点，比如基类和派生类紧密耦合，基类的成员变量和成员函数都介入到了派生类。sean parent在其better code系列演讲中对继承做了强烈批判。louis的dyno库使用boost hana为基础，并使用type erase技术对运行时多态做了非常杰出的改进。这里我们介绍google 工程师john bandela 的另外一个方案metaprogrammed_polymorphism，使用type erase和函数重载技术，不过非常小巧，不到270行。

Read More

value wrapper and SFINAE failure

sfinae

C++17中的value wrapper 如optional 和variant给我们带来很大便利。假定我们要实现一个自己的value wrapper，代码如下:


#include <iostream>
#include <fmt/format.h>
template<class T>
struct wrapper{
    T t;
    template<class F>
    auto pass_to(F f)const->decltype(f(t))
    {
      fmt::print("pass_to const\n");
      return  f(t);
    }
    template<class F>
    auto pass_to(F f)->decltype(f(t))
    {
      fmt::print("pass_to  not const\n");
      return f(t);
    }
};
struct Foo{
    void do_something(){};
};
int main()
{
    wrapper<Foo> f;//[1]
    f.pass_to([](auto &&x){x.do_something(); }); //[2]
}

这里wrapper是我们的value wrapper。[2]处的f.pass_to将回调lambda，lambda的参数为wrapper<Foo>的唯一成员变量t。然而上述代码有个bug，你能看出来吗？

bug是pass_to的sfinae将产生hard error。如gcc 的error output:

<source>: In instantiation of 'main()::<lambda(auto:19&&)> [with auto:19 = const Foo&]':
<source>:7:39:   required by substitution of 'template<class F> decltype (f(((const wrapper<Foo>*)this)->wrapper<Foo>::t)) wrapper<Foo>::pass_to(F) const [with F = main()::<lambda(auto:19&&)>]'
<source>:25:14:   required from here
<source>:25:42: error: passing 'const Foo' as 'this' argument discards qualifiers [-fpermissive]
   25 |     f.pass_to([](auto &&x){x.do_something(); });
      |                            ~~~~~~~~~~~~~~^~
<source>:20:10: note:   in call to 'void Foo::do_something()'
   20 |     void do_something(){};
      |          ^~~~~~~~~~~~

两个pass_to都有->decltype(f(t))的sfinae，因此当我们传递lambda时，需要先进行sfinae决议，然而在sfinae的时候需要知道f(t)的返回类型，对于没有尾置返回的lambda，编译器必须解析lambda的全部代码决定返回类型而不能只解析lambda的签名。当如下const pass_to 成员函数做sfinae时，t是常成员变量，x是t左值引用，也是常量，而do_something()函数并不是常成员函数，因此Sfinae 时x.do_something()产出hard error。

...
 template<class F>
    auto pass_to(F f)const->decltype(f(t))
    {
      fmt::print("pass_to const\n");
      return  f(t);
    }
...

有啥办法解决对pass_to函数sfinae时产生hard eror的问题吗？在c++20以前是没有办法的，C++23引入deduce this的新语言特性可完美解决该问题。

例子代码选自cppcon上sy brand的How to write a value wrapper演讲。

Read More

variadic template and typelist mutual conversion

metaprogramming

C++11引入了variadic template，现在模板库都使用新的variadic template来实现模板元编程，可是C++03使用typelist，旧有的模板元库的算法难道都要舍弃了，另起炉灶吗？旧有的算法有其价值，最好的方法是能将typelist和variadic template相互转换，这样我们就可以应用旧有的算法于variadic template了。 如何转换呢？我们这里使用boost mp11库实现。

Read More

A better ostream_iterator

iterator

ostream_iterator 可方便的用于算法。但有个缺陷，使用ostream_iterator必须指定要输出类型的type，如ostream_iterator<int>。正如各种标准库的谓词可以不指定模板参数，ostream_iterator的设计也可改为不再需要指定模板参数，而将输出操作也就是复制函数改为模板成员函数

#include <iterator>
#include <iosfwd>
//now don't need to specify output type, all template parameter has default type.
template <class charT=char, class traits=std::char_traits<charT> >
  class OstreamIter :
    public std::iterator<std::output_iterator_tag, void, std::ptrdiff_t, void, void>
{
  std::basic_ostream<charT,traits>* out_stream;
  const charT* delim;

public:
  typedef charT char_type;
  typedef traits traits_type;
  typedef std::basic_ostream<charT,traits> ostream_type;
  OstreamIter(ostream_type& s) : out_stream(&s), delim(0) {}
  OstreamIter(ostream_type& s, const charT* delimiter)
    : out_stream(&s), delim(delimiter) { }
  OstreamIter(const OstreamIter<charT,traits>& x)
    : out_stream(x.out_stream), delim(x.delim) {}
  ~OstreamIter() {}
  OstreamIter() =default;
  //now is template function
  template< class T >
  OstreamIter<charT,traits>& operator= (const T& value) {
    *out_stream << value;
    if (delim!=0) *out_stream << delim;
    return *this;
  }

  OstreamIter<charT,traits>& operator*() { return *this; }
  OstreamIter<charT,traits>& operator++() { return *this; }
  OstreamIter<charT,traits>& operator++(int) { return *this; }
};

使用ctad，现在我们的OstreamIter的对象初始化时不再需要指定OstreamIter模板参数了。

#include <iostream>
#include <vector>
#include <algorithm>
#include <range/v3/all.hpp>
int main()
{
  std::vector v{0,1,2,3,4};
  //std::ostream_iterator<int> oit(std::cout,",");
  OstreamIter o(std::cout,",");
  ranges::copy(v,o);
  std::cout<<"\n";
  std::copy(v.begin(),v.end(),o);
  std::cout<<"\n";
  ranges::copy(v,oit);
  std::cout<<"\n";
}

godbold

Read More

stl排列组合算法

algorithm

标准库的排列组合算法现在只支持next_permutation和prev_permutation。排列组合有着极为重要的应用，howard hinnart开发了15个泛型算法，可以表示日常排列组合的大多数应用。 我们挑选其中三个做说明。

template <class BidirIter, class Function>
Function
for_each_permutation(BidirIter first,
                     BidirIter mid,
                     BidirIter last,
                     Function f);

计算从distance(first,last)个元素中挑选distance(first,mid)个元素的所有排列，对每一个排列回调f函数。 f的例子

auto f = []<typename BidirIter >(BidirIter b, BidirIter e){
    std::for_each(b,e,[](auto e){std::cout<<e<<',';});
    std::cout<<'\n';
}

如果回调以上f，将打印挑选出来的每个排列的各个元素。

template <class UInt>
UInt
count_each_combination(UInt d1, UInt d2);

计算从d1+d2的元素中挑选出d1个元素的所有组合的数量，如 count_each_combination(2,1) ==3。

template <class BidirIter>
std::uintmax_t
count_each_circular_permutation(BidirIter first,
                                BidirIter mid,
                                BidirIter last);

计算从distance(first,last)个元素中挑选distance(first,mid)个元素的循环排列的数量。 如

std::vector<int> v{1,2,3};
auto n = count_each_circular_permutation(v.begin(),v.end(),v.end());//n==2

这里只有两种。所有排列都可以由{1,2,3}, {1,3,2}这两种循环后表示出来，而这两种不能相互循环表示。

代码和benchmark可以从howard的Combinations and Permutations文章中获得。

Read More

查找字符串最长的不包含重复字符的子串

algorithm

给定一个字符串，查找最长的不包含重复字符的子串

用法例子：
./findSubStr asfdsadfkassadsf
sadfk

#include <vector>
#include <iostream>
#include <iterator>
#include <string_view>
auto notdupcharSubString(std::string_view s)
{
  const char*      p = s.data();
  std::vector<int> char2pos(256, -1);
  int              b   = 0;
  int              len = 0;
  std::pair        sub{0, 0};

  int i = 0;
  for (; i < s.size(); ++i) {
    if (char2pos[*(p + i)] != -1) {
      int sublen = i - b;
      if (sublen > len) {
        len = sublen;
        sub = {b, i};
      }
      for (; b <= char2pos[*(p + i)]; ++b) {
         char2pos[*(p + b)] = -1;
      }
    }
    char2pos[*(p + i)] = i;
  }
  int sublen = i - b;
  if (sublen > len) {
    len = sublen;
    sub = {b, i};
  }
  return sub;
}
int main(int argc, char** argv)
{
  if (argc != 2) {
    return 0;
  }
  auto p      = notdupcharSubString(argv[1]);
  auto [b, e] = p;
  std::copy(argv[1] + b, argv[1] + e, std::ostream_iterator<char>(std::cout, ""));
}
Read More

24点游戏的一种实现

algorithm parser

24点游戏是一种扑克牌游戏，抽四张扑克牌，寻找表达式，以这四张扑克牌的数字表示为操作数，如果表达式的结果为24，则代表成功找到。实现使用了穷举法，对于任意大于零小于13的四个数，遍历这四个数的所有四则运算表达式，如果表达式结果为24则输出。使用了boost spirit x3来做表达式值的解析，原本使用boost spirit2实现，可有除零错；为了处理除零，改用spirit x3，使用lambda来表示语法解析时的动作。

用法例子：
./game 5 5 5 5
((5*5)-(5/5))

//game.cpp
#include <algorithm>
#include <complex>
#include <exception>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/home/x3.hpp>

#include "exprs.h"
namespace x3    = boost::spirit::x3;
namespace ascii = boost::spirit::x3::ascii;
namespace parser
{
using x3::eps;
using x3::int_;
using x3::lexeme;
x3::rule<class expr, int> const   expr      = "expr";
x3::rule<class term, int> const   term      = "term";
x3::rule<class factor, int> const factor    = "factor";
x3::rule<class group, int> const  group     = "group";
auto                              indentity = [&](auto& ctx) { _val(ctx) = _attr(ctx); };
auto                              multi     = [&](auto& ctx) { _val(ctx) *= _attr(ctx); };
auto                              divide    = [&](auto& ctx) {
  if (_attr(ctx) && (!(_val(ctx) % _attr(ctx)))) {
    _val(ctx) /= _attr(ctx);
  } else {
    _pass(ctx) = false;
  }
};
auto       add        = [&](auto& ctx) { _val(ctx) += _attr(ctx); };
auto       sub        = [&](auto& ctx) { _val(ctx) -= _attr(ctx); };
auto const expr_def   = term[indentity] >> *(('+' >> term[add]) | ('-' >> term[sub]));                 //左结合
auto const term_def   = factor[indentity] >> *(('*' >> (factor)[multi]) | ('/' >> (factor)[divide]));  //左结合
auto const factor_def = (int_ | group);
auto const group_def  = '(' >> expr >> ')';

BOOST_SPIRIT_DEFINE(expr, term, factor, group);
}  // namespace parser

bool verify(std::string const& sv) noexcept
{
  size_t l = 0;
  try {
    int n = std::stoi(sv, &l);
    return (l == sv.size() && (n >= 0) && (n < 14));
  } catch (...) {
    std::cerr << "function verify: string:" << sv << " stoi failed" << std::endl;
    return false;
  }
}

int main(int argc, char** argv)
{
  if (argc < 5) {
    std::cerr << "usage sample: ./game [1-13] [1-13] [1-13] [1-13] \n";
    return 0;
  }
  bool good = std::all_of(&argv[1], &argv[5], verify);
  if (!good) {
    std::cerr << "usage sample: ./game [1-13] [1-13] [1-13] [1-13] \n";
    return 0;
  }

  std::vector<std::string> v{std::string(argv[1]), std::string(argv[2]), std::string(argv[3]), std::string(argv[4])};

  using parser::expr;
  auto allexprs = getAllexprs(v);
  for (auto&& oneexpr : allexprs) {
    int                         result{0};
    std::string::const_iterator iter = oneexpr.cbegin();
    std::string::const_iterator end  = oneexpr.cend();
    try {
      bool r = x3::parse(iter, end, expr, result);
      if (r && iter == end && result == 24) {
        std::cout << oneexpr << std::endl;
      } else {
      }
    } catch (...) {
      std::cout << oneexpr << ": exception caught\n";
    }
  }
}

// exprs.cpp
#include <algorithm>
#include <complex>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <exception>
#include "exprs.h"
std::vector<std::string> getAllexprs(std::vector<std::string>& v)
{
  std::vector<std::string> r;
  auto                     all = getAllPerms(v);
  for (auto&& i : all) {
    auto pairs = generateExprs(i.begin(), i.end());
    for (auto&& t : pairs) {
    }
    r.insert(r.end(), pairs.begin(), pairs.end());
  }
  for (auto&& expr : r) {
  }
  return r;
}
std::vector<std::vector<std::string>> getAllPerms(std::vector<std::string> v)
{
  std::vector<std::vector<std::string>> r;
  r.push_back(v);
  while (std::next_permutation(v.begin(), v.end())) {
    r.push_back(v);
  }
  return r;
}

//exprs.h
#pragma once

#include <vector>
#include <string>
template <class I>
std::vector<std::string> generateExprs(I b, I e)
{
  int                      n = e - b;
  std::vector<std::string> v;
  v.reserve(24);
  if (n == 0) {
    v.push_back(std::string{});
    return v;
  } else if (n == 1) {
    v.push_back(std::string("") + *b + std::string(""));
    return v;
  } else {
    for (int i = 1; i < n; ++i) {
      auto l = generateExprs(b, b + i);
      auto r = generateExprs(b + i, e);
      for (auto li : l) {
        for (auto ri : r) {
          std::string s = std::string("(") + li + std::string("+") + ri + ")";
          v.push_back(s);
          s = std::string("(") + li + std::string("-") + ri + ")";
          v.push_back(s);
          s = std::string("(") + li + std::string("*") + ri + ")";
          v.push_back(s);
          s = std::string("(") + li + std::string("/") + ri + ")";
          v.push_back(s);
        }
      }
    }
    return v;
  }
}
std::vector<std::string> getAllexprs(std::vector<std::string>& v);

std::vector<std::vector<std::string>> getAllPerms(std::vector<std::string> v);
Read More

使用asio和boost fiber纤程实现echo服务器

asio fiber

boost fiber提供了编写异步程序的另一种方式，发起异步调用时切换上下文，由调度器迁移到其他纤程，当异步操作完成时，将原来纤程加入就绪队列，最终不再wait，成功执行完成操作，下文我们使用纤程实现echo服务器，可以看到会话session的语法和过程式调用一样简单。

#include <boost/asio/io_context.hpp>
#include <boost/asio/ip/tcp.hpp>
#include <boost/asio/spawn.hpp>
#include <boost/asio/write.hpp>
#include <iostream>
#include <memory>
#include <libs/fiber/examples/asio/yield.hpp>
#include <libs/fiber/examples/asio/detail/yield.hpp>
#include <libs/fiber/examples/asio/round_robin.hpp>

using boost::asio::ip::tcp;

void session(tcp::socket&& socket_)
{
  using boost::fibers::asio::yield;

  {
    try {
      boost::system::error_code ec;
      char                      data[16];
      for (;;) {
        std::size_t n = socket_.async_read_some(boost::asio::buffer(data), yield);

        if (!n) {
          break;
        }
        boost::asio::async_write(socket_, boost::asio::buffer(data, n), yield);
      }
    } catch (std::exception& e) {
      socket_.close();
    }
  }
}
void server(std::shared_ptr<boost::asio::io_context> io_ctx, int port);

int main(int argc, char* argv[])
{
  try {
    int port = 15999;
    if (argc == 2) {
      port = std::atoi(argv[1]);
    }

    std::shared_ptr<boost::asio::io_context> io_ctx = std::make_shared<boost::asio::io_context>();
                   boost::fibers::use_scheduling_algorithm<boost::fibers::asio::round_robin>(io_ctx);

    using boost::fibers::asio::yield;
    boost::fibers::fiber(server, io_ctx, port).detach();
    io_ctx->run();

  } catch (std::exception& e) {
    std::cerr << "Exception: " << e.what() << "\n";
  }
  return 0;
}

void server(std::shared_ptr<boost::asio::io_context> io_ctx, int port)
{
  tcp::acceptor acceptor(*io_ctx, tcp::endpoint(tcp::v4(), port));
  using boost::fibers::asio::yield;

  for (;;) {
    boost::system::error_code ec;
    tcp::socket               socket(*io_ctx);
    acceptor.async_accept(socket, yield[ec]);
    if (!ec) {
      boost::fibers::fiber(session, std::move(socket)).detach();
    }
  }
}
Read More