Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

Furgster

macrumors 6502
Original poster
Jun 16, 2007
260
1
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!

Code:
#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

macrumors 68040
Jan 10, 2005
3,182
3
Dallas, TX
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.

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

macrumors 6502
Original poster
Jun 16, 2007
260
1
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

macrumors 68040
Jan 10, 2005
3,182
3
Dallas, TX
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

macrumors 6502
Original poster
Jun 16, 2007
260
1
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

macrumors regular
Jan 19, 2006
225
0
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

macrumors 6502a
Apr 24, 2008
519
66
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
Code:
int doSomething(std::vector<std::string> someVector, std::string someString);

do

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

mobilehaathi

macrumors G3
Aug 19, 2008
9,368
6,352
The Anthropocene
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
Code:
int doSomething(std::vector<std::string> someVector, std::string someString);

do

Code:
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

macrumors 6502a
Apr 24, 2008
519
66
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.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.