3
\$\begingroup\$

I have just learnt the strategy pattern. I'm using this pattern to implement this UML to better understand it. Here is the code snippet:

#include<iostream>
#include<functional>
#include<vector>
#include<memory>

template<class T>
class ISortingStrategy
{
public:
    virtual void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator) = 0;
    virtual ~ISortingStrategy() = default;
};

template<class T>
class SelectSort final : public ISortingStrategy<T>
{
public:
    void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator = std::less<T> ()) override
    {

        for(std::size_t i=0; i<cnt-1; i++)
        {
            T max = *(org_ptr+i);
            std::size_t max_idx = i;
            for(std::size_t j=i+1; j<cnt; j++)
            {
                if(less_operator(max, *(org_ptr+j)))
                {
                    max = *(org_ptr+j);
                    max_idx = j;
                }
            }

            if(max_idx !=i)
            {
                std::swap(*(org_ptr+i), *(org_ptr+max_idx));
            }
        }
    }

    ~SelectSort() override = default;
};

template<class T>
class MergeSort : public ISortingStrategy<T>
{
public:
    void sort(T *const org_ptr, std::size_t size, std::function<bool(const T&, const T&)> less_operator = std::less<T> ()) override
    {
        std::size_t max_sub_size = 2;
        while(max_sub_size<size)
        {
            if(size<=1)
            {
                return;
            }
            if(size==2)
            {
                if(less_operator(*org_ptr, *(org_ptr+1)))
                {
                    std::swap(*org_ptr, *(org_ptr+1));
                }
                return;
            }
            else
            {
                std::size_t size1{size>>1}, size2{size - size1};
                T* const ptr1 = org_ptr;
                T* const ptr2 = org_ptr+size1;

                sort(ptr1, size1, less_operator);
                sort(ptr2, size2, less_operator);

                auto res = merge(ptr1, size1, ptr2,  size2, less_operator);

                std::copy(res.begin(), res.end(), org_ptr);

                max_sub_size = res.size();
            }
        }
    }

    std::vector<T> merge(T * const ptr1, std::size_t size1, T* const ptr2, std::size_t size2, std::function<bool(const T&, const T&)> less_operator=std::less<T>())
    {
        std::size_t res_size = size1+size2;
        std::vector<T> res_ptr(size1+size2, T{});

        std::size_t part1_idx{0}, part2_idx{0};
        T part1_val{}, part2_val{};

        for(std::size_t k=0; k< res_size; k++)
        {
            if(part1_idx<size1)
            {
                part1_val = *(ptr1+part1_idx);
            }
            else
            {
                std::copy(ptr2+part2_idx, ptr2+size2, res_ptr.data()+k);
                break;
            }

            if(part2_idx<size2)
            {
                part2_val = *(ptr2+part2_idx);
            }
            else
            {
                std::copy(ptr1+part1_idx, ptr1+size1, res_ptr.data()+k);
                break;
            }

            if(less_operator(part1_val, part2_val))
            {
                ++part2_idx;
                res_ptr[k] = part2_val;
            }
            else
            {
                ++part1_idx;
                res_ptr[k] = part1_val;
            }
        }

        return res_ptr;
    }

    ~MergeSort() override = default;
};

template<class T>
class Client
{
public:
    Client(ISortingStrategy<T>* sort_ptr):m_sort_ptr(sort_ptr){};
    void sort(T *const org_ptr, std::size_t cnt, std::function<bool(const T&, const T&)> less_operator =  std::less<T> ())
    {
        m_sort_ptr->sort(org_ptr, cnt, less_operator);
    }
private:
    ISortingStrategy<T>* m_sort_ptr;
};

int main()
{
    Client<int> client(new MergeSort<int>());

    std::vector<int> vec{5, 9, 6, 11, 3, 7, 1};
    client.sort(const_cast<int*>(vec.data()), vec.size());

    for(const auto& val:vec)
    {
        std::cout << val << std::endl;
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ Interface to algorithms in C++ is an iterator. \$\endgroup\$ Commented May 6 at 19:36
  • \$\begingroup\$ @MartinYork Thank you for pointint out that. But for non-continuous and non-bidirectional container,(say std::forward_list) sorting would be very very slow. \$\endgroup\$
    – John
    Commented May 7 at 2:18
  • 1
    \$\begingroup\$ If you want to limit your algorithm to specific types of iterator, that is valid. That does not change the fact that we basically have effectively a standard model that uses iterators (or ranges that are based on iterators) for the interface to algorithms. Trying to shoe horn in C like semantics is bad design. \$\endgroup\$ Commented May 7 at 16:55
  • \$\begingroup\$ @MartinYork I see, thank you. \$\endgroup\$
    – John
    Commented May 8 at 2:47
  • 1
    \$\begingroup\$ Note: You can iterators on an C_array using std::begin() and std::end() no work required. \$\endgroup\$ Commented May 8 at 15:33

2 Answers 2

7
\$\begingroup\$

This is a bad example

The class Client adds no value to the code whatsoever, in main() you can just call a strategy directly:

int main() {
    std::vector<int> vec{5, 9, 6, 11, 3, 7, 1};
    MergeSort<int>{}.sort(const_cast<int*>(vec.data()), vec.size());
    …
}

In fact, there is no reason to make anything a class at all, just making free functions merge_sort() and select_sort() is enough.

Also, while you use the strategy pattern for the sorting algorithm, you use std::function<> for the comparison function. If anything would benefit from the strategy pattern, it would be the comparison function, not the sorting algorithm!

Memory leak

Since you didn't use a smart pointer for m_sort_ptr, there will be a memory leak when client goes out of scope.

Use the same API as the standard library where possible

Your sort() functions don't look like std::sort(). In particular, you take a pointer to the first element and a size. The problem is that your code will then only work on data which is stored contiguously in memory, like in an array or in a std::vector, but it wouldn't be able to sort anything stored in a different type of container.

Ideally, your sort() functions look the same as std::sort() (or even better, like std::ranges::sort()). This makes it much more compatible with other container types, and it also makes it easier to switch between your sort() functions and the standard library's ones.

Minor issues

  • Naming: Client is too generic.
  • Unnecessary use of const_cast<>(); vec.data() already returns a non-const int*, and if it did return a const int*, then casting const away would probably not be a good idea anyway.
  • Prefer to use '\n' instead of std::endl.
  • Why is SelectSort final but MergeSort is not?
\$\endgroup\$
6
\$\begingroup\$

I haven't looked extensively, but a couple things immediately stand out to me.

Comparison operator

In your base class, the interface ISortingStrategy, you accept a parameter called less_operator. In all of your subclasses, you pass in std::less<T> as the default value for this parameter. But when I call sort on one of your subclasses, there is nothing stopping me from passing in some other comparison function, such as std::greater<T>. Wouldn't it then make more sense to just call this parameter operator (or better yet, something more clear like comparison_operator) since the user can choose any comparison function they want to use to sort their data?

Merge is different

Your MergeSort class implements the sort function from ISortingStrategy<T>, but it also has an additional merge function. This seems a little out of place, since merge has nothing to do with sort, so it doesn't really make sense that it's a part of the MergeSort class.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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