Re: DList and SList missing length property?

[monarch_dodra]

On Tuesday, 28 May 2013 at 22:29:02 UTC, Steven Schveighoffer 
wrote:
On Tue, 28 May 2013 17:11:06 -0400, monarch_dodra 
<monarchdo...@gmail.com> wrote:

A proper implementation should be able to track length anyway: 
provide 0(1) splice, and an "amortized" 0(1) length.

I've always wondered why the standard didn't decide to do 
*that*? I think *we* should provide that...

I'm not sure how that works, can you explain/have a link?

-Steve

Well, the basic idea is to give your list an "m_size" member. 
This starts at 0. Whenever the user does a push_back/pop_back or 
whatnot operation, the the "m_size" attribute gets correctly 
upgraded. At that point, calling "size()" simply returns "m_size".

Now, once a splice operation gets called, the m_size gets reset 
to a magic value, to indicate that tracking of the size has been 
lost. Operations will seize upgrading m_size, until a call to 
size is made, at which point it will be re-calculated, once.

This, I think is the best solution, since it keeps people that 
use length in a safe position, while users of splice are also 
satisfied. Also, I *think* people who use splice tend to be more 
aware of the situation, and avoid calling length entirely. 
Implementation wise, it would mostly look like this:

template <typename T>
class list
{
    size_t m_size = 0;

    size_t push_back(T other)
    {
        //Normal Code

        if ( m_size != std::numeric_limits<size_t>::max() )
            ++m_size;
    }
    size_t splice(list::iterator first, list::iterator last)
    {
        //Normal Code

        //Reset length
        m_size == std::numeric_limits<size_t>::max();
    }

    size_t size() const
    {
        if ( m_size == std::numeric_limits<size_t>::max() )
            //Re-evaluate m_size
            m_size = std::distance( cbegin(), cend() );
        return m_size;
    }
};