vector or list?

[Jacko123]

Hi guys,
I know what a vector and a list is?

I have this scenario and I want to know which will be best to use.

I have a class called "molecule". The maximum number of atoms a molecule can hold is 72. The number of atoms vary depending on the type of molecule, it can be 4 or 10 or 1 or 50 etc etc...upto maxatoms.

Hence, since the maximum number of atoms is fixed i.e 72, and for current molecule if the number of atoms is only 4, there are 68 vacant space empty.
A big "waste of space".
Also I want to randomly access the atoms, to test certain conditions.
Currently I use vector<molecule> but I think using vector can help me randomly access the atoms but eats up more memory. Dont you think?

So what do you think can be best "vector/list" for above discussed scenario.

Thanks in advance

[laserlight]

You should use a vector<atom>. If there are only 4 atoms in the molecules, just have a vector of 4 elements. If there are 72 atoms, then have a vector of 72 elements.

[Jacko123]

You should use a vector<atom>. If there are only 4 atoms in the molecules, just have a vector of 4 elements. If there are 72 atoms, then have a vector of 72 elements.

Did you mean something like this

class molecule;
class atom
{
	int numatoms;
public:
	atom(){numatoms = 0;}
	friend class molecule;
};

class molecule
{
    vector<atom> m_atoms;	
	public:
		molecule()
        {}
		void setAtoms(int i);	
};
void molecule::setAtoms(int i)
{	
	atom* atm = new atom;
	atm->numatoms = i ;
	m_atoms.push_back( *atm );
}

int main()
{
	vector<molecule> m_molecules;
	int totalMol = 4;
	molecule* mol = new molecule[totalMol];	
	for(int i=0; i<totalMol; ++i)
	{
		mol->setAtoms( (i+1)*4 );  //some random values
		m_molecules.push_back( *mol );
	}	
	return 0;
}

[laserlight]

From what I understand, you have a molecule class. Each molecule has a positive number of atoms, up to a maximum of 72 atoms. I do not see the point of a numatoms member variable for the atom class since an atom object represents exactly one atom. You could have such a member variable in the molecule class, but it is made redundant by the size() member function of the molecule's vector of atoms.

Looking at your main() function, are you perhaps confusing atoms and molecules?

[Jacko123]

Here is the code with comments. The relationship is a "molecule has atoms"
Please modify the code below to express what you mean.
Thanks

class molecule;
class atom
{	
public:
	atom(){}
	friend class molecule;
};

class molecule
{ 
	int no_of_atoms;
	public:
		molecule()
                {
			no_of_atoms = 0; 
		}
		void setAtoms(int i);	
};
void molecule::setAtoms(int i)
{	
	//create atom objects. If suppose this molecule has 
	//4 atoms, these 4 atoms can have different properties.
	//Hence I create atom objects and use it accordingly to 
	//compute or assign some values
	atom* atm = new atom[i];
}

int main()
{
	vector<molecule> m_molecules;
	int totalMol = 4;
	molecule* mol = new molecule[totalMol];	//there are 4 types of molecules
	for(int i=0; i<totalMol; ++i)
	{
		//Each molecule is made of atoms, The number of atoms can be any.
		//For number of atoms I take some random values 
		mol->setAtoms( (i+1)*4 );  //some random values
		m_molecules.push_back( *mol );
	}	
	//use m_molecules for other cases
	return 0;
}

[laserlight]

Here is the code with comments. The relationship is a "molecule has atoms"
Please modify the code below to express what you mean.

Sounds like homework to me...

I might create the classes like:

class atom
{
public:
    atom();
    // other member functions to work with the atom's properties
    // ...
private:
    // properties of the atom
    // ...
};

class molecule
{
public:
    molecule();
    void setNumAtoms(int num);
    // other member functions to work with the molecule's atoms
    // ...
private:
    std::vector<atom> atoms;
};

Then to use them, my main() function may be like:

int main()
{
    size_t totalMol = 4; // there are 4 molecules of possibly different types
    vector<molecule> molecules(totalMol);

    for (size_t i = 0; i < totalMol; ++i)
    {
        molecules[i].setNumAtoms((i + 1) * 4); // some "random" number of atoms
    }

    // use molecules for other cases
    // ...

    return 0;
}

[Jacko123]

Infact this is not a homework.
You defined the class but where are you making using of vector of atoms "atoms"?

Can you please tell me how would you define "setNumAtoms" function?

[Paul McKenzie]

Here is the code with comments. The relationship is a "molecule has atoms"

Your class does not show his relationship. Instead, it (IMO) unnecessarily creates a friend class. Atom does nothing with molecule, so why are you making molecule a friend of atom? As a matter of fact, what does the "Atom" class do?

Second, it seems lately that a lot of posters think C++ is Java, and they don't need to worry about calling "delete" or delete[] in their code, this post not withstanding. Your code has memory leaks all over the place.

Third, you use vector, but then you don't use it for other things that vector was created for. There is no need to do new[]/delete[] in any of your code -- instead, just use vector.

Fourth, your main() function makes no sense to me. You are creating a vector of molecules, then creating another "array" of molecules, and then assigning this array to the vector? First, as mentioned in my third point, there is no need for new[]/delete[], since vector is supposed to take care of this for you. But in general, your main() function looks very confused.

Did you try to model this? The very first thing "A molecule has atoms" wasn't even modeled correctly with what you initially did. Here is the way I would interpret what you're trying to do.

#include <vector>
class atom
{	
public:
	atom(){}
};

class molecule
{ 
   std::vector<atom> theAtoms;

   public:  
        molecule()  {}
        void setAtoms(int i);	
        int getNumberOfAtoms() const { return theAtoms.size(); }
};

void molecule::setAtoms(int i)
{	
     theAtoms.resize(i);
}

Regards,

Paul McKenzie

[laserlight]

You defined the class but where are you making using of vector of atoms "atoms"

You would need to provide suitable member functions in the molecule class to access individual atoms in the molecule. My code snippet merely uses the setNumAtoms() member function to resize the vector of atoms.

Can you please tell me how would you define "setNumAtoms" function?

Refer to the implementation of setAtoms() in Paul McKenzie's code example. Frankly, I think setAtoms() is a poor name for setting the number of atoms unless you are copying from an existing collection of atoms, hence I suggest a rename to setNumAtoms().

[Jacko123]

Ok, I have one more question.

When I use vectors, is there really wasted spaces. Doesnt a vector grows on demand.
I got this while goggling.
"A vector is not like a statically sized array."

Thanks

[Paul McKenzie]

Ok, I have one more question.

When I use vectors, is there really wasted spaces. Doesnt a vector grows on demand.

First, what do you mean by "wasted space"? Second, it grows depending on what you placed in there. You are in control of the number or items placed in vector.

"A vector is not like a statically sized array."

This means that a vector can grow, unlike an array which stays fixed.

What if you started out with 10 items, and later on, this needs to be increased to 20 items? How would you do that with an array? Look at the function I wrote that sets the number of atoms. A single call to resize(). It can't get any simpler than that.

Regards,

Paul McKenzie

[sunnypalsingh]

vector< > uses contiguous memory to store its elements. vector automatically grabs a chunk of memory(say 256 Kbytes) and puts all the data into this memory.When you keep adding data, you will run out of the 256 bytes.So vector gets another 512 Kbytes of contiguous memory and copies the data from its first 256 Kbytes and adds the new data after that..Eventually the 512 Kbytes will also be exhausted and there will be one more allocation and a copy.
All these can be avoided if you know the approximate size of the vector you need.Reserve your vector with the memory it needs, so that it will not need any allocation or copy till the reserved meory is used up. So you almost get the efficiency of the 'C' style array but still have the flexibility to add more elements as needed.

[Jacko123]

Here is what I meant

         _____________________
        |___mol1____|__mol2____|         
                |            |
                |            |
                |            |
                |            |____________________                             
                |            |_1_|_2_|_3_|_.....|_72__|  
             _  |__________________
            |_1_|_2_|_3_|_.....|_72__|

Assume there are two molecules mol1, mol2.
mol1 has allocated space for maxatoms 72, and mol2 has allocated space for maxatoms 72.
Just think mol1 is actually a molecule having only 4 atoms and mol2 is actually a molecule having only 52 atoms. Dont worry about how or why just assume.

Now, dont you think 68 spaces are wasted in case of mol1 and 20 spaces in case of mol2 ?
This was my question. Hence, can you now tell me using a vector is better or a list?
Since list is a doubly linked list, I think using a list should save up memory. But on the other hand I cannot use subscripts to access data "randomly".

[laserlight]

Assume there are two molecules mol1, mol2.
mol1 has allocated space for maxatoms 72, and mol2 has allocated space for maxatoms 72.
Just think mol1 is actually a molecule having only 4 atoms and mol2 is actually a molecule having only 52 atoms. Dont worry about how or why just assume.

Now, dont you think 68 spaces are wasted in case of mol1 and 20 spaces in case of mol2 ?
This was my question. Hence, can you now tell me using a vector is better or a list?

You say: assume that you waste memory. Then you state: dont you think that wastes memory?

So, of course you waste memory!

Since list is a doubly linked list, I think using a list should save up memory. But on the other hand I cannot use subscripts to access data "randomly".

A list would not help:

Assume there are two molecules mol1, mol2.
mol1 has allocated space for maxatoms 72, and mol2 has allocated space for maxatoms 72.
Just think mol1 is actually a molecule having only 4 atoms and mol2 is actually a molecule having only 52 atoms. Dont worry about how or why just assume.

Now, dont you think 68 spaces are wasted in case of mol1 and 20 spaces in case of mol2 ?

See? It is the same whether you use a vector or a list. A vector will still be better as you can access the elements faster.

[Paul McKenzie]

Here is what I meant

You are the one setting these sizes of 72, not vector. If you decide to allocate 72 items, then that is your doing, not vectors. You have *total* control of how many items a vector uses up.

Regards,

Paul McKenzie