PDA

View Full Version : need help with C++ command line utility




Furgster
Aug 29, 2008, 10:49 PM
ive written this program that allows the user to input names and find and remove them in a vector. the insertion function is able to put them in alphabetical order but i am having a problem when i insert a name that is less than the previous name entered. for example, when i insert john and then insert adam, it returns the array as adam and adam instead of adam and john. i am certain that the error is in the insert function at the for loop, but i dont know what the error and cant fix it. ive been trying for hours, its probably something simple that i cant see, and any help would be great thanks!


#include <iostream>
#include <vector>
#include <string>
#include <cassert>

using namespace std;

const int NOT_FOUND = -1;

/**
prints out all names in a vector, one per line
param names the vector to print
*/
void printNames(vector<string> names) {
for (unsigned int i=0; i < names.size(); i++) {
cout << names[i] << endl;
}
}

/**
finds location of a name in a vector of names
param names is the vector to search
param target is the name we are looking for
returns the location of target in the vector, or
NOT_FOUND if it's not present
*/
int lookup(vector<string> names, string target) {
unsigned int loc = 0;

while (loc < names.size() && names[loc] != target) {
loc++;
}
if (loc == names.size()) {
return NOT_FOUND;
}
else {
return loc;
}

}


/**
removes value at loc in names
param names is a vector where size() > 0
param loc is a location such that 0 <= loc < size()
*/
void removeAt(vector<string>& names, unsigned int loc) {
assert(0 <= loc && loc < names.size());
for (unsigned int i = loc; i < names.size()-1; i++) {
names[i] = names[i+1];
}
names.pop_back();
}


/**
removes a name from names vector. if target name not present does nothing
leaves remaining names in same order as before call.
param names is the vector
param target the name to remove
*/
void remove(vector<string> &names, string target) {
int loc = lookup(names, target);
if (loc != NOT_FOUND) {
removeAt(names,loc);
}
}


/**
inserts into a vector of strings in alphabetical order
if it's not already there.
param names is a list of strings in alphabetical order
param newName is a name to insert
returns false if no insert done (name is already in list), true otherwise
*/
bool insert(vector<string> &names, string newName) {
int loc = lookup(names,newName); // already present

if (loc == NOT_FOUND) { //

unsigned int newLoc = 0; // find correct location
while (newLoc < names.size() && newName > names[newLoc]) {
newLoc++;
}

names.push_back(newName);
for (unsigned int i = newLoc+1; i < names.size(); i++) {
names[i] = names[i-1];

}
//names[newLoc] = newName;
return true;
}
else {
return false;
}
}



int main() {

vector<string> names;
string name;
char cmd;
int loc;

cout << "i(nsert) r(emove) l(ookup) e(xit): ";
cin >> cmd;
while (cmd != 'e') {
switch (cmd) {
case 'i':
cout << "What name do you want to insert? ";
cin >> name;
insert(names,name);
break;
case 'r':
cout << "What name do you want to remove? ";
cin >> name;
remove(names,name);
break;
case 'l':
cout << "What name are you looking for? ";
cin >> name;
loc = lookup(names, name);
if (loc == NOT_FOUND) {
cout << name << " is not in the list" << endl;
}
else {
cout << name << " is " << loc+1 << "th in the list" << endl;
}
break;
default:
cout << "Invalid command." << endl;
}

cout << "There are " << names.size() << " names." << endl;
cout << "The names are..." << endl;
printNames(names);

cout << "i(nsert) r(emove) l(ookup) e(xit): ";
cin >> cmd;

}

return 0;

}



lee1210
Aug 29, 2008, 11:36 PM
I was really hoping someone else would post first, because C++ is not one of my primary languages, but I gave it a go and came up with this. I tried to just do something simple to test with instead of integrating my attempt into your code.


#include <string>
#include <iostream>
#include <vector>

void insertOrdered(std::vector<std::string> &,std::string);
void printList(std::vector<std::string>);

int main(int argc, char *argv[]) {
std::string input;
std::vector<std::string> names;
for(int x=0; x < 10; x++) {
std::cout << "Enter name " << x << ": ";
std::cin >> input;
insertOrdered(names,input);
}
printList(names);
}

void insertOrdered(std::vector<std::string> &nameList,std::string newName) {
std::vector<std::string>::iterator findPos;
if(nameList.empty()) {
nameList.push_back(newName);
return;
}
for( findPos = nameList.begin(); findPos != nameList.end(); findPos++) {
if(newName == *findPos) return; //Make it unique
if(newName < *findPos) {
nameList.insert(findPos,newName);
return;
}
}
nameList.push_back(newName);
return;
}

void printList(std::vector<std::string> toPrint) {
std::vector<std::string>::iterator printPos;
std::cout << "Printing list, there are " << toPrint.size() << " elements." << std::endl;
for(printPos = toPrint.begin(); printPos != toPrint.end(); printPos++) {
std::cout << "Next name: " << *printPos << std::endl;
}
}



It seemed like doing one operation on the vector rather than a bunch of manual reorganization would be best for the insert. I tested this a few times, and the logic seems sound.

As an aside, vector will be slow for inserting because an array is used underneath. You may want to switch to another data structure that wouldn't have this sort of penalty (essentially the manual reorganization you were doing happens anyway whenever you insert, plus amortized N complexity because reallocs will be necessary when the underlying array gets full and you do the next insert).

-Lee

Furgster
Aug 30, 2008, 12:28 AM
thank you for the advice, and i think you are right, there are much better ways of doing this than the way i have it. however, this is actually a piece of homework and i am required it to do it this way :(, thanks for helping!

lee1210
Aug 30, 2008, 12:46 AM
thank you for the advice, and i think you are right, there are much better ways of doing this than the way i have it. however, this is actually a piece of homework and i am required it to do it this way :(, thanks for helping!

please say if you are working on homework, so people don't write code for you.

I am not familiar enough with std::vector to say the right way to do this other than using an iterator. Push_back puts things at the end, so I guess using operator[] is it. You find where you need to put the new string, you just need to increase size before your for loop, then after the loop just assign newName to the proper position with [] notation.

-Lee

Furgster
Aug 30, 2008, 02:21 AM
thanks for your help, after many tries through the xcode debugger i was able to figure out what it was doing and fix it, thanks again! :D

Mac Player
Aug 30, 2008, 03:15 AM
thank you for the advice, and i think you are right, there are much better ways of doing this than the way i have it. however, this is actually a piece of homework and i am required it to do it this way :(, thanks for helping!


Next time you might want to try the multiset :D

Sander
Aug 30, 2008, 03:24 AM
Also, get used to passing "large" things by const reference instead of by value. "Large" is anything bigger than 4 bytes, so a vector of strings certainly applies. Otherwise, the entire vector is copied when it is passed to your functions.

So instead of

int doSomething(std::vector<std::string> someVector, std::string someString);


do


int doSomething(const std::vector<std::string>& someVector, const std::string& someString);

mobilehaathi
Aug 30, 2008, 07:59 AM
Also, get used to passing "large" things by const reference instead of by value. "Large" is anything bigger than 4 bytes, so a vector of strings certainly applies. Otherwise, the entire vector is copied when it is passed to your functions.

So instead of

int doSomething(std::vector<std::string> someVector, std::string someString);


do


int doSomething(const std::vector<std::string>& someVector, const std::string& someString);




const only if he is planning to not modify it. If he plans to change the data structure within the function, errors will occur.

Sander
Aug 30, 2008, 02:16 PM
const only if he is planning to not modify it. If he plans to change the data structure within the function, errors will occur.

If he passes things by value while planning to modify it, he will face even stranger errors, as he will be modifying his local copy only.

mobilehaathi
Aug 30, 2008, 07:20 PM
If he passes things by value while planning to modify it, he will face even stranger errors, as he will be modifying his local copy only.

Obviously! :)

That is why I only mentioned const.:cool: