Archived

This topic is now archived and is closed to further replies.

Nervo

Possible way to convert a vector to a list and vice versa?

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
To copy the stuff from vector to list, it''s as slow as if you pushed the stuff directly the list, and slower because of the side-step of using a temp vector instead of directly using the list.

Besides, you''d need to have millions of students to even notice some speed problems! I think you''re worried over nothing, and de-optimizing even.

Share this post


Link to post
Share on other sites
I agree with AP, you probably don't need to worry about performance. Write your program so it works first, then you can speed it up.

That being said, you can copy any iterator range into a container via the range contructor or the assign function.


vector<string> names;
...
list<string> namesList(names.begin(),names.end());
list<string> namesList2;
namesList2.assign(names.begin(),names.end());


[edited by - sjelkjd on October 21, 2003 4:20:41 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by sjelkjd
That being said, you can copy any iterator range into a container via the range contructor or the assign function.
Yes, but lets make this clear: A range assignment is nothing but a concise way to do several push_backs repeatedly. It does not do such speed up as the original poster was hoping for, and if he uses a temp vector he''ll only lose speed. Vector and linked list are very different data structures so "simple assignment of the whole container" is simply not possible (i.e. in the way that it''s super-fast).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Push_back into a list is very fast, that's just three pointer assignments, the next pointer of the previously last element, and the prev pointer of the element inserted. And finally the next pointer of the element inserted, so that it points to the end of the list.

So, you should definitely not worry about the speed of that.

Additionally(added when I editited the post):

Inserting into a vector can be a great deal slower than inserting into a list, if you don't know the amount of elements you are going to insert beforhand. When there's not enough space left in the vector, it has to grow, wich is rather expensive, all elements have to be copied to another place in memory.

So in practice push_back into a list is usually faster than push_back into a vector.

The advantages of the vector is fast access of a given element, and most sorting algorithms needs a vector too. A vector also requires less memory than a list. Those are the arguments you should consider when choosing a vector instead of a list, not the speed of push_back.

[edited by - fredizzimo on October 21, 2003 6:07:30 AM]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites