Just glancing at it, this:

    template<class BidirIt>
    void weave(BidirIt first, BidirIt last) {
        if ((last - first) < 3) {
            return;
        }

...jumped out--although the template parameter seems to imply that you want this to work for bidirectional iterators, the subtraction will only work for a random access iterator. To work for bidirectional iterators, you'll want to use `std::distance` instead.

Although it's only in the test code:

    std::ostream& operator<<(std::ostream& out, const std::vector<int>& v) {
        if (v.begin() == v.end()) {
            return out << "{}";
        }

...I'd prefer `if (v.empty()) {`