3
\$\begingroup\$

I'm learning modern C++ and also algorithms, and am doing some practice by coding up some simple algorithms. Also trying to use templates whenever possible as I'm quite unfamiliar with generic programming.

Would like some help in reviewing the code in terms of design, efficiency, conciseness, and style. Please do not hold back and rip my code apart. It's the best way for me to learn :) thank you! I'm using MSVC, C++17.

// version for contaners with random access
// move minima to correct position (sweep from right to left)
template<typename T>
void bubbleRandCppStl(T& container) {
    for (auto i{ container.rend() - 1 }; i != container.rbegin(); --i) {
        bool swapped {}; // flag to store if swap occured in sweep
        for (auto j{ container.rbegin() }; j != i; ++j) {
            if (*j < *(j + 1)) {
                std::iter_swap(j, j + 1);
                swapped = true;
            }
        }
        if (!swapped) { // end early if no swap occurred in sweep
            break;
        }
    }
}

// version for lists (std::list and std::forward_list)
// move maxima to correct position (sweep from left to right, because forward iterator is unidirectional)
template<typename T>
void bubbleListCppStl(T& container) {
    // container.size() takes O(n) time, so we just do a full sweep
    // and get the size at the same time
    typename T::size_type sz{};
    bool swapped{}; // flag to store if swap occured in sweep
    for (auto i{ container.begin() }, after_i{ ++container.begin() };
        after_i != container.end(); ++i, ++after_i) {
        ++sz;
        if (*i > * after_i) {
            std::iter_swap(i, after_i);
            swapped = true;
        }
    }
    if (!swapped) { // end early if no swap occurred in sweep
        return;
    }

    // decrement size as we now need to sort only sz - 1 elements
    --sz;

    // sort the remaining elements
    for (; sz > 1; --sz) {
        auto i{ container.begin() };
        for (auto elem_left{ sz }; elem_left > 1; --elem_left, ++i) {
            if (*i > * (std::next(i))) {
                std::iter_swap(i, std::next(i));
                swapped = true;
            }
        }
        if (!swapped) { // end early if no swap occurred in sweep
            break;
        }
    }
}

```
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Not sure why you need different algorithms for this. Don't quite understand why the random access iterator version is more efficient. \$\endgroup\$ – Martin York Sep 4 '20 at 17:55
3
\$\begingroup\$

Welcome to Code Review. Here's some suggestions:

  • Instead of taking a container as argument, take a pair of iterators for flexibility.

  • Provide one function that uses iterator_category to find the correct version.

  • Allow the user to specify a custom comparator.

  • Personally, I'd say that bool swapped{false}; is clearer than bool swapped{}.

  • Constantly swapping seems less efficient than moving.

  • Are you sure you need reverse iterators here? Just traversing from left to right seems fine.

  • Calculating std::next(i) twice doesn't feel efficient.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.