1
\$\begingroup\$

I was solving a DSA question, running median in a stream. And I decided to design my own stream class with additional features.

template<typename T>
class ActionInterface{

    public :
        virtual void process(const T element) = 0;
};

template<typename T,typename V>
class Action : public ActionInterface<T> {

    protected :
        
        V result;
        Action() : result((V)false) {};

    public :
        
        virtual void process(const T element) = 0;
        
        virtual V getResult() const final{

            return result;
        };
};

template <typename T>
class Stream{

    private :
        
        vector<T> buffer;
        unordered_map<string, ActionInterface<T>* > actions;

        void processActions(){

            for(const auto& [key, action] : actions){

                action->process(buffer.back());
            }
        }

    public :
        
        Stream(){};

        void addAction(string actionName, ActionInterface<T> *action){

            actions[actionName] = action;            
        }

        void addElement(const T element){

            buffer.push_back(element);
            processActions();
        };

        ActionInterface<T> *getActionObject(string actionName) const{
            
            if(actions.find(actionName) == actions.end())
                return nullptr;
            
            return actions.at(actionName);
        };

        ~Stream(){

             for(const auto& [key, action] : actions){

                delete action;
            }
        }

};

template<typename T,typename V>
class RunningMedian : public Action<T,V>
{
    private :
        priority_queue<T> max_heap;
        priority_queue<T,vector<T>,greater<T>> min_heap;
    
    public :
        RunningMedian() {};
        virtual void process(const T element);
};

template<typename T, typename V> void RunningMedian<T,V>::process(const T element){

    if(element <= this->result)
        max_heap.push(element);
    else
        min_heap.push(element);

    if(abs((int)max_heap.size() - (int)min_heap.size()) > 1){

        if(max_heap.size() > min_heap.size()){

            min_heap.push(max_heap.top());
            max_heap.pop();
        }       
        else{

            max_heap.push(min_heap.top());
            min_heap.pop();
        }
    }

    if(max_heap.size() == min_heap.size())
        this->result = ((V)max_heap.top() + min_heap.top())/2;
    else
        this->result = (max_heap.size() > min_heap.size())? max_heap.top() : min_heap.top();
}

vector<double> Solution::solve(vector<int> &A) {

    int n = A.size();
    Stream<int> *stream = new Stream<int>();
    ActionInterface<int> *action = new RunningMedian<int,double>();
    vector<double> result(n);

    stream->addAction("runningMedian", action);
    for(int i=0;i<n;i++){

        stream->addElement(A[i]);
        result[i] = ((RunningMedian<int,double> *)action)->getResult()
    }

    delete stream;
    return result;
}

Any suggestion would be appreciated. Thanks in advance.

\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

Where are the tests?

The code doesn't compile - I needed to add a missing semicolon in Solution::solve() and prefix with some definitions:

#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <functional>

using std::vector;
using std::string;
using std::unordered_map;
using std::priority_queue;
using std::greater;

namespace Solution 
{
    std::vector<double> solve(std::vector<int>&);
}

(Though really I wouldn't have all those usings - just write the full names instead).

Even with these fixes, I get a lot of compiler warnings:

269757.cpp: In function ‘std::vector<double> Solution::solve(std::vector<int>&)’:
269757.cpp:142:19: warning: conversion from ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} to ‘int’ may change value [-Wconversion]
  142 |     int n = A.size();
      |             ~~~~~~^~
269757.cpp: In instantiation of ‘class ActionInterface<int>’:
269757.cpp:35:7:   required from ‘class Action<int, double>’
269757.cpp:102:7:   required from ‘class RunningMedian<int, double>’
269757.cpp:144:66:   required from here
269757.cpp:28:7: warning: ‘class ActionInterface<int>’ has virtual functions and accessible non-virtual destructor [-Wnon-virtual-dtor]
   28 | class ActionInterface{
      |       ^~~~~~~~~~~~~~~
269757.cpp: In instantiation of ‘class Action<int, double>’:
269757.cpp:102:7:   required from ‘class RunningMedian<int, double>’
269757.cpp:144:66:   required from here
269757.cpp:35:7: warning: base class ‘class ActionInterface<int>’ has accessible non-virtual destructor [-Wnon-virtual-dtor]
   35 | class Action : public ActionInterface<T> {
      |       ^~~~~~
269757.cpp:35:7: warning: ‘class Action<int, double>’ has virtual functions and accessible non-virtual destructor [-Wnon-virtual-dtor]
269757.cpp: In instantiation of ‘class RunningMedian<int, double>’:
269757.cpp:144:66:   required from here
269757.cpp:102:7: warning: base class ‘class Action<int, double>’ has accessible non-virtual destructor [-Wnon-virtual-dtor]
  102 | class RunningMedian : public Action<T,V>
      |       ^~~~~~~~~~~~~
269757.cpp:102:7: warning: ‘class RunningMedian<int, double>’ has virtual functions and accessible non-virtual destructor [-Wnon-virtual-dtor]
269757.cpp: In instantiation of ‘Stream<T>::Stream() [with T = int]’:
269757.cpp:143:43:   required from here
269757.cpp:70:9: warning: ‘Stream<int>::buffer’ should be initialized in the member initialization list [-Weffc++]
   70 |         Stream(){};
      |         ^~~~~~
269757.cpp:70:9: warning: ‘Stream<int>::actions’ should be initialized in the member initialization list [-Weffc++]
269757.cpp: In instantiation of ‘RunningMedian<T, V>::RunningMedian() [with T = int; V = double]’:
269757.cpp:144:66:   required from here
269757.cpp:109:9: warning: ‘RunningMedian<int, double>::max_heap’ should be initialized in the member initialization list [-Weffc++]
  109 |         RunningMedian() {};
      |         ^~~~~~~~~~~~~
269757.cpp:109:9: warning: ‘RunningMedian<int, double>::min_heap’ should be initialized in the member initialization list [-Weffc++]
269757.cpp: In instantiation of ‘Stream<T>::~Stream() [with T = int]’:
269757.cpp:154:12:   required from here
269757.cpp:95:17: warning: deleting object of abstract class type ‘ActionInterface<int>’ which has non-virtual destructor will cause undefined behavior [-Wdelete-non-virtual-dtor]
   95 |                 delete action;
      |                 ^~~~~~~~~~~~~

Don't ignore warnings - your compiler is your first reviewer.

For example, that last one causes a memory leak:

==2921039== 32 bytes in 1 blocks are definitely lost in loss record 1 of 2
==2921039==    at 0x4839F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2921039==    by 0x10E515: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (new_allocator.h:127)
==2921039==    by 0x10D354: allocate (allocator.h:201)
==2921039==    by 0x10D354: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (alloc_traits.h:460)
==2921039==    by 0x10C929: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (stl_vector.h:346)
==2921039==    by 0x10C5AF: void std::vector<int, std::allocator<int> >::_M_realloc_insert<int const&>(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) (vector.tcc:440)
==2921039==    by 0x10BA83: std::vector<int, std::allocator<int> >::push_back(int const&) (stl_vector.h:1198)
==2921039==    by 0x10F157: std::priority_queue<int, std::vector<int, std::allocator<int> >, std::greater<int> >::push(int const&) (stl_queue.h:642)
==2921039==    by 0x10EF2B: RunningMedian<int, double>::process(int) (269757.cpp:114)
==2921039==    by 0x10BB1E: Stream<int>::processActions() (269757.cpp:59)
==2921039==    by 0x10B0B7: Stream<int>::addElement(int) (269757.cpp:75)
==2921039==    by 0x10A3F0: Solution::solve(std::vector<int, std::allocator<int> >&) (269757.cpp:140)
==2921039==    by 0x10A58F: main (269757.cpp:153)
==2921039== 
==2921039== 32 bytes in 1 blocks are definitely lost in loss record 2 of 2
==2921039==    at 0x4839F2F: operator new(unsigned long) (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==2921039==    by 0x10E515: __gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*) (new_allocator.h:127)
==2921039==    by 0x10D354: allocate (allocator.h:201)
==2921039==    by 0x10D354: std::allocator_traits<std::allocator<int> >::allocate(std::allocator<int>&, unsigned long) (alloc_traits.h:460)
==2921039==    by 0x10C929: std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long) (stl_vector.h:346)
==2921039==    by 0x10C5AF: void std::vector<int, std::allocator<int> >::_M_realloc_insert<int const&>(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >, int const&) (vector.tcc:440)
==2921039==    by 0x10BA83: std::vector<int, std::allocator<int> >::push_back(int const&) (stl_vector.h:1198)
==2921039==    by 0x10F105: std::priority_queue<int, std::vector<int, std::allocator<int> >, std::less<int> >::push(int const&) (stl_queue.h:642)
==2921039==    by 0x10EFE3: RunningMedian<int, double>::process(int) (269757.cpp:121)
==2921039==    by 0x10BB1E: Stream<int>::processActions() (269757.cpp:59)
==2921039==    by 0x10B0B7: Stream<int>::addElement(int) (269757.cpp:75)
==2921039==    by 0x10A3F0: Solution::solve(std::vector<int, std::allocator<int> >&) (269757.cpp:140)
==2921039==    by 0x10A58F: main (269757.cpp:153)

We don't need a modifiable copy of the input vector, so accept it by reference to const. Consider accepting arbitrary ranges:

std::vector<double> solve(std::ranges::forward_range auto);

Transferring ownership using raw pointers is error-prone and therefore dangerous. Use smart pointers instead to indicate the ownership semantics (e.g. pass a unique pointer by value when transferring ownership from one object to another).

Better still, avoid pointers altogether.

Consider

    using Action<T,V>::result;

That lets us write result instead of the ugly this->result all over the place.

Don't write empty default constructors. Just let the compiler default them naturally.

When overriding functions, use the override keyword instead of virtual.

Don't cast std::size_t to int like this:

if(abs((int)max_heap.size() - (int)min_heap.size()) > 1){
    if(max_heap.size() > min_heap.size()){

That's probably better split out into simpler tests anyway:

if (max_heap.size() > min_heap.size() + 1) {
    min_heap.push(max_heap.top());
    max_heap.pop();
}
if (min_heap.size() > max_heap.size() + 1) {
    max_heap.push(min_heap.top());
    min_heap.pop();
}

ActionInterface and Action look like overkill. Why not just pass a suitable invocable object? It can hold a reference to a result value which it updates.

Why does Stream have a buffer member that is only written and never read?

Why do we name the actions, but never use those names for anything?

The for loop in solve looks like it could be a std::transform().

Simplified code

Based on the above observations, I reduced to this version, which gives me no compiler warnings and no memory issues in Valgrind:

#include <concepts>
#include <functional>
#include <queue>
#include <string>
#include <vector>

namespace Solution
{
    std::vector<double> solve(const std::vector<int>&);
}


template <typename T>
class Stream
{
    std::vector<std::function<void(T)>> actions = {};

public:
    void addAction(std::invocable<T> auto action)
    {
        actions.emplace_back(std::move(action));
    }

    void addElement(const T value)
    {
        for (const auto& action: actions) {
            action(value);
        }
    }
};

template<typename T>
class RunningMedian
{
    std::priority_queue<T> max_heap = {};
    std::priority_queue<T,std::vector<T>,std::greater<T>> min_heap = {};
    T& median;

public:
    RunningMedian(T& median)
        : median{median}
    {}

    void operator()(const T element)
    {
        if (element < median)
            max_heap.push(element);
        else
            min_heap.push(element);

        if (max_heap.size() > min_heap.size() + 1) {
            min_heap.push(max_heap.top());
            max_heap.pop();
        } else if (min_heap.size() > max_heap.size() + 1) {
            max_heap.push(min_heap.top());
            min_heap.pop();
        }

        median
            = min_heap.size() < max_heap.size() ? max_heap.top()
            : max_heap.size() < min_heap.size() ? min_heap.top()
            : (max_heap.top() + min_heap.top()) / 2;
    }
};

std::vector<double> Solution::solve(const std::vector<int>& input)
{
    Stream<int> stream{};
    double median = 0.0;
    stream.addAction(RunningMedian<double>{median});

    std::vector<double> result;
    result.reserve(input.size());
    for (auto i: input) {
        stream.addElement(i);
        result.push_back(median);
    }

    return result;
}

// Simple test.  TODO: more rigorous testing
#include <iostream>
int main()
{
    std::vector a = { 1, 1, 1, 2, 3, 4, 5, 6, 5, 5};
    const char* sep = "";
    for (auto i: Solution::solve(a)) {
        std::cout << sep << i;
        sep = ", ";
    }
    std::cout << '\n';
}
\$\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.