9
\$\begingroup\$

I would like a review for this code which is used apparently successfully in my current project. More info are available in this gist but I'm pasting here the main info:

The project use C++11/14 as provided by VS2013 (no CTP) and Boost. I didn't try to compile it in other compilers yet (lack of time and resources). The tests are provided in another other file, it compiles and run for me but the tests themselves might require review too. Tests are using GTest. I use custom assert macros which I will not explain here as they are obvious to understand.

AnyValueSet: I use this container more or less as a message board, the values being the messages. Sometime, I use types which are compared using only part of their value and contain more data that are not used in comparison, which is why there are overwritting functions.

I would like reviews in particular concerning correctness (including the tests), performance and security. I expose this code here because I am alone on my (big) project and I fear the lack multiple eyes on the code, in particular for this part of code which is reused several time in the project.

Note that this container isn't supposed to be as generic as a standard or boost container but is specific to my use (which I think should be clear from the tests).

The full code, extracted from my project (which explains the namespace):

#ifndef HGUARD_NETRUSH_INPUT_ANYVALUESET_HPP__
#define HGUARD_NETRUSH_INPUT_ANYVALUESET_HPP__

#include <memory>
#include <typeindex>
#include <vector>

#include <boost/container/flat_map.hpp>
#include <boost/container/flat_set.hpp>
#include <boost/optional.hpp>

#include <utilcxx/assert.hpp>

namespace netrush {
namespace input {

    /** Set that can contain multiple value types.
        The contained types must be Comparable, Copyable and CopyConstructible.
        The identity of values is determined by comparison (operator< and operator==), 
        which allows for the type to have a different identity than it's value, 
        in which case overwriting can be used to change the non-observable state while keeping the identity.
    */
    class AnyValueSet
    {
    public:

        AnyValueSet() = default;

        AnyValueSet( const AnyValueSet& other ) 
        { 
            insert( other );    
        }

        AnyValueSet& operator=( const AnyValueSet& other ) 
        { 
            clear();
            insert( other );
            return *this;
        }

        AnyValueSet( AnyValueSet&& other )
            : m_size_changed( std::move(other.m_size_changed) )
            , m_size( std::move(other.m_size) )
            , m_set_index( std::move(other.m_set_index) )
        {}

        AnyValueSet& operator=( AnyValueSet&& other )
        {
            m_size_changed = std::move(other.m_size_changed);
            m_size = std::move(other.m_size);
            m_set_index = std::move(other.m_set_index);
            return *this;
        }


        /** Add a new value if not already stored.
            @return True if the value have been added, false otherwise.
        */
        template< class ValueType >
        bool add( ValueType&& value )
        {
            auto& value_set = find_or_create_set<ValueType>();
            bool was_added = value_set.add( std::forward<ValueType>(value) );
            if( was_added )
                size_changed();
            return was_added;
        }

        /** Add a new value and overwrite the previous one even if it was already stored. 
            @return True if the value have been added, false if the value was overwritten.
        */
        template< class ValueType >
        bool overwrite( ValueType&& value )
        {
            auto& value_set = find_or_create_set<ValueType>();
            bool was_added = value_set.overwrite( std::forward<ValueType>( value ) );
            if( was_added )
                size_changed();
            return was_added;
        }

        /** Remove a value if it was stored. */
        template< class ValueType >
        void remove( const ValueType& value )
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                value_set->remove( value );
                size_changed();
            }
        }

        /** Remove all values contained in the provided set which are stored in this one. */
        void remove( const AnyValueSet& other )
        {
            if( other.empty() || this->empty() )
                return;

            auto current_slot = begin( m_set_index );
            const auto end_current = end( m_set_index );

            auto other_slot = begin( other.m_set_index );
            const auto end_other = end( other.m_set_index );

            while( current_slot != end_current
                && other_slot != end_other )
            {
                if( current_slot->first == other_slot->first )
                {
                    auto& current_set_ptr = current_slot->second;
                    auto& other_set_ptr = other_slot->second;
                    UCX_ASSERT_NOT_NULL( current_set_ptr );
                    UCX_ASSERT_NOT_NULL( other_set_ptr );
                    current_set_ptr->remove( *other_set_ptr );
                    size_changed();
                    ++other_slot;
                }               
                ++current_slot;
            }
        }

        /** Search for the value comparable to the provided key.
            The key can have a different type than the value or the same type.
            If the value type is specified, the 
            @return Either a copy of the stored value or none if not found.
        */
        template< class ValueType, class KeyType >
        boost::optional<ValueType> find( const KeyType& key ) const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->find( key );
            }
            return {};
        }

        /** Specializatoin of find() in case the value type is not specified. */
        template< class ValueType >
        boost::optional<ValueType> find( const ValueType& value ) const
        {
            return find<ValueType, ValueType>( value );
        }

        /** @return true if the specified key is comparable to a stored value of the specified value type, false otherwise. */
        template< class ValueType, class KeyType >
        bool contains( const KeyType& key ) const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->contains( key );
            }
            return false;
        }

        /** @return true if the value is comparable to a stored value of the same type. */
        template< class ValueType >
        bool contains( const ValueType& value ) const
        {
            return contains<ValueType, ValueType>( value );
        }

        /** Insert all the values from the provided set which are not already stored into this one. */
        void insert( const AnyValueSet& other )
        {
            for( const auto& set_pair : other.m_set_index )
            {
                auto& set_ptr = set_pair.second;
                UCX_ASSERT_NOT_NULL( set_ptr );

                if( auto value_set = find_set( set_pair.first ) )
                {
                    value_set->insert( *set_ptr );
                }
                else
                {
                    m_set_index.emplace( set_pair.first, set_ptr->clone() );
                }
                size_changed();
            }

        }

        /** Insert all the values from the provided set which are not already stored into this one. */
        void insert_overwrite( const AnyValueSet& other )
        {
            for( const auto& set_pair : other.m_set_index )
            {
                auto& set_ptr = set_pair.second;
                UCX_ASSERT_NOT_NULL( set_ptr );

                if( auto value_set = find_set( set_pair.first ) )
                {
                    value_set->insert_overwrite( *set_ptr );
                }
                else
                {
                    m_set_index.emplace( set_pair.first, set_ptr->clone() );
                }
                size_changed();
            }

        }

        /** Copy and return all the values of the specified type. */
        template< class ValueType >
        std::vector<ValueType> all() const
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                return value_set->values();
            }
            return {};
        }

        /** @return How many values are currently stored for all types. */
        size_t size() const 
        { 
            if( m_size_changed )
            {
                m_size_changed = false;
                compute_size();
            }

            return m_size; 
        }

        /** @return true if there is at least one value stored of any type, false otherwise. */
        bool empty() const
        {
            return m_set_index.empty()
                || size() == 0;
        }

        /** Destroy all values of the provided type. */
        template< class ValueType >
        void clear()
        {
            if( auto* value_set = find_set<ValueType>() )
            {
                value_set->clear();
                size_changed();
            }
        }

        /** Destroy all values of all types. */
        void clear()
        {
            for( const auto& set_slot : m_set_index )
            {
                auto& set_ptr = set_slot.second;
                UCX_ASSERT_NOT_NULL( set_ptr );
                set_ptr->clear();
            }
            size_changed();
        }



    private:

        struct Set
        {
            virtual void insert( const Set& other ) = 0;
            virtual void insert_overwrite( const Set& other ) = 0;
            virtual void remove( const Set& other ) = 0;
            virtual std::unique_ptr<Set> clone() = 0;
            virtual size_t size() const = 0;
            virtual void clear() = 0;
            virtual ~Set() = default;
        };

        template< class T >
        class SetOf : public Set
        {
            boost::container::flat_set<T> m_values;
        public:
            SetOf() = default;

            template< class Iterator >
            SetOf( Iterator&& it_begin, Iterator&& it_end )
                : m_values( std::forward<Iterator>( it_begin ), std::forward<Iterator>( it_end ) )
            {}

            /** Add a new value if not already stored.
                @return True if the value have been added, false otherwise.
            */
            bool add( T value ) 
            {
                auto result = m_values.emplace( std::move( value ) );
                return result.second;
            }

            /** Add a new value and overwrite the previous one even if it was already there. 
                @return True if the value have been added, false if the value was overwritten.
            */
            bool overwrite( T value )
            {
                auto result = m_values.insert( value );
                if( !result.second )
                {
                    *result.first = value;
                    return false;
                }
                return true;                    
            }

            void remove( const T& value ) { m_values.erase( value ); }

            template< class KeyType >
            boost::optional<T> find( const KeyType& key ) const
            {
                for( const auto& value : m_values )
                {
                    if( value == key ) 
                        return value;
                }

                return {};
            }

            template< class KeyType >
            bool contains( const KeyType& key ) const 
            { 
                for( const auto& value : m_values )
                {
                    if( value == key )
                        return true;
                }

                return false;
            }

            void insert( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                m_values.insert( begin(specific_set.m_values), end(specific_set.m_values) );
            }

            void insert_overwrite( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                for( auto&& value : specific_set.m_values )
                {
                    overwrite( value );
                }
            }

            void remove( const Set& other ) override
            {
                const auto& specific_set = static_cast<const SetOf<T>&>( other );
                m_values.erase( std::remove_if( begin( m_values ), end( m_values )
                    , [&]( const T& value ) { return specific_set.contains( value ); } )
                    , end( m_values ) );
            }

            std::unique_ptr<Set> clone() override
            {
                return std::make_unique<SetOf<T>>( begin( m_values ), end( m_values ) );
            }

            size_t size() const override { return m_values.size(); }

            std::vector<T> values() const
            {
                return { begin( m_values ), end( m_values ) };
            }

            void clear() override { m_values.clear(); }
        };

        Set* find_set( std::type_index type_id ) const
        {
            auto find_it = m_set_index.find( type_id );
            if( find_it != end( m_set_index ) )
            {
                auto& set_ptr = find_it->second;
                auto& specific_set = *set_ptr;
                return &specific_set;
            }
            return nullptr;
        }


        template< class T, typename ValueType = std::decay<T>::type >
        SetOf<ValueType>* find_set() const 
        { 
            return static_cast<SetOf<ValueType>*>( find_set( typeid( ValueType ) ) ); 
        }

        template< class T, typename ValueType = std::decay<T>::type >
        SetOf<ValueType>& find_or_create_set()
        {
            if( auto* specific_set = find_set<ValueType>() )
            {
                return *specific_set;
            }

            auto new_set = std::make_unique<SetOf<ValueType>>();
            auto position = m_set_index.emplace( typeid( ValueType ), std::move(new_set) ).first;
            auto& set_ptr = position->second;
            return static_cast<SetOf<ValueType>&>( *set_ptr );
        }

        inline void size_changed() const { m_size_changed = true; }

        void compute_size() const
        {
            m_size = 0;
            for( const auto& set_pair : m_set_index )
            {
                auto& set_ptr = set_pair.second;
                m_size += set_ptr->size();
            }
        }


        boost::container::flat_map<std::type_index, std::unique_ptr<Set>> m_set_index;
        mutable bool m_size_changed = false;
        mutable size_t m_size = 0;

    };



}}


#endif

The test code I use:

#include <gtest/gtest.h>

#include <utility>
#include <string>

#include <netrush/system/input/anyvalueset.hpp>

using namespace netrush::input;

struct Foo
{
    int k;
    long l;
};

bool operator==( const Foo& a, const Foo& b )
{
    return a.k == b.k
        && a.l == b.l
        ;
}

bool operator< ( const Foo& a, const Foo& b )
{
    return a.k < b.k
        && a.l < b.l
        ;
}

struct Id
{
    int value;
};

bool operator==( const Id& a, const Id& b )
{
    return a.value == b.value;
}

bool operator< ( const Id& a, const Id& b )
{
    return a.value < b.value;
}


struct Entity // The id is the identity, comparisons use only the id.
{
    Id id;
    std::string name;
};

bool operator==( const Entity& a, const Entity& b )
{
    return a.id == b.id;
}

bool operator< ( const Entity& a, const Entity& b )
{
    return a.id < b.id;
}

bool operator==( const Id& a, const Entity& b )
{
    return a == b.id;
}
bool operator==( const Entity& a, const Id& b )
{
    return b == a;
}

template< class T >
void test_all_operations( AnyValueSet& value_set, T value )
{
    const auto begin_size = value_set.size();
    value_set.add( value );
    ASSERT_TRUE( value_set.contains( value ) );
    const auto stored_value = value_set.find( value );
    ASSERT_EQ( value, *stored_value );
    ASSERT_EQ( begin_size + 1, value_set.size() );

    auto values = value_set.all<T>();
    auto find_it = std::find( begin( values ), end( values ), value );
    ASSERT_NE( end( values ), find_it );
}

TEST( Test_AnyValueSet, any_kind_of_values )
{
    static const auto BLAH = std::string{ "Blah" };

    AnyValueSet value_set;
    test_all_operations( value_set, 42 );
    test_all_operations( value_set, 3.14 );
    test_all_operations( value_set, 0.5f );
    test_all_operations( value_set, Foo{ 42, 5 } );
    test_all_operations( value_set, Id{ 1234 } );
    test_all_operations( value_set, Entity{ Id{ 5678 }, "A" } );
    test_all_operations( value_set, BLAH );

    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 7, value_set.size() );

    AnyValueSet values_to_remove;
    values_to_remove.add( BLAH );
    values_to_remove.add( 0 );
    values_to_remove.add( 2.5 );

    value_set.remove( values_to_remove );
    ASSERT_FALSE( value_set.contains( BLAH ) );
    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 6, value_set.size() );

    value_set.clear<int>();
    ASSERT_FALSE( value_set.empty() );
    ASSERT_EQ( 5, value_set.size() );

    value_set.clear();
    ASSERT_TRUE( value_set.empty() );
}

TEST( Test_AnyValueSet, add_unique_simple_values )
{
    AnyValueSet value_set;
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    value_set.add( 42 );
    ASSERT_EQ( 1, value_set.size() );

}

TEST( Test_AnyValueSet, overwrite_unique_simple_values )
{
    AnyValueSet value_set;
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    value_set.overwrite( 42 );
    ASSERT_EQ( 1, value_set.size() );

}

TEST( Test_AnyValueSet, add_unique_key_values )
{
    AnyValueSet value_set;
    value_set.add( Entity{ Id{ 42 }, "A" } );
    value_set.add( Entity{ Id{ 42 }, "B" } );
    value_set.add( Entity{ Id{ 42 }, "C" } );
    value_set.add( Entity{ Id{ 42 }, "D" } );
    value_set.add( Entity{ Id{ 42 }, "E" } );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }

    AnyValueSet other_set;
    other_set.add( Entity{ Id{ 42 }, "X" } );
    value_set.insert( other_set );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }
}

TEST( Test_AnyValueSet, overwrite_unique_key_values )
{
    AnyValueSet value_set;
    value_set.overwrite( Entity{ Id{ 42 }, "A" } );
    value_set.overwrite( Entity{ Id{ 42 }, "B" } );
    value_set.overwrite( Entity{ Id{ 42 }, "C" } );
    value_set.overwrite( Entity{ Id{ 42 }, "D" } );
    value_set.overwrite( Entity{ Id{ 42 }, "E" } );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "E", entity->name );
    }

    AnyValueSet other_set;
    other_set.add( Entity{ Id{ 42 }, "A" } );
    value_set.insert_overwrite( other_set );
    ASSERT_EQ( 1, value_set.size() );

    {
        auto entity = value_set.find<Entity>( Id{ 42 } );
        ASSERT_TRUE( entity );
        ASSERT_EQ( "A", entity->name );
    }

}


TEST( Test_AnyValueSet, merge_sets_same_type )
{
    AnyValueSet set_a, set_b;

    set_a.add( 1 );
    set_a.add( 2 );
    set_a.add( 3 );
    set_a.add( 4 );

    set_b.add( 1 );
    set_b.add( 2 );
    set_b.add( 3 );
    set_b.add( 4 );
    set_b.add( 5 );
    set_b.add( 6 );
    set_b.add( 7 );
    set_b.add( 8 );

    set_a.insert( set_b );
    ASSERT_EQ( set_a.size(), set_b.size() );
    auto b_values = set_b.all<int>();
    for( const auto i : b_values )
    {
        ASSERT_TRUE( set_a.contains( i ) );
    }

    AnyValueSet set_c;
    set_c.insert( set_a );
    auto c_values = set_c.all<int>();
    for( const auto i : c_values )
    {
        ASSERT_TRUE( set_a.contains( i ) );
    }
    for( const auto i : b_values )
    {
        ASSERT_TRUE( set_c.contains( i ) );
    }

}

TEST( Test_AnyValueSet, merge_sets_different_types )
{
    AnyValueSet set_a, set_b;

    set_a.add( 1 );
    set_a.add( 2 );
    set_a.add( 3 );
    set_a.add( 4 );

    set_b.add( 1.f );
    set_b.add( 2.f );
    set_b.add( 3.f );
    set_b.add( 4.f );
    set_b.add( 5.f );
    set_b.add( 6.f );
    set_b.add( 7.f );
    set_b.add( 8.f );

    set_a.insert( set_b );
    AnyValueSet set_c;
    set_c.insert( set_a );

    {

        auto b_values = set_b.all<int>();
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        auto c_values = set_c.all<int>();
        for( const auto i : c_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_c.contains( i ) );
        }
    }
    {

        auto b_values = set_b.all<float>();
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        auto c_values = set_c.all<float>();
        for( const auto i : c_values )
        {
            ASSERT_TRUE( set_a.contains( i ) );
        }
        for( const auto i : b_values )
        {
            ASSERT_TRUE( set_c.contains( i ) );
        }
    }

}

TEST( Test_AnyValueSet, copy_and_move )
{
    AnyValueSet set_a;
    set_a.add( 42 );

    AnyValueSet set_b = set_a;
    ASSERT_TRUE( set_a.contains( 42 ) );
    ASSERT_TRUE( set_b.contains( 42 ) );

    set_a.add( 33 );
    ASSERT_TRUE( set_a.contains( 33 ) );
    ASSERT_FALSE( set_b.contains( 33 ) );

    AnyValueSet set_c = std::move(set_a);
    ASSERT_FALSE( set_a.contains( 42 ) );
    ASSERT_FALSE( set_a.contains( 33 ) );
    ASSERT_TRUE( set_a.empty() );
    ASSERT_TRUE( set_c.contains( 42 ) );
    ASSERT_TRUE( set_c.contains( 33 ) );
    ASSERT_FALSE( set_c.empty() );

}

All this is available on gist: https://gist.github.com/Klaim/10599137

\$\endgroup\$
5
+50
\$\begingroup\$

I don't see any real problem, only tidbits and things that could potentially be done differently:

  • Your header guard name is actually reserved to the implementation since it uses a double underscore.
  • Moving integer types seems useless. You will probably get even perfomance if you simply copy them.
  • You can use list initialization in the constructor initialization lists to prevent implicit narrowing type conversions. Be careful, it does not work with some special types (references for example).

    AnyValueSet( AnyValueSet&& other )
        : m_size_changed{ std::move(other.m_size_changed) }
        , m_size{ std::move(other.m_size) }
        , m_set_index{ std::move(other.m_set_index) }
    {}
    

But overall, your code seems pretty good: the style is good (indentation, variable names, redability, proper use of override to prevent surprises, etc...) and the internal logic also seems good (type erasure, use of mutable to cache values, efficient use of iterators, etc...). Therefore, I don't think that you have to worry :)


Ok, I tried to compile your code with GCC, and it seems that you actually have errors that MSVC is not able to catch:

  • typename ValueType = std::decay<T>::type actually produces an error. It seems that MSVC does not properly handles the dependant names. You need to add typename before std::decay<>.
  • I also got a warning concerning the order of initialization of the class members in your move constructor: in idiomatic code, the members should be initialized in the order they were declared. The order of initialization should be as follows:

    AnyValueSet( AnyValueSet&& other )
        : m_set_index( std::move(other.m_set_index) )
        , m_size_changed( std::move(other.m_size_changed) )
        , m_size( std::move(other.m_size) )
    {}
    
\$\endgroup\$
4
  • \$\begingroup\$ Thanks! 1. Oups! I thouht suffix double underscores were not reserved, I'll have to check in the standard. 2. My understanding is that moving integer types makes the compiler generate the same code than copying, so I was under the assumption that I wouldn't have to specialize code for these types. Do you think there would still be any benefit? 3. I'm not sure I understand your suggestion. Do you suggest using list initialization for AnyValueSet constructor? I guess a way to insert several values in one call could be helpful too, I don't have a specific case yet though. \$\endgroup\$ – Klaim Apr 17 '14 at 17:25
  • \$\begingroup\$ @Klaim I think that it generates the same code with or without std::move for integers (I'm not sure), but what I mean is that std::move(other.m_size) in your constructor does not seem useful, other.m_size would have been enough. I added an example for 3, and I forgot the word "narrowing": only implicit narrowing conversion are forbidden (for example float to int). Sometimes, a float is implicitly converted to an int and you loss precision without knowing where your error comes from. List initialization solves this problem :) \$\endgroup\$ – Morwenn Apr 17 '14 at 19:13
  • \$\begingroup\$ @Klaim Even better: list initialization forbids for example unsigned a{-1}: it catches that corner case where you have a huge number somewhere and you don't know why because of an unsigned overflow. \$\endgroup\$ – Morwenn Apr 17 '14 at 19:17
  • \$\begingroup\$ Ok I knew about narrowing in initializer expression but didn't take that into account indeed. Thanks for having tested on GCC, I'll fix these now. \$\endgroup\$ – Klaim Apr 17 '14 at 21:21

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.