5 ms·

No, std::deque has O(n) space overhead... the goal here is to get that to O(sqrt(n)), and in the worst case too.

MichaelMoser123 9y ago
std::deque has the following constraints * Random access - constant O(1) * Insertion or removal of elements at the end or beginning - constant O(1) * Insertion or removal of elements - linear O(n) Also in glibc/libstdc++ it is one https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015...
- wfunction 9y ago
  O(n) in my comment refers to space overhead. You're talking about time.
  - MichaelMoser123 9y ago
    [1] does not mention a linear space requirement, it mentions O(1) time for random access and removal of elements. Both major implementations implement std::deque in this way libstdc++ [2] and libc++ [3], but you say it can't be so. Well well. [1] http://en.cppreference.com/w/cpp/container/deque http://en.cppreference.com/w/cpp/container/deque [2] https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015... [3] https://github.com/llvm-mirror/libcxx/blob/master/include/deque https://github.com/llvm-mirror/libcxx/blob/master/include/de...
    - wfunction 9y ago
      I don't get what you're arguing against, if anything. Can you make an actual claim and tell me where I'm wrong? Literally all I've been saying so far is that std::deque does not meet the O(sqrt n) space overhead of compact dynamic arrays. i.e.: yes it is more exotic than a mere std::deque, which is precisely the question you were asking and I was answering initially. So you're saying I'm wrong, or what? If you're saying I'm wrong, which implementation of std::deque do you think meets that overhead spec?
      - MichaelMoser123 9y ago
        "No, std::deque has O(n) space overhead... the goal here is to get that to O(sqrt(n))," implies that compact dynamic array can't be used for std::deque, when it is used as such, also I did not find a source that states this space requirement for std::deque in the first place.
        wfunction 9y ago
        ...you were asking what's so "exotic" about compact dynamic arrays if they're just deques? I'm telling you they're not deques, because they have additional constraints that deques don't have. Are you intentionally twisting this backwards or something? You're basically turning the conversation into something like this: You: "Penguins are birds, right? What's so exotic about penguins when I see all these birds flying around me?" Me: "Penguins live in Antarctica... and don't fly... (hence why people find them exotic...)" You: "But who says birds can't live in Antarctica?? And chickens can't fly either. And penguins are birds. So what's so exotic about penguins?" Me: {what sane response can I even give you here?!} ________________________________________ But anyway... > implies that compact dynamic array can't be used for std::deque, when it is used as such To entertain your new argument here: Deque requires references to existing elements not to be invalidated when new elements are appended. I don't know how compact dynamic arrays work, but dynamic arrays generally move elements around in memory while maintaining guaranteed worst-case O(1)-time access to them, so it seems kind of impossible for them to meet both requirements.
        MichaelMoser123 9y ago
        Where, where does it say that std::deque is supposed to have O(sqrt(n)) space requirement as worst case?
        wfunction 9y ago
        > Where, where does it say that std::deque is supposed to have O(sqrt(n)) space requirement as worst case? Nowhere! Where did I even claim it said that anywhere?!
mnarayan01 9y ago
Where are you getting O(sqrt(n)) space from? The linked article says O(n) for compact dynamic arrays.
- wuch 9y ago
  Note that the original article describes space complexity as "N + O(sqrt N)", i.e., there are N records and O(sqrt N) extra space. Their data structure is considerably more complex than traditional implementations of std::deque, I wonder if it is actually of any practical interest.

std::deque has the following constraints * Random access - constant O(1) * Insertion or removal of elements at the end or beginning - constant O(1) * Insertion or removal of elements - linear O(n) Also in glibc/libstdc++ it is one https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015...

wfunction 9y ago
O(n) in my comment refers to space overhead. You're talking about time.
- MichaelMoser123 9y ago
  [1] does not mention a linear space requirement, it mentions O(1) time for random access and removal of elements. Both major implementations implement std::deque in this way libstdc++ [2] and libc++ [3], but you say it can't be so. Well well. [1] http://en.cppreference.com/w/cpp/container/deque http://en.cppreference.com/w/cpp/container/deque [2] https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01503_source.html https://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a015... [3] https://github.com/llvm-mirror/libcxx/blob/master/include/deque https://github.com/llvm-mirror/libcxx/blob/master/include/de...
  - wfunction 9y ago
    I don't get what you're arguing against, if anything. Can you make an actual claim and tell me where I'm wrong? Literally all I've been saying so far is that std::deque does not meet the O(sqrt n) space overhead of compact dynamic arrays. i.e.: yes it is more exotic than a mere std::deque, which is precisely the question you were asking and I was answering initially. So you're saying I'm wrong, or what? If you're saying I'm wrong, which implementation of std::deque do you think meets that overhead spec?
    - MichaelMoser123 9y ago
      "No, std::deque has O(n) space overhead... the goal here is to get that to O(sqrt(n))," implies that compact dynamic array can't be used for std::deque, when it is used as such, also I did not find a source that states this space requirement for std::deque in the first place.
      - wfunction 9y ago
        ...you were asking what's so "exotic" about compact dynamic arrays if they're just deques? I'm telling you they're not deques, because they have additional constraints that deques don't have. Are you intentionally twisting this backwards or something? You're basically turning the conversation into something like this: You: "Penguins are birds, right? What's so exotic about penguins when I see all these birds flying around me?" Me: "Penguins live in Antarctica... and don't fly... (hence why people find them exotic...)" You: "But who says birds can't live in Antarctica?? And chickens can't fly either. And penguins are birds. So what's so exotic about penguins?" Me: {what sane response can I even give you here?!} ________________________________________ But anyway... > implies that compact dynamic array can't be used for std::deque, when it is used as such To entertain your new argument here: Deque requires references to existing elements not to be invalidated when new elements are appended. I don't know how compact dynamic arrays work, but dynamic arrays generally move elements around in memory while maintaining guaranteed worst-case O(1)-time access to them, so it seems kind of impossible for them to meet both requirements.
        MichaelMoser123 9y ago
        Where, where does it say that std::deque is supposed to have O(sqrt(n)) space requirement as worst case?
        wfunction 9y ago
        > Where, where does it say that std::deque is supposed to have O(sqrt(n)) space requirement as worst case? Nowhere! Where did I even claim it said that anywhere?!

mnarayan01 9y ago

Where are you getting O(sqrt(n)) space from? The linked article says O(n) for compact dynamic arrays.

wuch 9y ago
Note that the original article describes space complexity as "N + O(sqrt N)", i.e., there are N records and O(sqrt N) extra space. Their data structure is considerably more complex than traditional implementations of std::deque, I wonder if it is actually of any practical interest.