Thread: Randomly rearranging the elements in a vector

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    7

    Randomly rearranging the elements in a vector

    Hello, it's been quite some time since I've come to these forums. Anyway! I have a question about using the C++ vector class (from the standard). I want to perform an action to each and every element in one of my vectors, but I want the order of elements I perform the action on to be random.

    I was thinking one way to do this would be to just implement some algorithm that randomly rearranged all the elements in the vector, and then to go through the randomly rearranged vector sequentially performing the action. Is there any algorithm that could randomly sort a vector that would be easy to implement?

    Might there be a much better way here of doing what I'm trying to do that I'm not thinking of? (I am definitely not a C++ programmer!)

    Also, I've been wondering whether vector is the best class to use for what I'm trying to do. I need a list of elements, where I can add to the back of the list and remove from anywhere in the list. The list will also quickly grow to very large sizes (200,000+ elements). Is there some class other than vector which might be better for this?

    Last but not least: Say I want to remove the 53rd element from a vector called bob. Must I say, bob.erase(bob.begin() + 53)?

    Thank you so much. This is really important to me.

  2. #2
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    Why not randomly arrange some sequence of indexes, and then reference down the line with operator[], or at()?
    For my ease I'll use rand() as offered in <cstdlib>, but I'd suggest using something else.
    Code:
    //for some std::vector<T> vec, that you wish to work on
    typedef std::vector<T>::size_type st;
    std::vector<st> indexes;
    st sz = vec.size();
    for(st x = 0; x < sz; ++x) indexes.push_back(x);
    
    std::srand(std::time(NULL));
    while(sz)
    {
        st pick = std::rand() &#37; sz;
        operate_on_vector(vec[indexes[pick]]);
        indexes.erase(indexes.begin() + pick);
        --sz;
    }
    That's a sloppy concept. But that's my idea, I guess.
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    102
    You might try the vector shuffle algorithm already in the iostream library:
    Code:
    #include <vector>
    #include <ctime>
    #include <cstdlib>
    #include <iostream>
    
    int main()
    {
    std::vector<int> Numbers;
    
    srand(time(0));  //Seed the Generator
    
    for(int x = 0; x <= 5; ++x)
        Numbers.push_back(x);
    
    std::random_shuffle(Numbers.begin(), Numbers.end());  //Re-Arranges the vector from begin to end.
    
    for (int x = 0; x < Numbers.size(); ++x)
        {
        //Apply algorithm of yours.
        }
    
    }
    Also you can use iterators or just access elements in the array by using the [] operator
    Code:
    Numbers[5] = 32;
    Will set the 5th element to 32. It is an expensive operation to perform however, so I don't recommend using it a lot.
    Last edited by JJFMJR; 07-31-2007 at 07:50 PM.
    My Favorite Programming Line:
    Code:
    #define true ((rand() % 2) ? true : false)

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Last but not least: Say I want to remove the 53rd element from a vector called bob. Must I say, bob.erase(bob.begin() + 53)?
    No, just provide an iterator to an item for erase. Since pointers can be iterators anything like this is okay.

    bob.erase( &bob.at( 53 ) );

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    You might try the vector shuffle algorithm already in the iostream library:
    std::random_shuffle() is from <algorithm>, not <iostream>, and is not limited to vectors but a range from a sequence.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> bob.erase( &bob.at( 53 ) );
    Actually I don't think this is correct. It is not any iterator that vector needs, it is a vector<T>::iterator (where T is the object type). And that is not necessarily a pointer.

    >> bob.erase(bob.begin() + 53)
    Yes, that is how you erase the 54th element from a vector.

    >> I need a list of elements, where I can add to the back of the list and remove from anywhere in the list.
    Start with vector, and if you find you are having performance problems then consider other containers. It really depends on how often you remove from the middle of the container compared to everything else. The inserting will be fast with vector, the shuffling will be fast with vector, and many other operations will be fast with vector, so the fact that removal from the middle can be slow may be outweighed by those other considerations.
    Last edited by Daved; 08-01-2007 at 11:36 AM. Reason: Cactus_Hugger's correction

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Actually I don't think this is correct. It is not any iterator that vector needs, it is a vector<T>::iterator (where T is the object type).
    That's an awfully odd comment considering some things. A pointer can otherwise become a vector<t>::iterator correct? They're very similar concepts so I'd be very surprised if that is wrong on any compiler that matters. Educate me please, because I've used pointers to objects with the STL just fine.

    And that is not necessarily a pointer.
    The address of a reference is not of type t* ?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    A pointer can otherwise become a vector<t>::iterator correct? They're very similar concepts so I'd be very surprised if that is wrong on any compiler that matters. Educate me please, because I've used pointers to objects with the STL just fine.
    The vector's iterator type is implementation defined, though from what I understand pointers are usually used since a vector's elements are stored contiguously.

    My gripe would be that you gave a "no, just provide an iterator to an item for erase" when Signifier's usage was correct in providing an iterator
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Say I want to remove the 53rd element from a vector called bob. Must I say, bob.erase(bob.begin() + 53)?
    >> bob.erase(bob.begin() + 53)
    Yes, that is how you erase the 53rd element from a vector.
    That'd erase the 54th element, would it not? bob.erase(bob.begin() + 0) is the 1st element, and so on. bob.erase(bob.begin() + 52) would erase the 53rd element.
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    >> A pointer can otherwise become a vector<t>::iterator correct?
    No, it cannot unless you are lucky enough for the implementation to have done it that way.

    For simplicity, we'll assume a vector<int>. The erase function takes a vector<int>::iterator as its parameter:
    Code:
    vector<int>::iterator vector<int>::erase(vector<int>::iterator pos);
    Let's say your vector implementation typedefs a class called VecIter as its iterator:
    Code:
    class VecIter
    {
    // ...
    };
    
    class vector
    {
    public:
        typedef VecIter iterator;
    // ...
    };
    So that means that erase takes a VecIter as its parameter:
    Code:
    VecIter vector<int>::erase(VecIter pos);
    Now, you are trying to pass a pointer to int to this function that takes a VecIter. But an int pointer is not a VecIter, so it will fail.

    I think what you are thinking of is the parameters taken by generic algorithms. These are templated types that are assumed to follow the traits of iterators. For example:
    Code:
    template <typename RandomAccessIter>
    sort(RandomAccessIter beg, RandomAccessIter end);
    The difference there is that sort takes any type as its parameters, and the template mechanism enforces that the type works as an iterator. However, the vector erase member function doesn't take any type, it takes a single specific type, whatever it typedef'd as iterator.

    Passing a pointer will work if and only if the vector implementation uses a pointer as its iterator:
    Code:
    class vector
    {
    public:
        typedef int* iterator;
    // ...
    };
    But since that is not guaranteed, you cannot and should not rely on it. There are compilers that don't use pointers as iterators. The best example I can think of is debug build implementations that store extra information to aid in debugging.

  11. #11
    Registered User
    Join Date
    Apr 2005
    Posts
    7
    Thank you everyone! I'm using the random_shuffle algorithm that JJFMJR mentioned. Cactus_hugger, you are right, vec.erase(vec.begin() + 53) removes the 54th element.

    One last question about vectors (I am new to the C++ standard): will going through the elements of a vector using iterators a la

    Code:
    vector<int> vec;
    for (int a = 0; a < 10; ++a) vec.push_back(a);
    
    vector<int>::iterator i = vec.begin();
    while (i != vec.end())
    {
        cout << *i << endl;
        i++;
    }
    be faster than

    Code:
    vector <int> vec;
    for (int a = 0; a < 10; ++a) vec.push_back(a);
    const int L = vec.size();
    
    for (int i = 0; i < L; ++i)
        cout << vec[i] << endl;
    ?

    Am I using iterators right (with the dereference)?

  12. #12
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    I wouldn't worry about the difference, it will likely not be noticable.

    You might consider using the iterator version if you think you might change to another type in the future. In fact, you can create a typedef for your vector like this:
    Code:
    typedef vector<int> int_container;
    Obviously you'd pick a name that makes sense in your program, but then you can use int_container everywhere you have vector<int> now. If you decide you want to see if using a list creates performance improvements, then switch the typedef to
    Code:
    typedef list<int> int_container;
    If you use the iterator version of your loop above then it will work automatically when you switch to list. The operator[] version would have to be re-written to work with a list, since lists dont' support operator[].

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. can some one please tell me the cause of the error ?
    By broli86 in forum C Programming
    Replies: 8
    Last Post: 06-26-2008, 08:36 PM
  2. syntax help?
    By scoobygoo in forum C++ Programming
    Replies: 1
    Last Post: 08-07-2007, 10:38 AM
  3. Vector class
    By Desolation in forum C++ Programming
    Replies: 2
    Last Post: 05-12-2007, 05:44 PM
  4. Need some help/advise for Public/Private classes
    By nirali35 in forum C++ Programming
    Replies: 8
    Last Post: 09-23-2006, 12:34 PM
  5. Certain functions
    By Lurker in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2003, 01:26 AM