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.

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.

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.

Quote:

---

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 ) );

Quote:

---

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.

>> 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.

Quote:

---

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.

Quote:

---

And that is not necessarily a pointer.

---

The address of a reference is not of type t* ?

Quote:

---

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

Quote:

---

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

---

Quote:

---

>> 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.

>> 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.

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)?

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[].