8
\$\begingroup\$

I made a C++ container of an ordered list of integers, that, in order to save space, I save as ranges:

For example, the list \$ \{1,2,3,5,6,7,8,9,20\} \$ is saved in memory as \$ \{(1,3), (5,9), (20,20)\} \$.

I have doubts of the iterator used to show all the numbers that are include on one list is right. Mainly because my iterator doesn't allow to modify elements on the container.

And in general, I wrote it in C++11.

template<typename T,
         typename = typename std::enable_if<std::is_integral<T>::value>::type>
class RangeListIterator; // undefined

template<typename T>
class RangeListIterator<T>{
public:
    using value_type = T;
    using RangeItem = std::pair< value_type, value_type >;
    using RangeItemList = std::list<RangeItem>;
    using RangeItem_iterator = typename RangeItemList::iterator;

    RangeListIterator( RangeItem_iterator it, value_type val,
                       RangeItem_iterator itEnd );

    bool operator!=( const RangeListIterator<T> & b ) const;

    RangeListIterator& operator++();
    RangeListIterator operator++( int );

    const value_type& operator*() const;

private:
    RangeItem_iterator m_listIt;
    RangeItem_iterator m_listEnd;
    value_type m_val;
};

template<typename T>
RangeListIterator<T>::RangeListIterator( RangeItem_iterator it,
                                         value_type val,
                                         RangeItem_iterator itEnd)
    : m_listIt{ it }, m_listEnd{ itEnd }, m_val{ val }
{
    // empty
}

template<typename T>
bool RangeListIterator<T>::operator!=( const RangeListIterator<T> & b ) const{
    return (m_listIt != b.m_listIt) or (m_val != b.m_val);
}

template<typename T>
RangeListIterator<T>& RangeListIterator<T>::operator++() {
    if( m_val == std::numeric_limits<T>::max() ){
        ++m_listIt;
        m_val = 0;
    }else{
        ++m_val;
        if( m_val > m_listIt->second ){
            ++m_listIt;
            if( m_listIt == m_listEnd ){
                m_val = 0;
            }else{
                m_val = m_listIt->first;
            }
        }
    }

    return *this;
}

template<typename T>
RangeListIterator<T> RangeListIterator<T>::operator++( int ) {
    auto temp = *this;
    ++*this;
    return temp;
}

template<typename T>
const typename RangeListIterator<T>::value_type&
RangeListIterator<T>::operator*() const{
    return m_val;
}

template<typename T,
         typename = typename std::enable_if<std::is_integral<T>::value>::type>
class RangeList; // undefined

template<typename T>
class RangeList<T>{
public:
    using value_type = T;
    using RangeItem = std::pair< value_type, value_type >;
    using RangeItemList = std::list<RangeItem>;
    using RangeItem_iterator = typename RangeItemList::iterator;
    using RangeItem_const_iterator = typename RangeItemList::const_iterator;
    using iterator = RangeListIterator<T>;

    void insert( const value_type val );
    void remove( const value_type val );
    bool contains( const value_type val ) const;

    RangeItem_iterator beginItem();
    RangeItem_const_iterator beginItem() const;

    RangeItem_iterator endItem();
    RangeItem_const_iterator endItem() const;

    iterator begin();
    iterator end();

private:
    std::list<RangeItem> m_items;
};

template<typename T>
void RangeList<T>::insert( const T val ){
    for( auto it = std::begin(m_items) ; it != std::end(m_items) ; ++it ){
        if( val < it->first ){
            if( val == (it->first - 1) ){
                it->first = val;
            }else{
                m_items.emplace( it, std::make_pair( val, val ) );
            }
            return;
        }else if( val <= it->second ){
            return;
        }else if( val == (it->second + 1) ){
        auto next = std::next(it);
            if( next != std::end(m_items) ){
                if( (val >= next->first - 1) and (val <= next->second) ){
                    it->second = next->second;
                    m_items.erase( next );
                    return;
                }
            }
            it->second = val;
            return;
        }
    }

    m_items.emplace_back( std::make_pair( val, val ) );
}

template<typename T>
void RangeList<T>::remove( const T val ){
    for( auto it = std::begin(m_items) ; it != std::end(m_items) ; ++it ){
        if( val >= it->first and val <= it->second ){
            if( it->first == it->second ){
                m_items.erase( it );
                return;
            }
            if( val == it->first ){
                it->first = it->first + 1;
                return;
            }
            if( val == it->second ){
                it->second = it->second - 1;
                return;
            }
            m_items.emplace( it, std::make_pair( it->first, val - 1 ) );
            it->first = val + 1;
            return;
        }
        if( val < it->first ){
            return;
        }
    }
}

template<typename T>
bool RangeList<T>::contains( const T val ) const{
    for( const auto & it: m_items ){
        auto rmin = it.first <= val;
        if( rmin and (it.second >= val) ){
            return true;
        }
        if( not rmin ){
            return false;
        }
    }

    return false;
}

template<typename T>
inline
typename RangeList<T>::RangeItem_iterator
RangeList<T>::beginItem(){
    return m_items.begin();
}

template<typename T>
inline
typename RangeList<T>::RangeItem_const_iterator
RangeList<T>::beginItem() const{
    return m_items.begin();
}

template<typename T>
inline
typename RangeList<T>::RangeItem_iterator
RangeList<T>::endItem(){
    return m_items.end();
}

template<typename T>
inline
typename RangeList<T>::RangeItem_const_iterator
RangeList<T>::endItem() const{
    return m_items.end();
}

template<typename T>
typename RangeList<T>::iterator
RangeList<T>::begin(){
    auto listIt = std::begin(m_items);
    return RangeListIterator<T>( listIt, listIt->first, std::end(m_items) );
}

template<typename T>
inline
typename RangeList<T>::iterator
RangeList<T>::end(){
    return RangeListIterator<T>( std::end(m_items), 0, std::end(m_items) );
}

An example of use:

RangeList<int> range;

range.insert( 1 );
range.insert( 2 );
range.insert( 4 );
range.insert( 7 );
range.insert( 8 );
range.insert( 6 );

for( int i = 0 ; i < 10 ; ++i ){
    cout << " test " << i << " = " << range.contains(i) << endl;
}

for( auto it = range.beginItem() ; it != range.endItem() ; ++it ){
    cout << " range (" << it->first << " , " << it->second << ")" << endl;
}

for( auto v: range ){
    cout << " val " << v << endl;
}

RangeList<unsigned int> rangeu;

rangeu.insert( 4 );
rangeu.insert( 7 );
rangeu.insert( 1 );
rangeu.insert( 2 );
rangeu.insert( 0 );
rangeu.insert( -1 );
rangeu.insert( -2 );
rangeu.insert( 6 );

for( int i = 0 ; i < 10 ; ++i ){
    cout << " test " << i << " " << rangeu.contains(i) << endl;
}

for( auto it = rangeu.beginItem() ; it != rangeu.endItem() ; ++it ){
    cout << " range (" << it->first << " , " << it->second << ")" << endl;
}

for( auto v: rangeu ){
    cout << " val " << v << endl;
}

return 0;

UPDATED:

  1. Fixed insert. Now it merges two continuous ranges when you insert the element between them. E.g: \$ \{(1,3),(5,9)\} + insert(4) \$ generates \$ \{(1,9)\} \$.

  2. Added remove method.

\$\endgroup\$
  • 1
    \$\begingroup\$ If the iterator is not there to change the contents of the container then just make it a const iterator. \$\endgroup\$ – Nobody Apr 9 '14 at 17:17
  • \$\begingroup\$ You don't need the inline keywords, especially in a header file. \$\endgroup\$ – Jamal Apr 9 '14 at 17:32
  • \$\begingroup\$ Also, I can think a way without saving the end on the iterator. \$\endgroup\$ – Zhen Apr 9 '14 at 20:21
  • \$\begingroup\$ @Jamal I don't think so. Maybe you are thinking on definitions inside class declaration. \$\endgroup\$ – Zhen Apr 9 '14 at 20:24
  • \$\begingroup\$ I think it may be easier to represent the list with ranges that don't include the length. ie. {[1,4),[5,10),[20,21)} I hope my math notation is correct. \$\endgroup\$ – Martin York Apr 9 '14 at 20:58
5
\$\begingroup\$

A fairly minor point, but I'm not a huge fan of using enable_if here. For example, if we declare a RangeList<double>, we'll get the following as errors:

range_iter.cpp: In function 'int main()':

range_iter.cpp:53:21: error: no type named 'type' in 'struct std::enable_if' RangeList double_range;

range_iter.cpp:53:21: error: template argument 2 is invalid

range_iter.cpp:53:35: error: invalid type in declaration before ';' token RangeList double_range;

This also requires adding "clutter" like:

template<typename T,
         typename = typename std::enable_if<std::is_integral<T>::value>::type>
class RangeListIterator; // undefined

template<typename T,
         typename = typename std::enable_if<std::is_integral<T>::value>::type>
class RangeList; // undefined

Instead, I'd rather just use a static_assert at the top of each class:

static_assert(std::is_integral<T>::value, "T must be an integral type!");

This has the benefit of cutting down on the above clutter, as well as giving nicer compiler error messages:

range_iter.hpp: In instantiation of 'class RangeList':

range_iter.cpp:53:23: required from here

range_iter.hpp:92:5: error: static assertion failed: T must be an integral type! static_assert(std::is_integral::value, "T must be an integral type!");

\$\endgroup\$
  • \$\begingroup\$ Great, I like it, \$\endgroup\$ – Zhen Apr 10 '14 at 9:18
2
\$\begingroup\$

Depending on your setting, a bitvector might be a much better idea (or much worse!). This depends on how sparse your ranges actually are. The following might give you some ideas, and perhaps you might want to incorporate it into your data structure, and use some method to change the internal representation if needed.

const static std::size_t S = 128; 
std::bitset<S> range; // We can now store 128 values using only 128 bits

// Is 5 present?
bool five = range.test(4);

... and so on. You can support many operations in constant time. If you know how large S can be beforehand, great. If not, use a dynamic variant, such as boost::dynamic_bitset.

\$\endgroup\$
  • \$\begingroup\$ Good to know I can use bitset, but in my problem the number of elements are thousands to hundreds of thousands, and fairly dense. \$\endgroup\$ – Zhen Apr 10 '14 at 14:34

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.