Wednesday, February 19, 2003

In order to improve performance of the vector solutions that we saw in the previous class, we can use a list container. Here is the main() program:

#include <algorithm>
#include <list>
#include <string>

#include "grade.h"
#include "Student_info.h"

using std::max;

using std::cin;
using std::cout;
using std::endl;
using std::list;
using std::string;

list<Student_info> extract_fails(list<Student_info>& v);

int main()
{
        list<Student_info> vs;
        Student_info s;
        string::size_type maxlen = 0;
        while (read(cin, s)) {
                maxlen = max(maxlen, s.name.size());
                vs.push_back(s);
        }

        vs.sort(compare);

	list<Student_info> fails = extract_fails(vs);

	list<Student_info>::iterator i;

	for (i = fails.begin(); i != fails.end(); ++i)
		cout << i->name << " " << grade(*i) << endl;

	return 0;
}

And here is the implementation of the extract_fails() function using the list container. Note that its implementation is identical to the vector version that used iterators, except that vector has been replaced by list.

#include <list>
#include "Student_info.h"
#include "grade.h"

using std::list;
// version 4: use `list' instead of `vector'
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;
}

Advantages of list containers

• Insertion/deletion in the middle of a list container is quick relative to doing similar operation on a vector container.
• Erasing an item from a list invalidates only the erased item, not iterators that refer to subsequent items.
• Inserting an item into a list cannot potentially invalidate all the iterators that refer to other elements in the list.

Disadvantages of list containers

• You cannot randomly access elements in the list. (e.g. No indexing operator ([ ]) is defined for a list.)
• Because random access is not possible, the global sort() function cannot be used. (However, the list class provides its own sort() member function to sort its items.)

Advantages of vector containers

• You can randomly access elements in the vector. (e.g. An indexing operator ([ ]) is defined for a vector.)
• The global sort() function can be used to sort vector items. There's no need for vector to define its own sort() function.

Disadvantages of vector containers

• Insertion/deletion in the middle of a vector container is slow relative to doing similar operation on a list container.
• Erasing an item from a vector invalidates the iterator of the erased item as well as iterators that refer to subsequent items.
• Inserting an item into a vector can potentially invalidate all the iterators that refer to other elements in the vector. This is because all elements in the vector may have to be copied and moved in memory to ensure there is (contiguous) space for the new elements.

Miscellaneoues

Although we will not be covering K&M § 5.6, 5.7, 5.8 in class, you should sill read these sections as they continue to give further examples of container manipulation. Note that instead of doubles, string are actually stored in the vector container.

There are a couple of interesting functions methods introduced in these sections.

• substr() member function of the string class takes an index and a length and makes a copy of the characters in the index range from i upto but not including i+j.
• The global getline() function is provided which is roughly analagous to fgets() in C. getline() takes two parameters: an istream, and a string. It returns a reference to the istream passed in after the input operation takes place. The function itself reads the nect line of input from the input stream and stores it in the supplied string (without the newline character). You can use this function as the condition of a while loop.

  
  #include <iostream>
  #include <string>
  
  int
  main()
  {
  	std::string s;
  	while (getline(std::cin, s))
  		std::cout << s << std::endl;
  	return 0;
  }
  
  
  

Last modified: Thu Feb 20 13:00:54 2003