Professional C++ by N. A. Solter and S.J.Kleper.Quote:
Originally Posted by alphaoide
Printable View
Professional C++ by N. A. Solter and S.J.Kleper.Quote:
Originally Posted by alphaoide
Well, make sure you understand what you read.Quote:
Originally Posted by King Mir
I have this source
Quote:
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
Linear time insetrions and deleations. Constant time access.Quote:
Originally Posted by alphaoide
Me and the link are in compleate agreement, so to speak . . .
the difference is defined in the standard. the difference is in the specified interface, and that is comprised of the methods it must support.Quote:
Originally Posted by King Mir
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
Not only that, it would not have the same complexity, nor would it follow the results given by this nice experiment page.Quote:
Originally Posted by ChaosEngine
So clearly your proposed meathod (of coping a linked list over) is not the answer I'm looking for.
Though my source doesn't say about complexity in accessing item, it says about insertion and deletion.Quote:
Originally Posted by King Mir
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)
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.Quote:
Originally Posted by King Mir
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 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. ;)
I'm pretty sure random access iterators have to guarantee constant time for access, otherwise why wouldn't a linked list implement them?Quote:
Originally Posted by alphaoide
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, egQuote:
Originally Posted by sigfriedmcwild
However, 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)Quote:
All operations on Random Access Iterators are amortized constant time
Quote:
The run-time complexity of element access is amortized constant time
A 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.Quote:
Originally Posted by Bench82
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.Quote:
Originally Posted by sigfriedmcwild
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 :)