deque push_front, how it actually works?
Hi, I am learning about deques and their operations, and on push_front() and I am pretty sure I know how it works but just want to make 100% sure.
So i learnt that in a deque there is a array/vector normally called map that keeps track basically of the rest of the arrays/vectors which hold the actual data.
My question is, when push_front() is called, the element is added to the first vector/array if there is space for it. If it is added, does the thing in the map that keeps track of the array/vector of elements just then point to that newly added element? since it is now the first element. There is no shuffling of data etc?
Also how does map hold the data for these arrays, is it a pointer? I said point above, but not sure if that was right.
So i learnt that in a deque there is a array/vector normally called map that keeps track basically of the rest of the arrays/vectors which hold the actual data.
My question is, when push_front() is called, the element is added to the first vector/array if there is space for it. If it is added, does the thing in the map that keeps track of the array/vector of elements just then point to that newly added element? since it is now the first element. There is no shuffling of data etc?
Also how does map hold the data for these arrays, is it a pointer? I said point above, but not sure if that was right.
Did you look at:
https://en.cppreference.com/w/cpp/container/deque
http://www.cplusplus.com/reference/deque/deque/
Lets say that deque has collection of arrays. If the current front array is full, then a new (fixed-size) array is allocated, the new data element is put at the end of that array and the array is added to the front of the collection.
Insert and erase do shuffle, even worse than vector. The push/pop front/back do not shuffle elements.
https://en.cppreference.com/w/cpp/container/deque
http://www.cplusplus.com/reference/deque/deque/
Lets say that deque has collection of arrays. If the current front array is full, then a new (fixed-size) array is allocated, the new data element is put at the end of that array and the array is added to the front of the collection.
Insert and erase do shuffle, even worse than vector. The push/pop front/back do not shuffle elements.
While not a complete answer directly, more generally it should be said that most of the containers do not specifiy exactly how the underlying storage mechanism works. The specification is about the interface of the container and how it should behave. Each implementation is free to interpret that independently, so the specifics may differ from one implementation to another.
We can assume that vector is fairly predictable about what happens inside that container.
Map, on the other hand, may be implemented as a red-black tree, but there's no actual requirement of that. There are a few other trees they might use.
deque's push_front method is specified for an expected behavior specification (it can't behave as badly as a vector on push_front, but not as well as a list).
I'd argue that you might think of a deque as a collection of vectors of fairly limited size, so that expansion of the deque at either end doesn't require as much reorganization as a vector. The underlying storage mechanism need not be pointers, as in raw pointers, but could merely be indexed integers or iterators to the proper position in the sub-container at the front (or back). I might assume, without evidence, that a push front may, on the first push, open a new sub-container, but place the "beginning" of that container near the middle of the sub-container, so that push front or back is similarly efficient (for a while). That may be wasteful under certain circumstances, but I'd reason that if there are no push_fronts, there may never be, but once a push front is used I'd assume there would be more. I may implement the container assuming wasted storage is acceptable (the other containers are known to), but that may be undesirable in many use cases.
The strategies of a particular container may be so different from one implementation to another that even as versions of a particular library change over time, the implementation may differ as new observed behaviors lead to engineering improvements.
The very reason we trust these containers, from reputable sources, is that we assume the developers are testing, evaluating and improving their performance for their intended features, wherever that is possible, whereas we would never have much time to focus on that unless a very specific circumstance warranted it.
While there is immense curiosity on the point, and it is the science of algorithms and data structures (which everyone doing this stuff should study, as apparently you are), I would say that study should be independent of the curiosity associated with using the library.
It's kind of the "if you have to ask" category of questions, in a sense.
Those of us starting the study of C++ in the 80's, when it was new, and then in the early 90's, when templates were first fashioned, responded to templates specifically by creating containers and smart pointers. There were some really awful implementations which made all of the mistakes that can be made, even as the containers themselves generally worked. Smart pointers in particular (a container of 1) were so widely produced that I dare say thousands if not tens of thousands of implementations could be cataloged if some historian were interested to do so.
When HP first made news with the stl, it was an expected "shock" of sorts, and, of course, few of the compilers available could actually build it.
If you really want to understand the mechanics of the deque, you'll need to exit (temporarily) the curiosity over the std library's deque, and pull open some texts on the subject in algorithms and data structures, where you'd be treated to a series of experimental and some rather primitive implementations on the way to recognizing just what engineering goes into them, and what particular performance characteristics might be prioritized. A deque need not behave exactly as the std library's version does, and you'd gain that insight by diving in to that area of computer science. Of course, the deque isn't the first you'd encounter, so you might be in for a bit of a climb, but it is worth it.
We can assume that vector is fairly predictable about what happens inside that container.
Map, on the other hand, may be implemented as a red-black tree, but there's no actual requirement of that. There are a few other trees they might use.
deque's push_front method is specified for an expected behavior specification (it can't behave as badly as a vector on push_front, but not as well as a list).
I'd argue that you might think of a deque as a collection of vectors of fairly limited size, so that expansion of the deque at either end doesn't require as much reorganization as a vector. The underlying storage mechanism need not be pointers, as in raw pointers, but could merely be indexed integers or iterators to the proper position in the sub-container at the front (or back). I might assume, without evidence, that a push front may, on the first push, open a new sub-container, but place the "beginning" of that container near the middle of the sub-container, so that push front or back is similarly efficient (for a while). That may be wasteful under certain circumstances, but I'd reason that if there are no push_fronts, there may never be, but once a push front is used I'd assume there would be more. I may implement the container assuming wasted storage is acceptable (the other containers are known to), but that may be undesirable in many use cases.
The strategies of a particular container may be so different from one implementation to another that even as versions of a particular library change over time, the implementation may differ as new observed behaviors lead to engineering improvements.
The very reason we trust these containers, from reputable sources, is that we assume the developers are testing, evaluating and improving their performance for their intended features, wherever that is possible, whereas we would never have much time to focus on that unless a very specific circumstance warranted it.
While there is immense curiosity on the point, and it is the science of algorithms and data structures (which everyone doing this stuff should study, as apparently you are), I would say that study should be independent of the curiosity associated with using the library.
It's kind of the "if you have to ask" category of questions, in a sense.
Those of us starting the study of C++ in the 80's, when it was new, and then in the early 90's, when templates were first fashioned, responded to templates specifically by creating containers and smart pointers. There were some really awful implementations which made all of the mistakes that can be made, even as the containers themselves generally worked. Smart pointers in particular (a container of 1) were so widely produced that I dare say thousands if not tens of thousands of implementations could be cataloged if some historian were interested to do so.
When HP first made news with the stl, it was an expected "shock" of sorts, and, of course, few of the compilers available could actually build it.
If you really want to understand the mechanics of the deque, you'll need to exit (temporarily) the curiosity over the std library's deque, and pull open some texts on the subject in algorithms and data structures, where you'd be treated to a series of experimental and some rather primitive implementations on the way to recognizing just what engineering goes into them, and what particular performance characteristics might be prioritized. A deque need not behave exactly as the std library's version does, and you'd gain that insight by diving in to that area of computer science. Of course, the deque isn't the first you'd encounter, so you might be in for a bit of a climb, but it is worth it.
Topic archived. No new replies allowed.