vector sorting [beginner]

This is a discussion on vector sorting [beginner] within the C++ Programming forums, part of the General Programming Boards category; Well, with a little help I got started writing my own functions to sort a vector from least to greatest ...

  1. #1
    Registered User
    Join Date
    Nov 2004
    Posts
    25

    vector sorting [beginner]

    Well, with a little help I got started writing my own functions to sort a vector from least to greatest by a member of it's elements.

    It doesn't work at all, and I'm totally perplexed as to why not. Before I got any help, It would run through one iteration of the vector (successfuly putting the largest element at the end) but the program would crash. I couldn't figure out why, so I started over from scratch, and came up with these functions. For some reason, no changes are made to the contactList at all.

    Code:
            void listSort(){ //Bubble sortish 
                int biggest;
                int i;
                vector<contact>::iterator contactA;
                vector<contact>::iterator contactB;
                for (i=0;i!=contactList.size();++i){
                    biggest=i;
                    for (contactA=getIterator(&contactList[i]);contactA!=contactList.end();++contactA){
                        if ((contactA->getFirstName())>(contactList[biggest].getFirstName())){
                            contactB=getIterator(&contactList[biggest]);
                            biggest=intLoc(contactA);
                        }
                    }
                    iteratorSwap(&contactA,&contactB);
                }
                return;
            }
            vector<contact>::iterator getIterator(contact *matchingContact){ //Returns an iterator to the referenced element.
                vector<contact>::iterator i;
                for (i=contactList.begin();i!=contactList.end();++i){
                    if (i->getContactID()==matchingContact->getContactID()){//If two elements are the same...
                        return (i);
                    }
                }
                return(i);
            }
            void iteratorSwap(vector<contact>::iterator *a, vector<contact>::iterator *b){//Swaps elements.
                vector<contact>::iterator c;
                c=*a;
                a=b;
                *b=c;
                return;
            }
            int intLoc(vector<contact>::iterator matchingContact){//Returns the random access value equivalent to the iterator's position in the vector?
                vector<contact>::iterator i;
                int placeInVector=0;
                for (i=contactList.begin();i!=contactList.end();++i){
                    if(i->getContactID()==matchingContact->getContactID()){
                        return (placeInVector);
                    }
                    else{
                        ++placeInVector;
                    }
                }
                return (placeInVector);//Shouldn't ever happen if matchignContact is a legit value
            }
    It compiles successfuly, but no changes are actually made.
    getContactID() is a function that simply returns the contactID (int) of the contact.
    getFirstName() is the same thing, but a string.

    Thanks.

  2. #2
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    Are you learning how to sort or are you actually trying to sort something in your code? If it is the latter, then you should use the sort function in <algorithm> (or some other more appropriate algorithm).

    If you are just learning how to sort, then you don't want to swap iterators like you are doing. You want to swap actual elements. Setting one iterator equal to another doesn't actually swap them in the vector. There are other issues, also. Like how you loop through the vector in getIterator to find an iterator to the element you already have access to.

    I'd suggest using sort if you just need to sort, and don't use iterators if you are just trying to learn to sort.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    The [] operator is overloaded for the std vector class. Is there a reason why you are trying to use iterators rather than the [] operator? Iterators point to a memory location, just like pointers. You don't really want to swap memory locations, you want to swap values at memory locations. If you must pass iterators by reference for some reason, I'd suggest passing them as references rather than pointers, as it makes the syntax easier, and still accomplishes everything you can do passing as a pointer.

  4. #4
    Registered User
    Join Date
    Nov 2004
    Posts
    25
    I'll keep that in mind, but I guess I just can't get that concept through my head.
    I am trying to swap things in actual code, but I had no idea how to use the algorithm library. I figured the best way to learn it would be try to construct the functions myself. This would give me a better understanding on how it worked. I tried using the sort function, but it didn't work. (I can't remember why, I'm at a friend's house right now and I don't have the program handy) I think it had something to do with the fact I'm sorting them by their first name's alphabetically. As for the swap part, you're saying I should pass the address of the actual element?

    Well, I thought that's what iterator's were? Pointers containing the address of an element?

    Eek.

    Thanks for the advice, I'm sure I'll get it.

  5. #5
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    The problem with the sort function was probably a comparison operator problem (which can be fixed). Writing the sort yourself at least once is definitely beneficial, though.

    First, consider how you iterate using an iterator in the method getIterator. You can use that directly in the loop for your sort method instead of using an int index. You would have to, of course keep the biggest index as an iterator as well. (Although, it could be done using only indices and no iterators.)

    As the the swap. Consider two pointers (iterators do essentially the same thing), x and y. Say that x points to array[a] and y to array[b]. Now, the way you have it set up, you set x = array[b] and y = array[a]. That is, you just trade places of the iterators, without changing their content. So, you need to dereference them, and swap their content, not the locations they point to.

    Cheers
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  6. #6
    Registered User
    Join Date
    Nov 2004
    Posts
    25

    Thumbs up Finally, victory is mine.

    Alright. =) With a bit of time and experimentation, not to mention staring at a few examples really hard, I was able to understand how the sorting works. I'm suprised at how simple it really is now, but I'm a little disappointed that I couldn't catch on to it independantly. Either way, I'm glad to have it figured out. =P

    Here's what I came up with pertaining to the sorting of an array of contacts. I even made it go by last name first, and then if the last names are the same, it goes by first name. I'm proud of that part. =P

    list::listSort() works by sorting the list by last name (or first name if they're the same), and then iterates once more through the container to reset the contactIDs. (The variables the user specifies to select a contact, so the interface?)

    list::contactSwap() is pretty self explanitory, although before, I was stuck on having to use iterators for some reason.

    I'll have to look at <algorithm> 'cause I'm not too sure how I'd apply that to this situation. =| Either way, it was educational. =P

    Code:
            void listSort(){
                int smallest;
                for (int i=0;i!=contactList.size();++i){
                    smallest=i;
                    for (int j=i;j!=contactList.size();++j){
                        if ((contactList[j].getLastName())<(contactList[smallest].getLastName())){
                            smallest=j;
                        }    
                        else if ((contactList[j].getLastName())==(contactList[smallest].getLastName())){
                            if ((contactList[j].getFirstName())<(contactList[smallest].getFirstName())){
                                smallest=j;
                            }
                        }
                    }
                    contactSwap(&contactList[i],&contactList[smallest]);
                }
                vector<contact>::iterator matchingContact;
                int matchingID=1;
                for ((matchingContact=contactList.begin());matchingContact!=contactList.end();++matchingContact){
                    matchingContact->setContactID(matchingID);
                    ++matchingID;
                }    
                return;
            }
            void contactSwap(contact *contactA,contact *contactB){
                contact contactTemp=*contactA;
                *contactA=*contactB;
                *contactB=contactTemp;
                return;
            }
    Now, onward to unknown territory. File streams. Saving should write the list into a file, including the contact details, while loading should let the user specify a file (based on choices given), then read all the information into the appropriate objects. I sure hope I've got the right idea. If not, someone stop me. =P

    Any constructive criticism is definitely welcome.
    Thanks to all who've helped.

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    See if you like this syntax better. I didn't test it, but I'm pretty sure it will work, without all the pointers, and addresses of array elements, and derefernces of pointers, etc. Assumes contactList is an array of type contact.
    Code:
     
    contactSwap(contactList, i, smallest);
     
    void contactSwap(contact * contactList, int i, int j)
    {
       contact contactTemp= contactList[j];
       contactList[j] = contactList[i];
       contactList[i] = contactList[contactTemp];
    }
    If contactList is a vector then the syntax could be something like:
    Code:
    cotactSwap(contactList, i, smallest);
     
    void contactSwap(vector<contact> & contactList, int i, int j)  
    {
       contact contactTemp= contactList[j];
       contactList[j] = contactList[i];
       contactList[i] = contactList[contactTemp];
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. [beginner] float and division
    By codezero in forum C Programming
    Replies: 5
    Last Post: 04-27-2009, 09:32 PM
  2. [beginner] get file address from file pointer
    By taisao in forum C Programming
    Replies: 14
    Last Post: 03-30-2007, 09:46 AM
  3. New problem [Beginner]
    By Vintik in forum C++ Programming
    Replies: 2
    Last Post: 08-18-2005, 11:33 PM
  4. New Problem [Beginner]
    By Vintik in forum C++ Programming
    Replies: 5
    Last Post: 08-16-2005, 11:23 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21