CODEWITHSUNDEEP
c++
Pentium10
Pentium10

Reputation: 207912

how to search properly the vector for a value

The problem I have, I have to add to a vector, the missing chars. For example I have initially

s,a,p,i,e,n,t,i,a

and I have to add missing chars to it
s,a,p,i,e,n,t,i,a,b,c,d ...

I am trying to use this code to search for an existing value.

for(char c='a';c!='z';++c)
    {
        if (vec.end()!=find(vec.begin(),vec.end(),c))
            vec.push_back(c);
    }

The find returns last when it fails to locate a value. But how do I know if last value was in it?

EDIT

When the for loop starts, for 'a' returns vec.end() so it should not go in, but goes in, and adds 'a' again in the end.

See this in debugger alt text http://img203.imageshack.us/img203/2048/bb1f.jpg

(The bug I have, the value in last position gets inserted twice, I have to omit this)

Upvotes: 1

Views: 424

Answers (8)

James
James

Reputation: 25523

If you need to find a value in your container, then the greatest likelihood is that you need to use a different sort of container, where searching is fast!

Have a Look at this very useful diagram by Adrinael: Container Choice (Adrinael)
(source: adrinael.net)

(In your case I believe std::set is probably the most appropriate)

Upvotes: 1

Manuel
Manuel

Reputation: 13109

What others have answered is true but you should also change the termination condition in your for loop to c <= 'z' if you want the letter z to be included in your list.

EDIT I can't help adding that with the Boost.RangeEx library your problem can be solved with a one-liner:

boost::set_difference(boost::counting_range('a', char('z' + 1)),
                      std::set<char>(vec.begin(), vec.end()), 
                      std::back_inserter(vec));

Upvotes: 2

Eric
Eric

Reputation: 19863

you can start by sorting the vector

in this way you will notice instantly for gaps in the sequence

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main(int argc, char** argv)
{
   vector<char> original;

   original.push_back('a');
   original.push_back('d');
   original.push_back('x');
   original.push_back('j');
   original.push_back('z');

   sort(original.begin(), original.end());

   vector<char> unseen_chars;
   char current_char = 0;
   char last_char = original[0];

   for (int i = 1; i <= original.size(); i++)
   {
      current_char = original[i];
      for ( char j = last_char + 1; j < current_char; j++)
      {
         unseen_chars.push_back(j);
      }

     last_char = current_char;
   }
   for (int i = 0; i < unseen_chars.size(); i++)
   {
      cout << unseen_chars[i];
   }
   cout << endl;

Upvotes: 0

stefanB
stefanB

Reputation: 79810

You want to insert the character into array if it is NOT found, when it == end.

You are checking if it != end so you insert characters when they are already found in the string. See this:

char v[] = "acef";
vector<char> str(v,v+sizeof(v));

copy(str.begin(), str.end(), ostream_iterator<char>(cout, ","));

cout << endl;

for (char c = 'a'; c < 'g'; ++c)
{
    vector<char>::iterator it = find(str.begin(),str.end(), c);
    if (it == str.end())
    {
        str.push_back(c);
    }
}

copy(str.begin(), str.end(), ostream_iterator<char>(cout, ","));

output:

a,c,e,f,,
a,c,e,f,,b,d,

The extra empty character ,, is the null in the original string "acef" - null terminated.

Upvotes: 0

Daniel Daranas
Daniel Daranas

Reputation: 22624

In your case it's best to:

  1. Create one vector(bool), with indexes from 'a' to 'z' ,initialize it to false, (i)
  2. Run once through your original vector, set true in the other vector the element for each character that you find,
  3. Run once through this new vector and for each false value, append the corresponding char to the original.

(i) You may use actual_index = character - 'a'. Put some assertions here and there so that you don't crash for characters outside the range you are checking, presumably 'a' to 'z' (which by the way is not a strict definition of what a char is).

With just one initialization, two steps linear steps and no searches, you'll be done.

Upvotes: 3

user231967
user231967

Reputation: 1975

Nope, end() is not the last element of the vector but past it. To iterate over all elements you normally do

for(it= vec.begin(); it!= vec.end(); it++) ...

So whatever your problem is, this is ok.

Upvotes: 1

Tim Yates
Tim Yates

Reputation: 5291

vec.end() returns an iterator whose position is past the last element in the vector. If it matches on the last value, the returned iterator will not be equal to vec.end().

Upvotes: 0

Naveen
Naveen

Reputation: 73443

When find succeeds it returns iterator which is pointing to the found position. So if the value is in the vector then the return value will be something other that vec.end(). The condition inside the if condition should be == and not != if you are trying to create vector of unique characters.

Upvotes: 1

Related Questions