Adding elements to a vector

[Theeper]

If I have a struct like this ..

struct Stuff {
int stuff_id;
int red;
int blue;
int green;
};

and I make a vector of 'Stuff'...

vector<Stuff> vStuff;

and then create an object to pushback elements onto it ..

Stuff s;
s.blue = 255;
vStuff.push_back(s);

.. it works fine. But if I want to set the index manually and make it the same as 'stuff_id' is, I assume I need to use something like ..

vStuff.at(index).stuff_id = index;

I know that's not right, but I'm not sure of the syntax.

[Bazzy]

Why don't you use a map instead of a vector, with a map you can choose the index of the elements

[Theeper]

I think vectors are more efficient than maps in the situation I am using them. They will be loaded once and accessed many times. I was hoping there was a similar way to insert into a vector like you do a map.

[Theeper]

I overlooked it but earlier, I see vectors do have an insert function. Now to figure out how to use it with structs.

[jsmith]

Theeper: your statement does not say one way or another whether vector is more efficient than map in your case. Why do you need to store the index of the element as part of the struct?

struct Stuff {
   Stuff() : stuff_id( 0 ), red( 0 ), blue( 0 ), green( 0 ) {}
   Stuff( int r, int g, int b, int id = 0 ) : stuff_id( id ), red( r ), green( g ), blue( b ) {}

   int stuff_id;
   int red;
   int green;
   int blue;
};

vector<Stuff> vStuff;

vStuff.push_back( Stuff( 0, 0, 255, vStuff.size() ) );

If you are planning to use vector's insert() functions as opposed to vector's push_back() function, then there is absolutely no way vector is a better choice than map, because every insert into a vector that is not at the end incurs a complete reallocation of the underlying array and every element already in the array has to be copied.

[satm2008]

As jsmith noted, yes, using insert() for vector is not a good idea if it is to be invoked very frequently.
Unlike the push_back() the insert() may insert a new element at any position in the vector which is very time-intensive and too-much overhead if there are frequent insertions. Coming to performance, worse.
In such case, I would go for std::list that allows to insert anywhere but not much overhead, and better than map and vector.

For better performance and faster search reasons, I would avoid a map in my designs.

Check it out. Good luck :)

[jsmith]

Um, maps have O(log N) lookups and lists have O(N). How exactly is a list faster for searches??

[satm2008]

maps use hashing technique which is not so recommended option for better performance and duplicate elements.
It would be tricky and not easy to maintain, rather I would use a leaner search method for such faster search and random access.

May be a quick look at the following link would give you better explanation of it.
http://en.wikipedia.org/wiki/Hash_table

Compared to vector, a list offers faster insertions and deletions, though it is bit slower in accessing the elements randomly.


Check it out. Good luck :)

[jsmith]

maps by default use std::less which calls operator< which need not do any hashing at all. In the example above, if ids are at least semi-unique then operator< for Stuff can be implemented to check ids first and in most cases a single integer comparison will be all that is needed, and you won't get any faster than that.

struct Stuff {
  // ...

  bool operator<( const Stuff& rhs ) const
     { if( stuff_id < rhs.stuff_id ) return true;
       if( rhs.stuff_id < stuff_id ) return false;
       if( red < rhs.red ) return true;
       if( rhs.red < red ) return false;
       if( green < rhs.green ) return true;
       if( rhs.green < green ) return false;
       return blue < rhs.blue;
    }
};

maps do not allow for insertion of duplicates. multimap does.

There is very, very, very little programmer maintenance needed.

[satm2008]

As per my knowledge maps implement/use hashing technique and that is why I said I would avoid using a map.

Not sure how the std::map works, but for a faster search I would recommend other linear or better methods.

Good luck :)