Strings in Vectors. and placing them in order

Question

So I am placing objects in a vector. I want to drop them in order as they are added. the basics of the object are

class myObj  {
  private:
     string firstName;
     string lastName;
  public:
     string getFirst;
     string getLast;    
}

I also have a vector of these objects

vector< myObj > myVect;
vector< myObj >::iterator myVectit = myVect.begin();  

when I add a new object to the vector I want to find where it should be placed before inserting it. Can I search a vector by an object value and how? This is my first attempt

void addanObj (myObj & objtoAdd){
  int lowwerB = lower_bound(
                myVect.begin().getLast(), myVect.end().getLast(), objtoAdd.getLast()
                );
  int upperB = upper_bound(
               myVect.begin().getLast(), myVect.end().getLast(), objtoAdd.getLast()
               );

from there i plan to use lowwerB and upper B to determine where to insert the entry. what do I need to do to get this to work or what is a better method of tackling this challenge?

----Follow up----

the error I get when I attempt to compile

 error C2440: 'initializing' : cannot convert from 'std::string' to 'int'
 No user-defined-conversion operator available that can perform this conversion, 
 or the operator cannot be called

The compiler highlights both lower_bound and upper_bound. I would guess it is referring to where I am putting

objtoAdd.getLast()

-----More Follow up----------------- THis is close to compiling but not quite. What should I expect to get from lower_bound and upper_bound? It doesnt match the iterator i defined and im not sure what I should expect.

void addMyObj(myObj myObjtoadd)
    vector< myObj>::iterator tempLB;
    vector< myObj>::iterator tempUB;
    myVectit= theDex.begin();
    tempLB  = lower_bound(
              myVect.begin()->getLast(), myVect.end()->getLast(), myObjtoadd.getLast()
              );
    tempUB = upper_bound(
             myVect.begin()->getLast(), myVect.end()->getLast(), myObjtoadd.getLast()
             );

Answer 1

Your calls to std::lower_bound and std::upper_bound are incorrect. The first two parameters must be iterators that define a range of elements to search and the returned values are also iterators.

Since these algorithms compare the container elements to the third parameter value you'll also need to provide correct operator< functions that compare an object's lastName and a std::string. I've added two different compare functions since std::lower_bound and std::upper_bound pass the parameters in opposite order.

I think I have the machinery correct in this code, it should be close enough for you to get the idea.

class myObj {
    private:
        std::string firstName;
        std::string lastName;
    public:
        std::string getFirst() const { return firstName; }
        std::string getLast() const { return lastName; }
};

bool operator<(const myObj &obj, const std::string &value) // used by lower_bound()
{
    return obj.getLast() < value;
}

bool operator<(const std::string &value, const myObj &obj) // used by upper_bound()
{
    return value < obj.getLast();
}

int main()
{
    std::vector<myObj> myVect;
    std::vector<myObj>::iterator tempLB, tempUB;
    myObj objtoAdd;

    tempLB = std::lower_bound(myVect.begin(), myVect.end(), objtoAdd.getLast());
    tempUB = std::upper_bound(myVect.begin(), myVect.end(), objtoAdd.getLast());
}

Answer 2

So this is definitely not the best way to go. Here's why:

Vector Size

A default vector starts out with 0 elements, but capacity to hold some number; say 100. After you add the 101st element, it has to completely recreate the vector, copy over all the data, and then delete the old memory. This copying can become expensive, if done enough.

Inserting into a vector

This is going to be even more of a problem. Because a vector is just a contiguous block of memory with objects stored in insert order, say you have the below:

[xxxxxxxzzzzzzzz            ]

if you want to add 'y', it belongs between x and z, right? this means you need to move all the z's over 1 place. But because you are reusing the same block of memory, you need to do it one at a time.

[xxxxxxxzzzzzzz z           ]
[xxxxxxxzzzzzz zz           ]
[xxxxxxxzzzzz zzz           ]
...
[xxxxxxx zzzzzzzz           ]
[xxxxxxxyzzzzzzzz           ]

(the spaces are for clarity - previous value isn't explicitly cleared)

As you can see, this is a lot of steps to make room for your 'y', and will be very very slow for large data sets.

A better solution

As others have mentioned, std::set sounds like it's more appropriate for your needs. std::set will automatically order all inserted elements (using a tree data structure for much faster insertion), and allows you to find particular data members by last name also in log(n) time. It does this by using bool myObj::operator(const & _myObj) const to know how to sort the different objects. If you simply define this operator to compare this->lastName < _myObj.lastName, you can simply insert into the set much quicker.

Alternately, if you really really want to use vector: instead of sorting it as you go, just add all the items to the vector, and then perform std::sort to sort them after all the inserts are done. This will also complete in n log(n) time, but should be considerably faster than the current approach because of the vector insertion problem.