Professional C++ by N. A. Solter and S.J.Kleper.Originally Posted by alphaoide
Professional C++ by N. A. Solter and S.J.Kleper.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Well, make sure you understand what you read.
I have this source
A deque [1] is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.
http://www.sgi.com/tech/stl/Deque.html
source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense
Linear time insetrions and deleations. Constant time access.
Me and the link are in compleate agreement, so to speak . . .
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
the difference is defined in the standard. the difference is in the specified interface, and that is comprised of the methods it must support.
Of course the method interfaces define more than just a function signature. They define complexity (linear, constant, etc), pre and post conditions and error handling. In reality, this narrows down the implementation fairly sharply
e.g. vector::front() returns a reference to the start of a contiguous block of memory and it's subscript operator is constant time. This pretty much means array implementation. but, technically a vendor is free to implement vector as a linked list and copy the contents to a memory block whenever front is called or cache an array of pointers to the objects to provide constant time random access. It would be a slow crap implementation, but it would be standard-compliant.
edit: in fact, the standard library isn't really that standard at all. vendors are allowed to add extra parameters to methods and templates! http://www.gotw.ca/gotw/064.htm
Last edited by ChaosEngine; 05-07-2006 at 11:13 PM.
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore.Want to add some scripting to your App?
Not only that, it would not have the same complexity, nor would it follow the results given by this nice experiment page.
So clearly your proposed meathod (of coping a linked list over) is not the answer I'm looking for.
It is too clear and so it is hard to see.
A dunce once searched for fire with a lighted lantern.
Had he known what fire was,
He could have cooked his rice much sooner.
Though my source doesn't say about complexity in accessing item, it says about insertion and deletion.
Similarly, for insertion. Anyway, I'll let someone else put another view on this tomorrow.Code:Deletion operation = Accessing item + Deleting the item O(N) = O(N) + O(1)
source: compsci textbooks, cboard.cprogramming.com, world wide web, common sense
I wasn't really suggesting that! that was just a "lets take the most ridiculous implementation possible and torture it into meeting the requirements" exercise.
My point was that, as long as you match the given specifications for complexity (which, fair enough, my example failed to do) and interface the internals are up to the vendor. To take a much more realistic example, a vector can cache it's size or calculate it on calls to size().
"I saw a sign that said 'Drink Canada Dry', so I started"
-- Brendan Behan
Free Compiler: Visual C++ 2005 Express
If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore.
I would imagine a deque is a wrapper for an array (as someone else said - a bit like an overloaded vector) - since appending to the 'front' of an array would use exactly the same process as appending to the 'back'. Maybe this site will help: http://www.sgi.com/tech/stl/Deque.html
Due to the way templated code is handled by most compilers, the code is probably not hidden in any sort of precompiled library. Just open up the deque header file and look at it, it's there for you to see in all its wondrous glory. It will show you everything you want to know in excrutiating detail. It's then just a matter of translating that into English (...or whatever language you speak) which may be quite difficult depending on your level of expertice in the matter.
P.S. Don't ask me for any translation, I don't care, that's the beauty of the STL; as long as it works correctly and efficiently the internal workings don't matter. It's just that if you really want to know how it is implemented then the code is right there in front of you to look at.
"Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
-Christopher Hitchens
I'm pretty sure random access iterators have to guarantee constant time for access, otherwise why wouldn't a linked list implement them?
That's not the same thing. iterators are abstractions of pointers - the random access refers to the ability to access elements by index : ie, You can access an vector/deque directly by using an index, egHowever, linked lists do not have this ability, because there are no indexes in linked lists.Code:std::vector<int> foo; foo.push_back(5); foo.push_back(6); foo.push_back(8); int a = foo.at(1);
Again from the SGI STL reference (http://www.sgi.com/tech/stl/ )
and for Random access containers (those that provide random access iterators)All operations on Random Access Iterators are amortized constant time
The run-time complexity of element access is amortized constant timeA list is an ordered container, thus all elements have an index which is their position in their container. If the only requirement for random access was the ability to access elements by index a list could do so by iterating over the elements the right number of times.
Last edited by sigfriedmcwild; 05-08-2006 at 09:23 AM.
That isn't access in constant time - because the further into the list, the longer it takes to iterate through and find that element in the list. On the other hand, a vector or deque takes the same amount of time to access any element by index regardless of its position, because you can jump straight to it, and not have to iterate through the rest of the container.
Which is exactly what I was saying isn't it?
Sorry, I think I might have lost track of "who said what" in this thread
