Return to Answer

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()) {

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.

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()) {

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.

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()) {

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()) {

As far as the algorithm goes, yes, there's better. In particular, it looks like your current algorithm is \$O(N^2)\$, but it's possible to do the job in \$O(N)\$ (as you probably expected).

The first step would be to reverse the entire second half of your input. From there you can use an in-place shuffle algorithm. Also see an old answer on SO.

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.

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()) {