I've been trying to get my head round C++ vectors (not the one for movement in 2D/3D space!) as a way of managing the data structures for a GUI system I'm working on, but I could use some advice on whether I stick with the methods I've been using or advance to pointers and iterators - I've done a lot of research online, but I'm not really any the wiser on how these things actually work.
In my project, I create each form with a unique ID (verified in a separate method), and always add it to the vector "Form" such that the vector is always sorted by the "iFormID" parameter. I frequently have to find the vector index of a particular FormID, so I've implemented my own binary search through the array.
Header file:
#include <vector>
struct FormStruct
{
int iFormID;
int iFormType;
};
std::vector <FormStruct> Form;
Main cpp file:
#include <vector>
#include "Form.h"
int FindFormIndex(int FormID)
{
int High = Form.size();
int Low = 0;
int Mid = 0;
while(High>=Low)
{
Mid = (High+Low)/2;
if (Form[Mid].iFormID == FormID)
{
return Mid;
}
else
{ if (Form[Mid].iFormID < FormID)
Low = Mid + 1;
else
High = Mid - 1;
}
}
return -1;
}
Firstly, I'm concerned about the line "int high = Form.size();", because Form.size() returns a value of type t_Size and I'm not sure if it's valid to assign it to an int (although the code compiles fine). I was hoping to use iterators, but then I'm not sure if this is valid:
int FindFormIndex(int FormID)
{
std::vector<FormStruct>::iterator High = Form.end();
std::vector<FormStruct>::iterator Low = Form.begin();
std::vector<FormStruct>::iterator Mid = Form.begin();
while(High>=Low)
{
Mid = (High+Low)/2;
if ((*Mid).iFormID == FormID)
{
return (Mid - Form.begin());
}
else
{ if ((*Mid).iFormID < FormID)
Low = Mid + 1;
else
High = Mid - 1;
}
}
return -1;
}
The line "Mid = (High+Low)/2;" triggers a compiler error, as you can't add two iterators - so how do I find the Mid-point of the vector to continue the search? Also, is the comparison "while(High>=Low)" a valid statement? Is it even worthwhile advancing to iterators even if I can get this working? (I'm not sure quite what advantages they would bring)
I have found some references to the library <algorithms>, which provides a binary search method - it reqires iterators for the start and end of the search range in the vector, but it only returns true or false to state whether the specified ID exists. Is there any way to access the position (either an iterator or array index) of the entry? And if the requested form does not exist, can you get the index of where you should insert the form to keep all the iFormID variables running in numerical order (that is, the vector is always sorted)?
Sorry, for all of the questions, but I'm really out of my depth here - any help would be gratefully appreciated!
We spend our lives chasing dreams. Dark Basic lets us catch some of them.
