With this particular c++ grading program I am working on it builds a vector of students from input by the user that contains a struct which holds the students name midterm, final and homework grades. After input is complete another function is used to extract failing students and place them into another vector while erasing each failing record from the original vector. I'm taking performance issues into consideration. I realize that pushing back onto a vector is more efficient than pushing back onto a list, while removal of elements from the middle parts of a list will be faster than doing that operation on a vector. So, what I wanted to do was build the initial students records data using a vector (quicker) and then converting it to a list and passing it to the function that would pluck it apart as needed. Does anyone see what I'm trying to do or does it make any sense? I am not sure if there is a way to try and assign data from a vector to a list by simple assignment of the whole container. Well thanks for any help guys. |PicRepository|PicIndex| IM : CScoder@aol.com/ahmed7500@hotmail.com Duplicate this sig: Member of the Ban the Idiot Directxmen Society (BIDS) [edited by - nervo on October 21, 2003 3:56:29 AM]

Thanks for the input thus far guys. I have already written the program and it works well through vectors. This is something I must consider:

Performing removal of elements from a vector can make the run time squared the number of elements in the vector to preserve random access properties of a vector type. (according to my text).

Pushing back elements onto a list (growing sequentially) will be slower with a list than a vector.

With those two things said, the method of using a list for removing elements may have much more of a performance gain than using a vector, that also having to push_back onto a list would create a net gain in performance over using a vector for the whole operation. This is what I shall test.

Both a list and vector have O(1) push_back time, but the vector's time is amortized, meaning that a single push_back operation can be very expensive, but that m push_backs will cost O(m) time.
The difference between m pushbacks in the two will be within a constant factor of the other.(In Java the LinkedList add is actually a bit slower(constant factor) than the ArrayList("vector") over say 10000 add's)).

Why not just use a list all the way through? Do you need random access at any point?

Perhaps if you could explain a bit more about the operations you need to support on the structure, we could be of more help.
Btw, how many students are we talking about?

[edited by - ziphnor on October 21, 2003 8:52:35 AM]

Thanks a bunch for your insight among the two fredizzimo; I agree at this point.

Ziphnor: This program was only an exercise I had to do from the end of a chapter within a book. The bulk of the code was developed from the previous chapter with the only addition to modify the containers for pass/fail. I didn't do anything with the failed students container because when the pass container is displayed it should omit the failed students proving it works. Initially I wanted to mix a vector and list, but even if that was possible it appears impractical.

I shall now post the code (minus 2 headers):
mainsrc.cpp

#include <algorithm>#include <iomanip>#include <ios>#include <iostream>#include <stdexcept>#include <string>#include <vector>#include "grade.h"#include "Student_info.h"using std::cin;				using std::setprecision;using std::cout;			using std::sort;using std::domain_error;	using std::streamsize;using std::endl;			using std::string;using std::max;				using std::vector;using std::list;int main(){	list<Student_info> students;	Student_info record;	string::size_type maxlen = 0;	while (read(cin, record)) {		maxlen = max(maxlen, record.name.size());		students.push_back(record);	}	list<Student_info> failed;	failed = extract_fails(students);	students.sort(compare);	for (list<Student_info>::iterator iter = students.begin(); iter != students.end(); ++iter) {		cout << (*iter).name << string(maxlen + 1 - (*iter).name.size(),			' ');		try {            double final_grade = grade(*iter);			streamsize prec = cout.precision();			cout << setprecision(3) << final_grade << setprecision(prec);		} catch (domain_error e) {			cout << e.what();			getchar();		}		cout << endl; 	}	getchar();	return 0;}  Student_info.cpp   #include "Student_info.h"#include "grade.h"using std::istream;	using std::vector;using std::list;bool compare(const Student_info& x, const Student_info& y){	return x.name < y.name;}istream& read(istream& is, Student_info& s){	std::cout << "Please enter first name followed by midterm and final grades: ";	is >> s.name >> s.midterm >> s.final;	read_hw(is, s.homework);	return is;}istream& read_hw(istream& in, vector<double>& hw){	if (in) {		hw.clear();		std::cout << "Please enter homework grades in succession: ";		double x;		while (in >> x)			hw.push_back(x);		in.clear();	}	return in;}bool fgrade(const Student_info s) {	return grade(s) < 60;}list<Student_info> extract_fails(list<Student_info>& students) {	list<Student_info>::iterator iter = students.begin();	list<Student_info> fail;	while(iter != students.end()) {		if(fgrade(*iter)) {			fail.push_back(*iter);			iter = students.erase(iter);		} else {			iter++;		}	}		return fail;		}  grade.cpp   #include <stdexcept>#include <vector>#include "grade.h"#include "median.h"#include "Student_info.h"using std::domain_error;	using std::vector;double grade(double midterm, double final, double homework){	return 0.2 * midterm + 0.4 * final + 0.4 * homework;}double grade(double midterm, double final, const vector<double>& hw){	if(hw.size() == 0)		throw domain_error("Student has done no homework");	return grade(midterm, final, median(hw));}double grade(const Student_info& s){	return grade(s.midterm, s.final, s.homework);	}  median.cpp   #include <algorithm>#include <stdexcept>#include "median.h"using std::domain_error;	using std::sort;	using std::vector;double median(vector<double> vec){	typedef vector<double>::size_type vec_sz;	vec_sz size = vec.size();	if (size == 0)		throw domain_error("median of an empty vector");	sort(vec.begin(), vec.end());	vec_sz mid = size/2;	return size % 2 == 0 ? (vec[mid] + vec[mid-1]) / 2 : vec[mid];}  pertinant header for readability Student_info.cpp   #ifndef GUARD_Student_info#define GUARD_Student_info#include <iostream>#include <string>#include <vector>#include <list>struct Student_info {	std::string name;	double midterm, final;	std::vector<double> homework;};bool compare(const Student_info&, const Student_info&);std::istream& read(std::istream&, Student_info&);std::istream& read_hw(std::istream&, std::vector<double>&);bool fgrade(const std::vector<Student_info>&);std::list<Student_info> extract_fails(std::list<Student_info>&);#endif 

I redid the code here using only list. It works fine. Feel free to leave comments if you like. This was only an exercise from Acclerated cpp.

[edited by - nervo on October 21, 2003 10:41:38 AM]