vector or list ---> confused

[vermarajeev]

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

[JosAH]

Also I want to randomly access the atoms, to test certain conditions.

The magic phrase here is "random access"; so use a vector.

kind regards,

Jos

[vermarajeev]

The magic phrase here is "random access"; so use a vector.

kind regards,

Jos

Dont you think using a vector in the above scenario is a big waste of memory though is helps me to "randomly access" the elements?

Thanks

[JosAH]

Dont you think using a vector in the above scenario is a big waste of memory though is helps me to "randomly access" the elements?

Thanks

Nope, a vector doesn't contain a fixed number of elements, e.g. if you have a
vector containing 68 elements the vector will take up more memory than a
vector containing just 2 elements; vectors aren't fixed size arrays.

kind regards,

Jos

[vermarajeev]

   ______________________
  |___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".

[JosAH]

   ______________________
  |___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".

When you use vectors for that, there are no 68 or 20 wasted spaces, i.e. a
vector grows on demand. A vector is not like a statically sized array.

kind regards,

Jos

[weaknessforcats]

When you use vectors for that, there are no 68 or 20 wasted spaces, i.e. a
vector grows on demand. A vector is not like a statically sized array.

Actually, I think it is a statically sized array. I believe vector must be implemented as an array. It;s just that when the vector needs to expand, a larger array is allocated and a copy occurs. That is, this must work for a vector:

[code=cpp]
vector<int> v;
v.push_back(10) ;
int * ptr = &v[0];
*ptr = 20; //changes the 10 to a 20
[/code]

[kreagan]

Why are you concerned about memory? (Just wondering) Is your program running sluggish or eating too much memory?

According to the articles below, vectors reserve a chunk of memory. Where as reserving the memory is a "waste of space" and theoretically the List would conserve more memory. However, memory management isn't perfect and deallocating and allocating memory can create fragmented memory. This can result in wasted memory also. I would suggest looking at the data structure with the best functionality until memory becomes an issue.

Anyways, here's some links to read about Vectors and Linked Lists:
http://www.cplusplus.c om/reference/stl/vector/
http://www.cplusplus.c om/reference/stl/list/

"Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists."

"Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position;"

[JosAH]

Actually, I think it is a statically sized array. I believe vector must be implemented as an array. It;s just that when the vector needs to expand, a larger array is allocated and a copy occurs. That is, this must work for a vector:

[code=cpp]
vector<int> v;
v.push_back(10) ;
int * ptr = &v[0];
*ptr = 20; //changes the 10 to a 20
[/code]

Nope, just suppose you're doing another push_back afterwards: this is what I
ripped from the STL documentation:

Reallocations invalidate all previously obtained iterators, references and pointers.

Those arrays used by vectors are resized whenever necessary. They don't have
a fixed size (that's a better phrase for it than 'statically sized' which I used previously).

kind regards,

Jos

[weaknessforcats]

Reallocations invalidate all previously obtained iterators, references and pointers.

True. But until then, the vector is a fixed array. After the push_back() there may (or may not) have been allocated a new array. While the pointers and interators may have been invalidated, the vector still contains an array.

[JosAH]

True. But until then, the vector is a fixed array. After the push_back() there may (or may not) have been allocated a new array. While the pointers and interators may have been invalidated, the vector still contains an array.

Yep, I never argued against that ;-) All I say is that that array may be reallocated
and the size will be different after that reallocation. Any decent implementation
'minimizes the overhead' of unused array elements, so I advised the OP to use
a vector for his/her purposes.

kind regards,

Jos