Specialization for LinkedList::extend

[udoprog]

Hey,

I’m currently looking into implementing some specialized* SpecExtend impl’s for LinkedList. *: https://github.com/rust-lang/rfcs/blob/master/text/1210-impl-specialization.md

What I’ve noticed and would like to check is: It’s currently only reasonable to implement specialization for iterator types which are defined in the same module.

For LinkedList, it’s conceivable that extend on DrainFilter would just relink the nodes drained from the iterator onto the list it’s being extended onto.

For linked_list::IntoIter, we can simply relink the end of one list to the beginning of another (which is really neat!).

But for the more exotic scenarios like:

list1.extend(list2.into_iter().skip_while(...).filter(...))

The type of this iterator wouldn’t match any of the specialized impls. At least as far as I’m able to express them.

Is this the case? If so, is it still worthwhile specializing some of the SpecExtend impl’s where possible?

[matklad]

Hm, is it worth the effort to specialize LinkedList though? My understanding is that it almost never a good idea to use LinkedList…

[bluss]

In a way the answer is simple: It’s not possible to specialize those meaningfully, because the implementation of filter is private to you (it’s in a different crate, core; not alloc). I don’t think it’s that important to try to do either.

[udoprog]

I say yes - while we still have LinkedList in stdlib. It would be a shame not to have it the best that it can be. If only to be able to run future benchmarks to establish exactly how bad it is.

But even for the sake of argument. I’m still interested in your view of specialization of this kind in general.

[udoprog]

Yes. I agree with this in the current state of things. Thanks for the validation.

In practice it seems like iterators could be taught to emit the node somehow for this case. But possibly not without having a large impact on the generic iterator types.

[scottmcm]

What if there were something like .into_nodes_iter(): Iterator<Item=Node<T>> on LinkedList? The public Node<T> could deref to T, but there would also be LinkedList<T>: FromIterator<Node<T>> that does the efficient no-node-reallocation collection. (And specializes if passed a NodesIter directly to just take the whole linked list in O(1).)

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.