-3

I came through a program which was like below

firstMissingPositive(vector<int> &A) {
    vector<bool> dict(A.size()+1,false);

    for(int i=0;i<A.size();i++){
            if(A[i]>0 && A[i]<dict.size()) dict[A[i]]=true;
    }

    if(A.size()==1 && A[0]!=1) return 1;
    else if(A.size()==1 && A[0]==1) return 2;

    int i=0;
    for(i=1;i<dict.size();i++){
        if(dict[i]==false) return i;
    }
    return i;
}

In this program, I could not get what is mean by following line

          vector<bool> dict(A.size()+1,false);

What is dict and this statement?

dlmeetei
  • 9,905
  • 3
  • 31
  • 38
Deepak Sharma
  • 67
  • 1
  • 9

3 Answers3

3

It's simply a variable.

The definition of the variable calls a specific constructor of the vector to initialize it with a specific size, and initialize all elements to a specific value.

It's equivalent to

vector<bool> dict;
dict.resize(A.size()+1,false);

See e.g. this std::vector constructor reference for more information about available constructors.

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
1

You are declaring container of bool's (it means variables which stores only 0/1 (8B)) which has same count of elements as int vector A and all these elements are set to false -> 0.

It calls this constructor

 vector (size_type n, const value_type& val,
       const allocator_type& alloc = allocator_type());

Example:

This is vector A:

  0   1   2   3   4    <- Indexes
+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 |     (int)
+---+---+---+---+---+

Its size is 5, so it would declare container with size 5, initialized to 0's.

  0   1   2   3   4    <- Indexes
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |     (bool)
+---+---+---+---+---+

In this case its used to flag indexes in first vectror.

For example it is often used for Sieve of Eratosthenes. You can set 1's to primes with each iteration. It would be (for numbers 0-4)

  0   1   2   3   4
+---+---+---+---+---+
| 0 | 0 | 1 | 1 | 0 |
+---+---+---+---+---+

Then you know on which indexes are primes in vector A.

for (int i = 0; i < A.size(); i++)
{
    if ( dict[i] == true )
    {
        std::cout << "Prime number: << A[i] << std::endl;
    }
}
kocica
  • 6,412
  • 2
  • 14
  • 35
1

It is an definition of a variable "dict" of type vector. And please Google it first

user123456
  • 65
  • 1
  • 9