StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>"(a) How is the link between A and D established. In other words, how does A access components of D? Give examples."</p> <p>It is done through iterators. Iterators are the glue between algorithms and data structures in STL. I will use c++11 for my example:</p> <pre><code>std::vector<int> vec{1, 5, 3, 4}; std::list<int> l{1, 4, 8, 3}; auto foundInVecItem = std::find(vec.begin(), vec.end(), 3); //Note: same algorithm used for different data structure. auto foundInVecItem = std::find(l.begin(), l.end(), 3); </code></pre> <p>This works because <code>std::find</code> makes no assumptions about the data structure that is using for the search. It uses the <code>ForwardIterator</code> concept for its implementation. You can take a look at iterator categories <a href="http://en.cppreference.com/w/cpp/iterator" rel="nofollow">here</a>.</p> <p><code>std::find</code> could be implemented something (simplified since it's just for learning) like this:</p> <pre><code>template <class ForwardIterator> ForwardIterator find(ForwardIterator b, ForwardIterator e, typename ForwardIterator::value_type v) { while (b != e) { if (*b == v) { return b; } } return e; </code></pre> <p>}</p> <p>The important point here is that the iterator interface is being used to access elements of <code>std::list</code> or <code>std::vector</code> so the algorithm doesn't care about the data structure as long as they provide <code>ForwardIterator</code>s.</p> <p>"(b) The STL guarantees (i.e., promises) something about the result of using A with D. What is the guarantee?"</p> <p>Sorry, this is too general, what do you mean by that question? If you mean about the big O notation, namely, asymptotic computational cost, yes. The standard promises a bounded big O cost for each algorithm given a data structure. It depends on the algorithm and the data structure. For example <code>std::advance</code>, which advances an iterator a number of steps, is guaranteed to be <code>O(1)</code> for <code>RandomAccessIterator</code>s and <code>O(n)</code> for the rest of them.</p> <p>"A) The STL also provides various "iterators" to access elements on the data structures. There are various types of Iterators, they can travel linearly from the start to the end, some can travel in both directions, and some can move freely to any element in D. The type of iterator supported by D will determine the type of A that can be run using D. "</p> <p>You can take a look at iterator categories <a href="http://en.cppreference.com/w/cpp/iterator" rel="nofollow">here</a>.</p> <p>"B) If A can be run on D then the STL guarantees the time-complexity (O(n)) that it will take to complete the A."</p> <p>Yes, that's right. The specification guarantees the asymptotic computational cost of an operation given a data structure.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload