582484 Algorithm Libraries

Exercise 3 solutions

  1. Note that we cannot use front_insert_iterator for vector because it doesn't have push_front() as a member. So, for uniformity, we haven't used insert_iterators at all.

    #include <iostream>
    #include <sstream>
    #include <vector>
    #include <deque>
    #include <list>
    
    
    typedef int test_type;
    typedef std::vector<test_type> test_vector;
    typedef std::deque<test_type> test_deque;
    typedef std::list<test_type> test_list;
    
    // generic version of back insertion
    template <typename Container>
    void
    test_back(int count)
    {
      Container c;
      typedef typename Container::value_type value_type;
      for (int i = 0; i < count; ++i)
        c.push_back(value_type());
    }
    
    
    // generic version of front insertion (used for deque and list)
    template <typename Container>
    void
    test_front(int count)
    {
      Container c;
      typedef typename Container::value_type value_type;
      for (int i = 0; i < count; ++i)
        c.push_front(value_type());
    }
    
    // specialized version of front insertion (used by vector)
    // since vector doesn't have push_front() member
    template <>
    void
    test_front<test_vector>(int count)
    {
      test_vector c;
      typedef test_vector::value_type value_type;
      for (int i = 0; i < count; ++i)
        c.insert(c.begin(), value_type());
    }
    
    
    // generic version for inserting in the middle
    template <typename Container>
    void
    test_middle(int count)
    {
      Container c;
      typedef typename Container::value_type value_type;
      typedef typename Container::iterator iterator;
      iterator iter = c.begin();
      for (int i = 0; i < count/2; ++i) {
        iter = c.insert(iter, value_type());
        iter = c.insert(iter, value_type());
        ++iter; // try to stay in the middle of the sequence
      }
    }
    
    int main(int argc, char* argv[])
    {
    
      if (argc != 4) {
        std::cerr << "Give three parameters: container, position and count" 
    	      << std::endl;
        return 1;
      }
    
      std::string container(argv[1]);
      std::string position(argv[2]);
      int count(atoi(argv[3]));
    
      clock_t start = clock();
    
      if (position == "back") {
    
        if (container == "vector")
          test_back<test_vector>(count);
        else if (container == "deque")
          test_back<test_deque>(count);
        else if (container == "list")
          test_back<test_list>(count);
    
      }
      else if (position == "front") {
    
        if (container == "vector")
          test_front<test_vector>(count);
        else if (container == "deque")
          test_front<test_deque>(count);
        else if (container == "list")
          test_front<test_list>(count);    
    
      }
      else if (position == "middle") {
    
        if (container == "vector")
          test_middle<test_vector>(count);
        else if (container == "deque")
          test_middle<test_deque>(count);
        else if (container == "list")
          test_middle<test_list>(count);    
    
      }
      else {
        std::cerr << "Position should be either front, middle or back"
    	      << std::endl;
        return 1;
      }
    
      // returns CPU time in seconds since the first call to clock()
      std::cout << (clock() - start)/(float)CLOCKS_PER_SEC;
      return 0;
    }
    
    

    In the following table 100000 integers were inserted in the three containers in different positions. The times are in seconds.

    vector front  6.48
    vector middle  3.15
    vector back  0
    deque front  0
    deque middle  63.94
    deque back  0
    list front  0.02
    list middle  0.02
    list back  0.02
    
    
    1. The essential operations of a queue are insertion at the back and removal from the front. The vector container doesn't allow insertion and removal from the front (at least, not efficiently). Therefore deque is used instead.

      List is not a random access container. Usually, priority queues are implemented as heaps (like binary heap), and a heap is represented as a tree, which is stored in an array for efficiency. Therefore random access property is needed.

    2. A stack can be implemented in terms of list, deque or vector. A deque is the default choice. It is obviously more efficient than list. In addition, deque is able to automatically decrease its capacity; in vector one can only increase capacity, not decrease it.

      As said in the first part of the question, using vector to implement a queue is out of the question. But list and deque are possible candidates since they both are front and back insertion sequences. Deque is chosen for default value because of efficiency.

      Priority queue needs to have a random access container as its underlying sequence, therefore a list will not do. A vector is preferred over deque for efficiency reasons. Speed is more essential here than with stack because all stack operations are constant time, but in a priority queue a push-operation can have logarithmic complexity. Therefore the individual random access operations used in performing the priority queue operations need to be fast. A deque is a more complicated data structure than a vector, and that is why its random access operations are also a bit slower.

  2. Accounting

    #include <iostream>
    #include <string>
    #include <map>
    
    int main()
    {
      std::map<std::string, int> balance;
      typedef std::map<std::string, int>:: iterator iterator;
      std::string name;
      int sum;
    
      // note that if a key is not found in the container,
      // then it is added there with its mapped type default constructed,
      // which results zero in the case of an integer. It is NOT
      // left uninitialized
      while (std::cin >> name >> sum)
        balance[name] += sum;
    
      for (iterator i = balance.begin(); i != balance.end(); ++i)
        std::cout << i->first << ' ' << i->second << std::endl;
      return 0;
    }