#6 Ammortized O(1) size() complexity for list and slist

closed
None
5
2009-06-03
2008-04-04
No

Hi,

I have a suggestion to optimize the size() method of list and slist containers. The current complexity is linear (O(n)) which is rather expensive in many cases. The complexity follows from the constant time complexity requirement on splice() methods.

I propose to add two private members of the container:
1. The size value. Let it be mutable size_type m_Size.
2. The boolean value that shows that m_Size is valid. mutable bool m_SizeIsValid.

The m_Size member holds the current size of the container. It gets incremented when an element is inserted and decremented when an element is erased. If the container constructed from a sequence of elements, m_Size is initialized with the number of those elements. It gets swapped in swap() and copied in assignment and copy constructor. It is not changed in any other methods, including splice.

The m_SizeIsValid member is true after the container construction and is not changed up until splice. In splice methods the m_SizeIsValid members of the two containers are set to false.

The size() method of the container could be implemented like this:

size_type size() const
{
if (!m_SizeIsValid)
{
m_Size = distance(begin(), end());
m_SizeIsValid = true;
}
return m_Size;
}

PROs:
- We get the constant time (O(1)) size() complexity up until we use splice(). Only first size() after splice() has linear complexity.
- The splice() stays constant time, as required

CONs:
- list and slist object size increases
- Minor overhead (a mere increment/decrement per element) is added to insertion/erasure methods

IMHO, the benefits of the improvement outweight the drawbacks by far. But just in case if it is critical to someone, the described optimization could be made optional, just like the short string optimization is.

I think, this could be a nice addition to 5.2.0.

Discussion

  • Petr Ovtchenkov

    Petr Ovtchenkov - 2009-06-03

    Very contradictory idea. It discussed many times. IMO drabacks are stronger then benefits (even overall performance shouldn't changed: ++sz done n times once or n times on every add/remove operation). Conclusion: this design prinsiple remains unchanged.

     
  • Petr Ovtchenkov

    Petr Ovtchenkov - 2009-06-03
    • assigned_to: nobody --> complement
    • status: open --> closed
     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks