std::vector iterator efficancy

**Gödel** · 04-02-2016

Hello,
I'm currently programming, as a sub-project, a voronoi diagram generator. In short, I roll a set of points stored as

Code:

std:: vector <std:: complex <float>> vertices

and then generate the Voronoi diagram accordingly. I've got the algorithm more or less down.

My question is: how much more effective is it to use

Code:

std:: vector< std :: complex <float> > :: iterator

opposed to using a simple

Code:

 for (int k=0; k < vertices. size; ++ k) { ...

the reason I ask is that I cannot do specific things with the vector iterator that I can do with the more classic

Code:

vertices  [k]. something

approach.

The following shows my two approaches, the first uses the vector iterator and the second code snippet uses a simple for loop.
(note: this is just the code for initializing the vertices as complex points on the plane.)

Code:

void Voronoi::InitVertices() {

    for ( int k = 0; k < vertices.size(); ++k ) {
        std::complex<float> dump( 0.f, 0.f );
        vertices.push_back( dump );
    }

        for ( std::vector<std::complex<float>>::iterator i = vertices.begin(); i != vertices.end(); ++i ) {
        bool checker = true;
        while ( checker ) {
            checker = false;
                for ( std::vector<std::complex<float>>::iterator j = vertices.begin(); j != vertices.end(); ++j ) {
                if ( ( point_distance( &(*i), &(*j) ) < MINIMUM_DIST ) && ( &(*i) != &(*j) ) ) {
                    (*i).real( std::rand() % RMW );
                    (*i).imag( std::rand() % RMH );
                    PrintPt( &(*i), true );
                    checker = true;
                    break;
                }
            }
        }
    }
}

Code:

void Voronoi::InitVertices2() {

    for ( int k = 0; k < vertices.size(); ++k ) {
        std::complex<float> dump(0.f,0.f);
        vertices.push_back( dump );
    }

    for ( int k = 0; k < vertices.size(); ++k ) {
    //for ( std::vector<std::complex<float>>::iterator i = vertices.begin(); i != vertices.end(); ++i ) {
        bool checker = true;
        while ( checker ) {
            checker = false;
            for ( int j = 0; j < vertices.size();++j ) {
            //for ( std::vector<std::complex<float>>::iterator j = vertices.begin(); j != vertices.end(); ++j ) {
                if ( ( point_distance( &vertices[k], &vertices[j]) < MINIMUM_DIST ) && ( (*k) != (*j) ) ) {
                    vertices[k].real( std::rand() % RMW );
                    vertices[k].imag( std::rand() % RMH );
                    PrintPt( &vertices[k], true );
                    checker = true;
                    break;
                }
            }
        }
    }
}

Now to the differences:
1) I cannot compare two

Code:

std:: vector <std:: complex<float>> iterator

with each other directly. My work-around is to instead check if the two iterators point to the same address, which is OK I guess but not something I particularly like.
2) When I do compare two vector iterators though, if the two std:: complex being compared have the same coordinates, lets say (0,0) then they will be seen as the same point. (which is not always wanted. Sometimes I need to differentiate between std:: complex's even if they have the same coordinates).

So, how bad is it if I use the normal for loop? Is there a better option for me?

to space,

M.

**MutantJohn** · 04-02-2016

Out of all the bottlenecks of a Voronoi generator, you're worried about a function called InitVertices?

**algorism** · 04-02-2016

Originally Posted by MutantJohn

Out of all the bottlenecks of a Voronoi generator, you're worried about a function called InitVertices?

It seems you didn't really read the question. He's using it as an (overly-complex for the purpose) example.

Actually, I don't see why he can't just compare the iterators, but I'm not a C++ expert so maybe there's some reason. Of course, in comparing the iterators he'd need to compare them as i == j and not *i == *j (that seems obvious, but his question makes me wonder if that's not the confusion).

**whiteflags** · 04-02-2016

My biggest complaint about that code is that it really feels like you don't know what you're doing with iterators, and that's one reason for you to prefer indexing, until you understand iterators better.

What iterators are supposed to do, particularly for vector, is mimic using a pointer to do a for loop over an array, i.e.

Code:

for (complex<float>* iter = array; iter != array + N; iter++)

Still, I'm surprised this compiles in the indexing version:

Code:

if ( ( point_distance( &vertices[k], &vertices[j]) < MINIMUM_DIST ) && ( (*k) != (*j) ) )

k and j aren't pointer types in this context!

And I'm not sure what you mean by "I cannot do specific things with the vector iterator that I can do with the more classic [for loop]" because, in spite of my complaints, it sure looks like you are using it okay. There are niggling things I would fix about the iterator version.

One of them is using arrow notation:

Code:

(*i).real( std::rand() % RMW );
(*i).imag( std::rand() % RMH );

// a.k.a
 i->real( std::rand() % RMW );
 i->imag( std::rand() % RMH );

And this:

Code:

 if ( ( point_distance( &(*i), &(*j) ) < MINIMUM_DIST ) && ( &(*i) != &(*j) ) ) 
// a.k.a
if ( point_distance( &*i, &*j ) < MINIMUM_DIST )

Note that &*i and &*j will generate pointers to complex<float> - so that is why I didn't change that. But you shouldn't need to compare the iterators i and j themselves. You can easily set it up so that they are never the same element.

Code:

 for (vector<complex<float>>::iterator i = vertices.begin(); i != vertices.end(); ++i)
// and
for (vector<complex<float>>::iterator j = vertices.begin() + 1; j != vertices.end() - 1; ++j)

**MutantJohn** · 04-02-2016

Originally Posted by algorism

It seems you didn't really read the question. He's using it as an (overly-complex for the purpose) example.

Actually, I don't see why he can't just compare the iterators, but I'm not a C++ expert so maybe there's some reason. Of course, in comparing the iterators he'd need to compare them as i == j and not *i == *j (that seems obvious, but his question makes me wonder if that's not the confusion).

To be entirely truthful, I'm kind of honestly surprised anyone who could legit code a Voronoi generator would not be able to answer this question themselves in the first place... I hope that doesn't sound mean but Voronoi diagrams are pretty non-trivial to program so asking a question about an iterator vs a pointer seems kind of fishy to me. How can you code something so massively complex but not reason about something so relatively basic...

But when I say that out loud, I think it makes me sound like a butt.

**whiteflags** · 04-02-2016

I tend to not make assumptions like that because I've been in situations where I have to do something legitimately hard while at the same time not being the most skilled at the language of choice.

**algorism** · 04-02-2016

Originally Posted by MutantJohn

Voronoi diagrams are pretty non-trivial to program so asking a question about an iterator vs a pointer seems kind of fishy to me.

Maybe he's a master Java programmer!

**MutantJohn** · 04-02-2016

Originally Posted by whiteflags

I tend to not make assumptions like that because I've been in situations where I have to do something legitimately hard while at the same time not being the most skilled at the language of choice.

That's fair. It's 100% fair. But by that same token, I assume you would also be able to read up on iterators in C++ and realize how to use them and how they would differ vs the use of raw pointers. Even then, there's also tons of tutorials about C++ out there.

Maybe the OP prefers to receive help from actual human beings which is fine but as someone who's coded Delaunay triangulations (the dual of the Vornoi diagram), I'm surprised the question is even being posed.

Which is why I said I feel like I sound like a butt because of how I'm acting.

**King Mir** · 04-02-2016

There is really not much difference between using indexes and iterators here. A third alternative is to use range base for loops. This requires c++11:

Code:

void Voronoi::InitVertices() {
 
    for ( int k = 0; k < vertices.size(); ++k ) {
        std::complex<float> dump( 0.f, 0.f );
        vertices.push_back( dump );
    }
 
    for ( auto & vertex1: vertices ) {
        bool checker = true;
        while ( checker ) {
            checker = false;
                for ( auto & vertex2 : vertices ) {
                if ( ( point_distance( &vertex1, &vertex2  ) < MINIMUM_DIST ) && ( &vrtex1 != &vrtex2  ) ) {
                    vertex1.real( std::rand() % RMW );
                    vertex1.imag( std::rand() % RMH );
                    PrintPt( &vertex1, true );
                    checker = true;
                    break;
                }
            }
        }
    }
}

You can totally compare iterators into the same vector directly. You can totally do i != j, for both vectors and indexes.

Also, your algorithm could use some work. For starters, this is an infinite loop:

Code:

    for ( int k = 0; k < vertices.size(); ++k ) {
        std::complex<float> dump( 0.f, 0.f );
        vertices.push_back( dump );
    }

In the second part, when you change a vertex that's too close to another, you don't check that the new position is too close to any other point.

Thread: std::vector iterator efficancy

Thread Tools

Search Thread

Display

std::vector iterator efficancy

Similar Threads

Using an iterator with a vector of objects

Problem with vector iterator

vector and iterator problem

Vector Iterator Help

std::vector iterator problems

Tags for this Thread