Algorithm Libraries exam Model solutions and grading 1. a) vector vs. deque Deque: - allows fast insertions to the beginning of the container - can automatically decrease its size if space is no longer needed - insertions and deletions to the beginning and end do not invalidate pointers and references to other elements (like they may in vector) Vector: - lower overhead in access and iteration operations - uses contiguous memory area Grading: 1 point per each fact, but at most 3 points in all b) auto_ptr vs. boost::shared_ptr auto_ptr: - no memory/time overhead (doesn't use reference counter) - uses unusual move semantics, that is: when copying an auto_ptr the ownership is transferred. shared_ptr: - allows multiple owners - can be stored in STL containers Grading: 1 point per each fact, but at most 3 points in all 2. a) int n=100; std::vector v; v.reserve(n); // reserve just enough capacity randint r(seed); std::generate_n(std::back_inserter(v), n, r); // or alternatively, this gives you only 1 point for (int i = 0; i != n; ++i) v.push_back(r()); b) std::set s; while (s.size() != n) s.insert(r()); std::vector v(s.begin(), s.end()); // or in a harder way, this gives you only 2 points std::vector v; int i; while(v.size() != n) { while (find(v.begin(), v.end(), i=r()) != v.end()) ; v.push_back(i); } A severe error can reduce one point. 3. If an algorithm or a container (etc) wants to be generic, then it should make minimal assumptions about the data types it uses. The set of syntactic and semantic requirements for a type is called *concept*. A concept is not a thing the compiler knows about, it is something more abstract, usually only mentioned in the documentation. But the types that fulfill the requirements of a concept (models for a concept) should be valid C++ types. For example, a type is a model of the *equality comparable* concept if - the expressions x==y and x!=y are valid (syntactic requirement) - the operators == and != are consistent (semantic - the operator== is an equivalence relation. requirements) All the primitive types of C++ are models of this concept. In C++ genericity is achieved by not specifying some specific types the algorithms and containers use, but by letting the types be parameterised as template parameters. Then in the documentation it is mentioned that for the algorithm (etc) to work, the type parameters should be models for some concepts. Concept is a two-sided issue: because it is not recognised by compilers (at least not yet) it is hard to verify whether a type models a concept or not. But on the other hand, this looseness gives much freedom and flexibility; even beyond what the designers originally intented. In addition to the algorithms and containers in STL, especially the concepts it defines are of great importance. The chosen concepts are minimal and form hierarchies, therefore they form a solid base for extensions and reuse of code. Also, because of the similar interfaces, it is easy to switch from one container to another, without having to change much code. Efficiency of an algorithm can be achieved by refining a concept into a subhierarchy. Then the algorithm is specialized for these different concept refinements so that fastest possible implementation is selected for each type. In STL this is done by tag dispatching. For example, the distance and advance algorithms are specialized for different types of iterators (forward, bidirectional, random access). Grading: Approximately one point per each paragraph above, but at most five points. 4. struct my_less { typedef std::map::value_type value_type; bool operator()(value_type a, value_type b) const { return a.second < b.second; } }; struct my_count { my_count(std::map& map) : m(map) {} void operator()(person p) { m[p.first_name] += 1; } private: std::map& m; }; std::vector v; std::vector::iterator vi; // initialize v std::map m; std::map::iterator mi; for_each(v.begin(), v.end(), my_count(m)); mi=std::max_element(m.begin(), m.end(), my_less()); std::cout << mi->first << std::endl; 5 points for good answer. 1 minus point per traditional for loop 1 minus point for some severe error 5. a) An iterator i is dereferencable if the expression *i is valid. So, a dereferencable iterator really points to a valid object. b) An iterator is mutable if one can change the pointed object through it. c) [a,b) is a valid range if - both a and b are valid iterators - iterator b can be reached from iterator a by applying operator++ finitely many times. d) difference_type Result type of subtracting two iterators. Note that subtracting iterators in generally allowed only for random access iterators. 1 point for correct answer 1/2 a point for incomplete answer Points from parts a,b,c and d are summed and rounded up.