theory - How dose an algorithm access components of a Data structure in STL -

the standard template library (stl) provides data structures , algorithms. however, not case every algorithm can used every data structure. suppose stl supports use of algorithm data structure d.

(a) how link between , d established. in other words, how access components of d? give examples.

(b) stl guarantees (i.e., promises) result of using d. guarantee?

---

a) stl provides various "iterators" access elements on data structures. there various types of iterators, can travel linearly start end, can travel in both directions, , can move freely element in d. type of iterator supported d determine type of can run using d.

b) if can run on d stl guarantees time-complexity (o(n)) take complete a.

hello! studying theory exam. wondering if think missed in answers here.

"(a) how link between , d established. in other words, how access components of d? give examples."

it done through iterators. iterators glue between algorithms , data structures in stl. use c++11 example:

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 different data structure. auto foundinvecitem = std::find(l.begin(), l.end(), 3); 

this works because std::find makes no assumptions data structure using search. uses forwarditerator concept implementation. can take @ iterator categories here.

std::find implemented (simplified since it's learning) this:

template <class forwarditerator> forwarditerator find(forwarditerator b, forwarditerator e,                     typename forwarditerator::value_type v) {     while (b != e) {       if (*b == v) {         return b;       }     }     return e; 

}

the important point here iterator interface being used access elements of std::list or std::vector algorithm doesn't care data structure long provide forwarditerators.

"(b) stl guarantees (i.e., promises) result of using d. guarantee?"

sorry, general, mean question? if mean big o notation, namely, asymptotic computational cost, yes. standard promises bounded big o cost each algorithm given data structure. depends on algorithm , data structure. example std::advance, advances iterator number of steps, guaranteed o(1) randomaccessiterators , o(n) rest of them.

"a) stl provides various "iterators" access elements on data structures. there various types of iterators, can travel linearly start end, can travel in both directions, , can move freely element in d. type of iterator supported d determine type of can run using d. "

you can take @ iterator categories here.

"b) if can run on d stl guarantees time-complexity (o(n)) take complete a."

yes, that's right. specification guarantees asymptotic computational cost of operation given data structure.