Most efficient way to find an entry in a C++ vector

Question

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 <iostream>
#include <iomanip>
#include <cmath>
#include <string.h>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

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

    uint8_t tableNum;
    uint8_t randomCount;
    srand(time(NULL));
    for( tableNum=0; tableNum < 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 < 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;
}

Answer 1

Header files

It's strange that this code uses the C header <string.h> but the C++ versions of <cmath>, <ctime> and <cstdlib>. 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 <cstring>, so we can probably just drop that, along with <iomanip>, <iostream> and <cmath>. And we need to add some missing includes: <cstdint> and <cstdio>.

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 < 20;  ++i) {
    std::uint8_t randomCount = rand() % 80;
    m_availTableNums.push_back(randomCount);
}

for (std::uint8_t i = 0;  i < 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 < 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<bool>(LIMIT, false);
for (auto value: m_availTableNums)
    by_val[value] = true;

for (std::uint8_t i = 0;  i < 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<bool>. We might also choose vector<char> instead of vector<bool> 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 <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <vector>

int main()
{
    constexpr std::uint8_t LIMIT = 80;
    std::vector<std::uint8_t> m_availTableNums;

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

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

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

    auto by_val = std::vector<bool>(LIMIT, false);
    for (auto value: m_availTableNums)
        by_val[value] = true;

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

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

Answer 2

I would seriously consider whether std::vector is the right data structure. Do you need the available table numbers to be in the order you got them, or can they be sorted? Do you need to allow duplicate table numbers? (I.e. if I add 42 twice, do I have one entry for 42 or two?)

If the data can be sorted and de-duplicated, then the most efficient way to find an entry is to store the data in a std::set. Storing the data takes a little longer (O(log n) for the set vs. amortized O(1) for the vector), but finding the data makes up for it (O(log n) for the set vs. O(n) for the vector). If you use a set, make sure to use set's find function (e.g. mySet.find(tableNum) rather than std::find(mySet.begin(),mySet.end(),tableNum)), or there's no benefit.

On a more general code-style note, since you're using C++ data structures anyway, you should probably use std::string and std::cout instead of char */char[] and printf.

Answer 3

A std::set or std::bitset might be the better containers to use for this, but assuming we're going to stick with std::vector, here's some improvements on this.

See Toby Speight's answer for some of the improvements I used but did not cover.

Avoid using unsigned numbers

Don't use unsigned int or uint8_t. Counterintuitively, it's generally best to use signed int types even when a value should never be negative. Operations on mixed signed types come with a lot of problems. It's an unfortunate mistake the standard went with unsigned numbers for container sizes. Unsigned numbers are best kept to bitwise operations.

Store whether an index is used at that index

Instead of storing a list of indexes that have been used, let's just store a bool at each possible index. This uses more space, but then no extra searching has to be done, just a single loop. (Notice I've changed m_availTableNums to availTableNums. The prefix m_ is conventionally only used for class members).

std::vector<bool> availTableNums (80);

Putting the 80 here will initialize the vector with 80 false values. Now when we fill the table, we choose random indices to insert true which indicates a value of used.

std::srand(std::time(nullptr));
for(int i=0; i < 20; i++)
{
    availTableNums[std::rand() % availTableNums.size()] = true;
}

Using modern RNG facilities

std::rand has no guarantees of the "randomness" of the numbers it generates. It's fine if you want to run up a quick test, but in production code we could modify the previous example to make it a little more robust.

std::default_random_engine engine {std::time()};
std::uniform_int_distribution<std::size_t> uniform_dist {0, availTableNums.size()};
for(int i=0; i < 20; i++)
{
    availTableNums[uniform_dist(e1)] = true;
}

Here we use std::size_t, even though it's an unsigned type, as it is better to not have to cast from one type to another if we could avoid it. The random number generator will automatically pick from the correct range so we no longer need the modulus operator.

Use C++ string streams

There is no need for a temporary string, and C++ streams are often a better choice than the C printf family of functions. We can write the header of the table as:

std::cout << "+-------+-------+\n"
          << "| TABLE | STATE |\n"
          << "+-------+-------+" << std::endl;

The extra <<s are left for style but not necessary. Now for the printing inside the loop, use std::setw(2) to make sure the printed index is within 2 columns. The value of this resets if string is sent to std::cout so it will not effect the rest of the line.

The use of std::endl will cause the output to always be flushed from the buffer and will have a small performance penalty. However, I am usually quite generous with them unless it is shown they have a sizeable impact on performance. It can make code easier to debug if output is consistently flushed and you know exactly where something went wrong.

for(auto i=0u; i < availTableNums.size(); i++)
{
    std::cout << "|  " << std::setw(2) << i << "   | "
              << (availTableNums[i] ? "USED " : "EMPTY")
              << " |" << std::endl;
}

We again choose an unsigned index as comparing two unsigned types is better than comparing mixed signs or casting one to the other. The conditional expression ?: allows us to concisely choose between the two strings depending on whether the index is true or false.

---

Putting it all together with only the relavent headers, we get:

#include <ctime>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>


int main()
{
    std::vector<bool> availTableNums (80);

    std::default_random_engine engine {std::time()};
    std::uniform_int_distribution<std::size_t> uniform_dist {0, availTableNums.size()};
    for(int i=0; i < 20; i++)
    {
        availTableNums[uniform_dist(e1)] = true;
    }

    std::cout << "+-------+-------+\n"
              << "| TABLE | STATE |\n"
              << "+-------+-------+" << std::endl;

    for(auto i=0u; i < availTableNums.size(); i++)
    {
        std::cout << "|  " << std::setw(2) << i << "   | "
                  << (availTableNums[i] ? "USED " : "EMPTY")
                  << " |" << std::endl;
    }

    std::cout << "+-------+-------+" << std::endl;

    return 0;
}

Answer 4

The above are good advice. Do you need exactly N values true? If so, the above loop might be better as (pieces left out for simplicity):

const std::size_t N = 80;
const std::size_t K = 20;

std::unordered_set<std::size_t> exists;

// Fill exists with K random values between [0 .. N], inclusive.
std::default_random_engine rng{std::time()};
std::uniform_int_distribution<std::size_t> uniform_dist {0, N};
while (exists.size() < K) {
  exists.insert(uniform_dist(rng));
}

// Print each value in order, in a table.
for(auto i = uniform_dist.min(); i <= uniform_dist.max(); ++i) {
    std::cout << "|  " << std::setw(2) << i << "   | "
              << ((exists.count(i) == 0) ?  "EMPTY" : "USED ")
              << " |" << std::endl;
}