CS 509 Test 4

CS 509, Advanced Programming II

Fall 2001 - Test 4

Let m be a variable of type map<int,string>. Given that
```
copy(x.begin(), x.end(), front_inserter(m))
```
compiles and executes correctly, what is the type of x?
The copy inserts elements into m, and for those insertions to be correct, the type of the elements being inserted must be pair<int,string>, the type of the elements in m. The interators returned by x.begin() and x.end() must refer to values of type pair<int,string>, and because any STL container supports begin() and end(), x can have type vector<pair<int,string> >, list<pair<int,string> >, or map<int,string>
Except, maps don't support push_front(), so the code given in the problem does not compile. What I should have written was
```
copy(x.begin(), x.end(), inserter(m, m.begin()))
```
For the curious, here's the error message produced by g++ for the code given in the problem:
/usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/../../../../include/g++-3/stl_iterator.h: In method class front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > > & front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >::operator =(const pair<const basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> &):
/usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/../../../../include/g++-3/stl_algobase.h:139: instantiated from __copy<pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >, ptrdiff_t>(pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >, random_access_iterator_tag, ptrdiff_t *)
/usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/../../../../include/g++-3/stl_algobase.h:161: instantiated from __copy_dispatch<pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >, __false_type>::copy(pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >)
/usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/../../../../include/g++-3/stl_algobase.h:188: instantiated from copy<pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > > >(pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, pair<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> *, front_insert_iterator<map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> > >) t.cc:10: instantiated from here
/usr/local/lib/gcc-lib/sparc-sun-solaris2.8/2.95.3/../../../../include/g++-3/stl_iterator.h:400: no matching function for call to map<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int, less<basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> > >, allocator<int> >::push_front (const pair<const basic_string<char, string_char_traits<char>, __default_alloc_template<false, 0> >, int> &)
CC wasn't much better with this error:
"/export/opt/forte/SUNWspro/WS6U2/include/CC/Cstd/./algorithm.cc", line 427: Error: Cannot assign std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int> to std::front_insert_iterator<std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char>>>, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>>>> without "std::front_insert_iterator<std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char>>>, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>>>>::operator=(const std::front_insert_iterator<std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char>>>, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>>>>&)";.
"t.cc", line 10: Where: While instantiating "std::copy<std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>*, std::front_insert_iterator<std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char>>>, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>>>>>(std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>*, std::pair<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>*, std::front_insert_iterator<std::map<std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int, std::less<std::basic_string<char, std::char_traits<char>, std::allocator<char>>>, std::allocator<std::pair<const std::basic_string<char, std::char_traits<char>, std::allocator<char>>, int>>>>)".
"t.cc", line 10: Where: Instantiated from non-template code. 1 Error(s) detected.
Give an example where it would be better to use a map with an integer key rather than a vector. (Hint: "When the data needs to be sorted." is not a correct answer.)
If the distance between successive indicies refering to non-default values is large, using a map instead of a vector would save space. For example, storing the set of pairs
```
{ (0, 0), (10, 1), (100, 2), (1000, 3) }
```
would take four elements (or so) in a map and 1001 elements in a vector.
Describe the weakest (least powerful) iterators required to implement the remove(s, e, v) generic function. Justify your answer.
The implementation of remove() is roughly
```
remove(s, e, v) 

  while true
    while s != e && *s == v
      s++
    if s == e
      return e

    is_val = s
    while is_val != e && *is_val != v
      is_val++
    if is_val == e
      return s

    t = *s
    *s = *is_val
    *is_val = t
```
The swap at the bottom of the while loop means that s and e must be both intput and output iterators; that is, they must both be forward iterators. The other operators applied to s and e (* and equality comparisons) are covered by forward iterators, which is the weakest iterator kind possible in this case.
Provide an upper-bound asymptotic estimate for the run-time of the following code:
```
list<Student_Info> extract_fails(list<Student_Info> & students) {

  list<Student_Info> fail;
  list<Student_Info>::iterator iter = students.begin();

  while (iter != students.end())
    if (fgrade(*iter)) {
      fail.push_back(*iter);
      iter = students.erase(iter);
      }
    else
      ++iter;

  return fail
  }
```
Be sure to clearly state your assumptions.
Because operations on iterators are constant time, the worst-case estimates for the atomic statements are
```
O(1)
list<Student_Info>::iterator iter = O(1)

while (iter != O(1))
  if (fgrade(O(1))) {
    fail.push_back(O(1));
    iter = students.erase(O(1));
    }
  else
    O(1);

return fail
```
Creating a list takes constant time, but assigning one list to another takes O(n), where n is the number of elements in the list. Inequality takes constant time, as does fgrade(). Pushing back and erasing from a list also takes constant time, which gives
```
O(1)
O(n)

while (O(1))
  if O(1) {
    O(1)
    O(1)
    }
  else
    O(1);

return fail
```
The if rule reduces the while body to constant time; the while iterates O(n) times. Returning a list requires a copy, which takes O(n) time. The anaysis is now
```
O(1)
O(n)

while O(1) : O(n)
  O(1)

O(n)
```
The while and sequence rules reduce the analisys to an O(n) execution time.

This page last modified on 12 November 2001.