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 
> <monarchdodra at 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;
     }
};