Most efficient way to find an entry in a C++ vector I'm trying to construct an output table containing 80 rows of table status, that could be EMPTY or USED as below

+-------+-------+
| TABLE | STATE |
+-------+-------+
|  00   | USED  |
|  01   | EMPTY |
|  02   | EMPTY | 
..
..
|  79   | EMPTY |
+-------+-------+


I have a vector m_availTableNums which contains a list of available table numbers. In the below example, I'm putting 20 random table numbers into the above vector such that all the remaining 60 would be empty. My logic below works fine. 

Is there a scope for improvement here on the find logic?

#include &lt;iostream&gt;
#include &lt;iomanip&gt;
#include &lt;cmath&gt;
#include &lt;string.h&gt;
#include &lt;cstdlib&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;ctime&gt;

using namespace std;

int main(int argc, const char * argv[]) {
    std::vector&lt;uint8_t&gt; m_availTableNums;
    char tmpStr[50];

    uint8_t tableNum;
    uint8_t randomCount;
    srand(time(NULL));
    for( tableNum=0; tableNum &lt; 20; tableNum++ )
    {
        randomCount = ( rand() % 80 );
        m_availTableNums.push_back( randomCount );
    }

    sprintf(tmpStr, "+-------+-------+");
    printf("%s\n", tmpStr);
    tmpStr[0]='\0';

    sprintf(tmpStr, "| TABLE | STATE |");
    printf("%s\n", tmpStr);
    tmpStr[0]='\0';

    sprintf(tmpStr, "+-------+-------+");
    printf("%s\n", tmpStr);

    tableNum = 0;
    for( tableNum=0; tableNum &lt; 80 ; tableNum++ )
    {
        tmpStr[0]='\0';
        if ( std::find(m_availTableNums.begin(), m_availTableNums.end(), tableNum) != m_availTableNums.end() )
        {
            sprintf(tmpStr, "|  %02d   | EMPTY |", tableNum );
        } else {
            sprintf(tmpStr, "|  %02d   | USED  |", tableNum );
        }

        printf("%s\n", tmpStr);
    }

    tmpStr[0]='\0';
    sprintf(tmpStr, "+-------+-------+");
    printf("%s\n", tmpStr);

    return 0;
}
Header files

It's strange that this code uses the C header &lt;string.h&gt; but the C++ versions of &lt;cmath&gt;, &lt;ctime&gt; and &lt;cstdlib&gt;.  I recommend sticking to the C++ headers except on the rare occasions that you need to compile the same code with a C compiler.  In this case, I don't see anything using &lt;cstring&gt;, so we can probably just drop that, along with &lt;iomanip&gt;, &lt;iostream&gt; and &lt;cmath&gt;.  And we need to add some missing includes: &lt;cstdint&gt; and &lt;cstdio&gt;.

Avoid using namespace std

The standard namespace is not one that's designed for wholesale import like this.  Unexpected name collisions when you add another header or move to a newer C++ could even cause changes to the meaning of your program.

Use the appropriate signature for main()

Since we're ignoring the command-line arguments, we can use a main() that takes no parameters:

int main()


Remove pointless temporary string

Instead of formatting into tmpStr and immediately printing its contents to standard output, we can eliminate that variable by formatting directly to standard output (using the same format string).  For example, instead of:


std::sprintf(tmpStr, "+-------+-------+");
std::printf("%s\n", tmpStr);
tmpStr[0]='\0';

std::sprintf(tmpStr, "| TABLE | STATE |");
std::printf("%s\n", tmpStr);
tmpStr[0]='\0';

std::sprintf(tmpStr, "+-------+-------+");
std::printf("%s\n", tmpStr);



we could simply write:

std::puts("+-------+-------+\n"
          "| TABLE | STATE |\n"
          "+-------+-------+");


And instead of


    tmpStr[0]='\0';
    if ( std::find(m_availTableNums.begin(), m_availTableNums.end(), tableNum) != m_availTableNums.end() )
    {
        std::sprintf(tmpStr, "|  %02d   | EMPTY |", tableNum );
    } else {
        std::sprintf(tmpStr, "|  %02d   | USED  |", tableNum );
    }

    printf("%s\n", tmpStr);



we would have:

    if (std::find(m_availTableNums.begin(), m_availTableNums.end(), tableNum) != m_availTableNums.end()) {
        std::printf("|  %02d   | EMPTY |\n", tableNum);
    } else {
        std::printf("|  %02d   | USED  |\n", tableNum);
    }


Reduce duplication

Most of these statements are common:


        std::printf("|  %02d   | EMPTY |\n", tableNum);
    } else {
        std::printf("|  %02d   | USED  |\n", tableNum);
    }



The only bit that's different is the EMPTY or USED string.  So let's decide that first:

    const char *status =
        std::find(m_availTableNums.begin(), m_availTableNums.end(), tableNum) != m_availTableNums.end()
        ? "EMPTY" : "USED";
    std::printf("|  %02d   | %-5s |\n", tableNum, status);


Prefer nullptr value to NULL macro

The C++ null pointer has strong type, whereas NULL or 0 can be interpreted as integer.

Reduce scope of variables

randomCount doesn't need to be valid outside the first for loop, and we don't need to use the same tableNum for both loops.  Also, we could follow convention and use a short name for a short-lived loop index; i is the usual choice:

for (std::uint8_t i = 0;  i &lt; 20;  ++i) {
    std::uint8_t randomCount = rand() % 80;
    m_availTableNums.push_back(randomCount);
}




for (std::uint8_t i = 0;  i &lt; 80;  ++i) {


Avoid magic numbers

What's special about 80?  Could we need a different range?  Let's give the constant a name, and then we can be sure that the loop matches this range:

constexpr std::uint8_t LIMIT = 80;
...
    std::uint8_t randomCount = rand() % LIMIT;
...
for (std::uint8_t i = 0;  i &lt; LIMIT;  ++i) {


A departure from specification

The description says


  I'm putting 20 random table numbers into the above vector such that, all the remaining 60 would be empty.


That's not exactly what's happening, as we're sampling with replacement from the values 0..79.  There's nothing to prevent duplicates being added (it's actually quite unlikely that there will be exactly 60 empty values).

Reduce the algorithmic complexity

Each time through the loop, we use std::find() to see whether we have any matching elements.  This is a linear search, so it examines elements in turn until it finds a match.  Since it only finds a match one-quarter of the time, the other three-quarters will examine every element in the list, and the time it takes will be proportional to the list length - we say it scales as O(n), where n is the size of the vector.  The complete loop therefore scales as O(mn), where m is the value of LIMIT.

We can reduce the complexity to O(m + n) if we use some extra storage to store the values in a way that makes them easy to test.  For example, we could populate a vector that's indexed by the values from m_availTableNums:

auto by_val = std::vector&lt;bool&gt;(LIMIT, false);
for (auto value: m_availTableNums)
    by_val[value] = true;

for (std::uint8_t i = 0;  i &lt; LIMIT;  ++i) {
    const char *status = by_val[i] ? "EMPTY" : "USED";
    std::printf("|  %02d   | %-5s |\n", i, status);
}


If the range were much larger, we might use an (unordered) set instead of vector&lt;bool&gt;.  We might also choose vector&lt;char&gt; instead of vector&lt;bool&gt; for better speed at a cost of more space.



Simplified code

Here's my version, keeping to the spirit of the original (creating a list of indices, rather than changing to storing in the form we want to use them):

#include &lt;algorithm&gt;
#include &lt;cstdint&gt;
#include &lt;cstdio&gt;
#include &lt;cstdlib&gt;
#include &lt;ctime&gt;
#include &lt;vector&gt;

int main()
{
    constexpr std::uint8_t LIMIT = 80;
    std::vector&lt;std::uint8_t&gt; m_availTableNums;

    std::srand(std::time(nullptr));

    for (std::uint8_t i = 0;  i &lt; 20;  ++i) {
        std::uint8_t randomCount = rand() % LIMIT;
        m_availTableNums.push_back(randomCount);
    }

    std::puts("+-------+-------+\n"
              "| TABLE | STATE |\n"
              "+-------+-------+");

    auto by_val = std::vector&lt;bool&gt;(LIMIT, false);
    for (auto value: m_availTableNums)
        by_val[value] = true;

    for (std::uint8_t i = 0;  i &lt; LIMIT;  ++i) {
        const char *status = by_val[i] ? "EMPTY" : "USED";
        std::printf("|  %02d   | %-5s |\n", i, status);
    }

    std::puts("+-------+-------+");
}