Hi,

maybe this is more indicated for d.learn, but I am not sure if
it is not a bug in the documentation/implementation.

According to the phobos documentation, all containers in std.container
should provide a length property.

However it is only available for arrays.

Sure one could use the std.algorithm.count() or std.range.walkLength(), but I don't see a reason why SList and DList aren't aware of their current size.

Is this on purpose?

--
Paulo

On Tuesday, May 28, 2013 20:03:49 Paulo Pinto wrote:
> Hi,
> 
> maybe this is more indicated for d.learn, but I am not sure if it is not a bug in the documentation/implementation.
> 
> According to the phobos documentation, all containers in std.container should provide a length property.

It never says that. It lists what complexity each operation must have in order for a container to have that operation. It doesn't guarantee that any particular operation will be present on all containers (though any that's O(n) or worse is pretty much bound to be on all containers unless in does something fundamentally incompatible with a particular container's data structure).

> However it is only available for arrays.
> 
> Sure one could use the std.algorithm.count() or std.range.walkLength(),
> but I don't see a reason why SList and DList aren't aware of their
> current size.
> 
> Is this on purpose?

Yes. It's on purpose. When dealing with lists, because you can insert at any point, you have two choices:

1. Make length efficent.

2. Make splicing efficient.

If you keep track of the length, then you have to count all of the elements when you splice two lists, so splicing is O(n) instead of O(1). If you don't keep track of the length, then splicing is O(1), but then length is O(n), and length can't be O(n) per std.container's complexity requirements.

Now, that being said, I don't see a splice operation on either SList or DList (and I don't think that splicing an SList can be done in O(1) anyway), so it would appear that the implementation is optimizing for an operation that it doesn't currently support.

The same situation exists with C++'s std::list type though - size() is O(n) and splicing is O(1). However, we opted for not having containers implement inefficient operations like that (which C++ mostly did as well, but not in this case).

If you want the length of a container which doesn't have a length property, then use walkLength on its range - e.g. walkLength(container[]).

- Jonathan M Davis

Am 28.05.2013 20:16, schrieb Jonathan M Davis:
> On Tuesday, May 28, 2013 20:03:49 Paulo Pinto wrote:
>> Hi,
>>
>> maybe this is more indicated for d.learn, but I am not sure if
>> it is not a bug in the documentation/implementation.
>>
>> According to the phobos documentation, all containers in std.container
>> should provide a length property.
>
> It never says that. It lists what complexity each operation must have in order
> for a container to have that operation. It doesn't guarantee that any
> particular operation will be present on all containers (though any that's O(n)
> or worse is pretty much bound to be on all containers unless in does something
> fundamentally incompatible with a particular container's data structure).
>
>> However it is only available for arrays.
>>
>> Sure one could use the std.algorithm.count() or std.range.walkLength(),
>> but I don't see a reason why SList and DList aren't aware of their
>> current size.
>>
>> Is this on purpose?
>
> Yes. It's on purpose. When dealing with lists, because you can insert at any
> point, you have two choices:
>
> 1. Make length efficent.
>
> 2. Make splicing efficient.
>
> If you keep track of the length, then you have to count all of the elements
> when you splice two lists, so splicing is O(n) instead of O(1). If you don't
> keep track of the length, then splicing is O(1), but then length is O(n), and
> length can't be O(n) per std.container's complexity requirements.
>
> Now, that being said, I don't see a splice operation on either SList or DList
> (and I don't think that splicing an SList can be done in O(1) anyway), so it
> would appear that the implementation is optimizing for an operation that it
> doesn't currently support.
>
> The same situation exists with C++'s std::list type though - size() is O(n)
> and splicing is O(1). However, we opted for not having containers implement
> inefficient operations like that (which C++ mostly did as well, but not in this
> case).
>
> If you want the length of a container which doesn't have a length property,
> then use walkLength on its range - e.g. walkLength(container[]).
>
> - Jonathan M Davis
>

Ok, maybe the documentation should explicitly state to which containers each operation applies to.

Currently it is a bit confusing to see the complexity listed, but not finding the methods.

Thanks for the lengthy explanation, it is actually in sync with what I was thinking might be the reason.

--
Paulo

On Tuesday, 28 May 2013 at 18:16:48 UTC, Jonathan M Davis wrote:
> Now, that being said, I don't see a splice operation on either SList or DList
> (and I don't think that splicing an SList can be done in O(1) anyway), so it
> would appear that the implementation is optimizing for an operation that it
> doesn't currently support.

SList can be spliced, but the semantics are a bit more complicated. In most cases, if you need to splice, you'd use a DList anyway: SList is really for particular use cases.

I think that if splice is not in DList, it is only because it is not *yet* in DList. I have an implementation ready to submit, which adheres to Andrei's proposed container semantics. I have not yet submitted it though, because fixing DList is more important that inserting more functionality.

It's current semantics are neither value nor ref. It's... something else. My fault for inserting it when trying to fix previous clusterfuck. I've since submitted fix that gives it classic semantics, but it's kind of just sitting there...

We should *really* see to getting it (or something else) pulled through.

> The same situation exists with C++'s std::list type though - size() is O(n)
> and splicing is O(1). However, we opted for not having containers implement
> inefficient operations like that (which C++ mostly did as well, but not in this
> case).
>
> - Jonathan M Davis

That was in C++03. In C++11, length was reduced to 0(1). And splice was increased to 0(N) (I think, I don't remember the exact details, but it was definitely changed).

I'll look up the exact requirement later tonight.

On Tuesday, May 28, 2013 20:51:55 monarch_dodra wrote:
> That was in C++03. In C++11, length was reduced to 0(1). And
> splice was increased to 0(N) (I think, I don't remember the exact
> details, but it was definitely changed).

I do remember hearing something about that, though that will actually result in some nasty performance changes to some of the code out there (including code that I've written).

Regardless, you have the choice of making length O(1) or splicing O(1) and not both, and C++98/03 made splicing O(1), which I'm inclined to believe is the better choice, though having size when it's O(n) was a definite mistake on C++'s part IMHO. I hate to think of how many times I've seen programmer's write container.size() == 0 instead of empty(), particularly when size() was O(n)...

- Jonathan M Davis

On Tue, 28 May 2013 15:06:53 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Tuesday, May 28, 2013 20:51:55 monarch_dodra wrote:
>> That was in C++03. In C++11, length was reduced to 0(1). And
>> splice was increased to 0(N) (I think, I don't remember the exact
>> details, but it was definitely changed).
>
> I do remember hearing something about that, though that will actually result
> in some nasty performance changes to some of the code out there (including
> code that I've written).
>
> Regardless, you have the choice of making length O(1) or splicing O(1) and not
> both, and C++98/03 made splicing O(1), which I'm inclined to believe is the
> better choice, though having size when it's O(n) was a definite mistake on
> C++'s part IMHO. I hate to think of how many times I've seen programmer's
> write container.size() == 0 instead of empty(), particularly when size() was
> O(n)...

I actually had performance bugs the OTHER way -- I needed the length of a list, and was using .size() without realizing it was O(n).  In profiling my code, I found that std::list<T>::iterator::operator++ was the most used function, and I had no idea why for a LONG time :)

You know, it is trivial to have an O(1) splice O(n) length list wrapped into an o(n) splice O(1) length list.  All you need is to add a tracked length.  And this is a REAL pain when you have to do it manually.  There should just be two list types in <list>

-Steve

On Tuesday, 28 May 2013 at 19:24:05 UTC, Steven Schveighoffer wrote:
> On Tue, 28 May 2013 15:06:53 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:
>
>> On Tuesday, May 28, 2013 20:51:55 monarch_dodra wrote:
>>> That was in C++03. In C++11, length was reduced to 0(1). And
>>> splice was increased to 0(N) (I think, I don't remember the exact
>>> details, but it was definitely changed).
>>
>> I do remember hearing something about that, though that will actually result
>> in some nasty performance changes to some of the code out there (including
>> code that I've written).
>>
>> Regardless, you have the choice of making length O(1) or splicing O(1) and not
>> both, and C++98/03 made splicing O(1), which I'm inclined to believe is the
>> better choice, though having size when it's O(n) was a definite mistake on
>> C++'s part IMHO. I hate to think of how many times I've seen programmer's
>> write container.size() == 0 instead of empty(), particularly when size() was
>> O(n)...
>
> I actually had performance bugs the OTHER way -- I needed the length of a list, and was using .size() without realizing it was O(n).  In profiling my code, I found that std::list<T>::iterator::operator++ was the most used function, and I had no idea why for a LONG time :)
>
> You know, it is trivial to have an O(1) splice O(n) length list wrapped into an o(n) splice O(1) length list.  All you need is to add a tracked length.  And this is a REAL pain when you have to do it manually.  There should just be two list types in <list>
>
> -Steve

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...

On Tuesday, 28 May 2013 at 19:24:05 UTC, Steven Schveighoffer wrote:
> You know, it is trivial to have an O(1) splice O(n) length list wrapped into an o(n) splice O(1) length list.  All you need is to add a tracked length.  And this is a REAL pain when you have to do it manually.  There should just be two list types in <list>

I think having two lists in list would be overkill.

I *do* find the standard's choice odd though: The *primary* reason I ever use list, ever, is for its splice ability to move elements without copying them, and still having their addresses valid. No other container can do that.

I don't get why they borked list's primary strength for a function you really shouldn't be using anyway. Worst, as you say, it is easy to implement one in terms of the other... but not the other way around. By doing what they just did, they effectively closed *any* way to splice in 0(1)...

If you don't need splice, then most of the time, deque is a better choice of a container, and *that* has 0(1) length (along with a few neat properties).

All this really doesn't make sense to me.

On Tue, 28 May 2013 17:11:06 -0400, monarch_dodra <monarchdodra@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

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@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;
    }
};