Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Consider replacing Vector and Deque with Sequence as a class (not an interface) #45

rtheunissen opened this issue Aug 30, 2016 · 6 comments


Copy link

rtheunissen commented Aug 30, 2016

The differences between Deque and Vector might be considered small enough to consider removing Vector and Sequence, and rename Deque to Sequence.

Advantages of Deque:

  • O(1) unshift and shift

Advantages of Vector:

  • 1.5x growth factor yields less average memory used than Deque's 2.0x
  • Slightly faster access time due to not having to translate into the buffer.

Sequence is also the only interface below Collection.

The important question is: is it clear enough when you would use one over the other?

Copy link

castarco commented Oct 8, 2016

I think that these two classes should remain separated. Maybe the documentation should include two well defined usage cases in order to make easier to programmers choose which class to pick .

Copy link
Member Author

rtheunissen commented Oct 9, 2016

@castarco why do you think they should remain separated?

Copy link

castarco commented Oct 13, 2016

Hi @rtheunissen , mainly because it's very interesting to keep the advantages of both data structures.

If the programmer knows in advance that the container won't be resized, or that the resize will be done only due to append operations (and NOT prepend ops)... then it should be crystal clear that Vector is the correct choice (over Deque or even over the native PHP "array").

There is no need to justify the Deque existence because it's more flexible than Vector, but maybe the programmers should know at which price. It's a good thing to allow the programmers to exploit this "forgotten" knowledge and optimize their programs.

Copy link
Member Author

rtheunissen commented Oct 13, 2016

@castarco I completely agree that it's ideal to keep the advantages of both structures, but I believe that the overhead of having two structures that are practically identical outweighs those benefits.

The minor differences between them are that a Vector is very slightly faster to access and modify at the end of the sequence (but has the same complexity as Deque), and the growth factor is 1.5 vs Deque's 2.0. But a Deque has a significant advantage offering O(1) ops at the front of the sequence. That to me is enough to make Deque the default, thereby making Vector practically redundant.

Keep in mind that this is with the introduction of Tuple (think SplFixedArray but better), which would consume some of the use cases where you might have used Vector. This would be where growth is not expected, or in read-only contexts.

See #52

Copy link

castarco commented Oct 15, 2016

Hum, it's true that a Tuple type will cover more than the 50% of the Vector class use cases.

Copy link
Member Author

rtheunissen commented Oct 17, 2018

Sequence should still be an interface, and will remain so in 2.0

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet

No branches or pull requests

2 participants