4
\$\begingroup\$

I have made some composited container Range which accepts either a min/max range as a std::pair or a set of integers as a std::set.

internally it saves a copy of the input by as void *

This container supports iterators which is useful. I am not sure if there is a better implementation to mimic an iteration for both, a range or a list of numbers, also with respect to move semantics. I could have used boost::variant types, but that only bloats the whole class, and for the iterator I need another boost::variant filled with iterators ...?

Have I used the move semantics correctly?

I added also some performance test in the MWE: MWE LINK

template<typename Type>
class Range{
    public:
    typedef std::pair<Type,Type> Pair;
    typedef std::set<Type> Set;

    Range(const Pair & pair){
        m_ptr = static_cast<void * >( new Pair(pair) );
        m_which = 0;
    }
    Range(Pair && pair){
        m_ptr = static_cast<void * >( new Pair( std::move(pair) ) );
        m_which = 0;
    }


    Range(const Set & set){
        m_which = 1;
        m_ptr = static_cast<void * >( new Set(set) );
    }
    Range(Set && set){
        m_which = 1;
        m_ptr = static_cast<void * >( new Set( std::move(set) ) );
    }


    Range(const Range & r){
        *this = r;
    }

    // Move Constructor
    Range(Range && r){
        *this = std::move(r);
    }

    // Move Assigment
    Range & operator=(Range && r){
        assert(r.m_ptr);
        if(m_ptr != r.m_ptr && this != &r ){ // Prevent self-assignment
            ~Range(); // delete resources
            m_ptr  =  std::move(r.m_ptr);
            m_which = std::move(r.m_which);
            r.m_ptr = nullptr;
            r.m_which = 0;
        }
    }

    // Assigment
    Range & operator=(Range & r){
        if(m_ptr != r.m_ptr && this != &r ){ // Prevent self-assignment
            if(r.m_which == 0){
                if(m_which == 0 && m_ptr){
                    *static_cast<Pair*>(m_ptr) = *static_cast<Pair*>(r.m_ptr); // Copy
                }
                m_ptr = static_cast<void * >( new Pair(*static_cast<Pair*>(r.m_ptr))); // Make new and Copy
            }else if(r.m_which==1){
                if(m_which == 1 && m_ptr){
                    *static_cast<Set*>(m_ptr) = *static_cast<Set*>(r.m_ptr); // Copy
                }
                m_ptr = static_cast<void * >( new Set(*static_cast<Set*>(r.m_ptr)));  // Make new and Copy
            }
            m_which = r.m_which;
        }
    }


    ~Range(){
        if(m_ptr){
            if(m_which == 0){
                auto p = static_cast<Pair * >(m_ptr); delete p;
            }else if(m_which==1){
                auto p = static_cast<Set * >(m_ptr); delete p;
            }
            m_which = 0;
        }
    }

    class iterator {
    public:
        iterator():m_r(nullptr),m_cur(0){};

        iterator(Range * r, bool atEnd = false):m_r(r) {
            if(!m_r->m_ptr){
                m_cur=0;
                return;
            }
            if(m_r->m_which == 0){
                auto p = static_cast<Pair * >(m_r->m_ptr);
                if(atEnd){
                    m_cur = p->second;
                }else{
                    m_cur = p->first;
                }
            }else{
                auto p = static_cast<Set * >(m_r->m_ptr);
                if(atEnd){
                    m_it = p->end();
                }else{
                    m_it = p->begin();
                }
            }
        };

        //Delete assignment operator
        iterator & operator=(const iterator&) = delete;
        iterator & operator=(iterator&) = delete;

        ~iterator() {
        }

        iterator( const iterator & it ): m_r(it.m_r), m_cur(it.m_cur) {
        }

        /** pre-increment ++it
        * Allow to iterate over the end of the sequence
        */
        iterator & operator++() {
                if(m_r->m_which == 0){
                    ++m_cur;
                }else {
                    ++m_it;
                }
            return *this;
        }
        /** post-increment it++
        *
        */
        iterator operator++(int) {
            iterator it(*this);
            operator++();
            return it;
        }


        bool operator==(const iterator &rhs) {
            if(m_r->m_which == 0){
                return m_cur == rhs.m_cur; // Two iterators for differente ranges, might compare equal!
            }else {
                return m_it == rhs.m_it;
            }

        }

        // Return false if the same!
        bool operator!=(const iterator &rhs) {
            return !(*this==rhs);
        }

        Type operator*() {
            if(m_r->m_which == 0){
                return m_cur ;
            }else {
                return *m_it;
            }
        }
    private:
        Range * m_r;
        typename Set::iterator m_it;
        Type m_cur;
    };

    iterator begin(){
        return iterator(this);
    }

    iterator end(){
        return iterator(this,true);
    }

    private:
    unsigned int m_which = 0;
    void * m_ptr = nullptr;
};

Usage:

    std::pair<Type,Type> p(0,100);
    Range<Type> range( std::pair<Type,Type>(0,100) );
        for(auto it=range.begin(); it != range.end(); ++it) {
            std::cout << *it << std::endl;
        }
    }

Here the updated MWE (from the comments)! =) https://ideone.com/jXI7Si

\$\endgroup\$
  • \$\begingroup\$ can you show us a few lines of main() that demonstrates your intended use case of Range? \$\endgroup\$ – TemplateRex Jun 5 '14 at 18:00
  • \$\begingroup\$ I never understood why you new that stuff. There are great containers like boost::any and boost::variant which do all the magic stuff for you w/o dynamic memory allocation. Also, I'm not sure what use-cases you had in mind, but where do you need a range that's separate from the original container? Typically, I want a range to iterate over things etc., i.e. I create a range temporarily so that it can point to the original container. \$\endgroup\$ – dyp Jun 5 '14 at 19:43
  • \$\begingroup\$ the use-case is: I have a class A which takes from outside a Range class range, stores it, and uses this range to iterate over to produce some output. I could have a boost::variant in class A which has a std::pair or std::set, then in class A I need some variant adpater? (how?) which extracts anyway some kind of general iterator for both types which lets me iterate over the range. This usecase is why I like to have a general object I am working with to be flexibel \$\endgroup\$ – Gabriel Jun 6 '14 at 7:56
5
\$\begingroup\$

You should use template specialization rather than casting to void* here

// Pair or set depends on m_which.
// Very easy to get that screwed up.
// Especially since it is not const.

Range(const Pair & pair){
    m_ptr = static_cast<void * >( new Pair(pair) );
    m_which = 0;
}
Range(const Set & set){
    m_which = 1;
    m_ptr = static_cast<void * >( new Set(set) );
}

Your technique is very error prone as the compiler can no longer validate the types you are using. By using template specialization you remove the problem.

This is the wrong way around.

Range(const Range & r){
    *this = r;
}

You should define the copy constructor like normal. Then define the assignment operator in terms of the copy constructor. It is known as the copy and swap idiom.

Also you don't set up the members. This means unless the assignment operator only sets the values you are looking at undefined behavior when they are read.

// As I suspected the first thing you try and do is read from `m_ptr`.
// This value has not been set in the copy constructor and thus you have
// undefined behavior.
Range & operator=(Range & r){
    if(m_ptr != r.m_ptr && this != &r ){ 

This is very hard to understand.
Comes from casting around void*. Would not do this.

            if(m_which == 0 && m_ptr){
                *static_cast<Pair*>(m_ptr) = *static_cast<Pair*>(r.m_ptr); // Copy
            }

Now you leak the original data and replace it with the a copy of the source.

            m_ptr = static_cast<void * >( new Pair(*static_cast<Pair*>(r.m_ptr))); // Make new and Copy
        }

Copy and Swap idiom looks like this:

Range(Range const& r)
  : m_which(r.m_which)
  , m_ptr(r.m_which == 0
            ? static_cast<void*>(new Pair(*static_cast<Pair*>(r.m_ptr)))
            : static_cast<void*>(new Set(*static_cast<Set*>(r.m_ptr)))
         )
{}

Range& operator=(Range value) // Pass by value to generate copy.
{
    value.swap(*this);        // Swap value with the copy.
    return *this;
}                             // Destructor of `value` cleans up the old value.

void swap(Range& other) noexcept
{
    std::swap(m_which, other.m_witch);
    std::swap(m_ptr,   other.m_ptr);
}

Same problem with the move constructor.

// Move Constructor
Range(Range && r){
    *this = std::move(r);
}

You don't initialize the members. Since the members are POD they have indeterminate values and thus reading them is undefined behavior (unless you assign something to them).

So the move assignment operator has the same problems as the assignment operator as it reads the value of m_ptr (only a problem when called from the move constructor).

// Move Assigment
Range & operator=(Range && r){
    assert(r.m_ptr);

    // Reading m_ptr here.
    // But we have just been called from the move constructor
    // thus m_ptr is not defined.
    if(m_ptr != r.m_ptr && this != &r ){

You are allowed to call the destructor.

        ~Range(); // delete resources

But this stops the object from being an object. The only thing you are allowed to do at this point is call the call placement new to make it a real object again (or pass it around as void*). So calling the destructor is not really a good idea. Move the code for releasing resource into another function and call that from here and the destructor.

OK. So after a move the source should be in a valid state (but can be indeterminate state).

        r.m_ptr = nullptr;
        r.m_which = 0;

I suppose this does that. But a lot of code assumes that m_which of 0 means that it contains a pointer to a pair. You may want to have another state ie 2 (or -1) that indicates nothing is stored in the object.

Personally I would simplify the above:

Range(Range && r)
    : m_which(r.m_wich)
    , m_ptr(r.m_ptr)
{
    // r.m_which = ??   not sure you may want to set this.
    r.m_ptr   = nullptr;
}
Range& operator=(Range&& r)
{
    r.swap(*this);      // Just swap the objects on assignment.
    return *this;
}
\$\endgroup\$
  • \$\begingroup\$ Very good comments, indeed! Helped me alot! Thanks! What do you exactly mean with template spezialization. Do you mean to have a trait struct which accepts a type (set or pair) and returns the correct integer (0,1 for m_which) \$\endgroup\$ – Gabriel Jun 7 '14 at 19:11
  • \$\begingroup\$ @Gabriel: I would create a base type template S class Range {}; that contained common code. Then I would have two specializations template class Range<Pair> {}; and template class Range<Set> {} that each housed the code specific to Pair/Set appropriately. Note (by Pair/Set I am not defining what that is because I have not tried it (could be std:pair/std::set or could by an enum I am not sure of the best approach at this point)). But it is definitely preferable to separate the code out (that way other versions can also be easily added) basically remove the need for m_which and void*. \$\endgroup\$ – Martin York Jun 8 '14 at 18:31
  • \$\begingroup\$ Thats what I though at the first place, but the problem: This range class should be part of a class A and a priori I don't know if it is a Range<Pair> or Range<Set> specialization. So the only way around this would be to have a variant kind of implementation (that was my approach with the void * . Or am I wrong, there is no way other than implementing some kind of a variant type (as boost::variant or boost:any for example) to do this? \$\endgroup\$ – Gabriel Jun 8 '14 at 20:11
  • \$\begingroup\$ @Gabriel: I don't have enough info to comment yeu. Is the decision to choose Range<Pair> over Range<Set> a runtime choice? Or is it part of the class declaration? \$\endgroup\$ – Martin York Jun 8 '14 at 23:07

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.