S>Это слишком примитивное мышление. Нужно рассмотреть не 1 случай а множество вариантов, в т.ч. создание списка и поиск по хеш-коду. Там нужно сотни разных тестов провести, прежде чем сделать вывод.
Вариант на хэштаблицах имеет нулевую разницу, 40+-1 миллисекунд:

#include <unordered_set>
#include <vector>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define USE128

static void randfill(void *p, size_t l)
{
    for (;l >= 2; l-= 2) {
        *(unsigned short *)p = rand();
        p = (char *)p + 2;
    }
    for (;l >= 1; l--) {
        *(unsigned char *)p = rand();
        p = (char *)p + 1;
    }
}

#ifdef USE128
struct Value
{
    uint64_t v1;
    uint64_t v2;
    Value()
    {
        randfill(&v1, sizeof(v1));
        randfill(&v2, sizeof(v2));
    }
    bool operator <(const Value &other) const
    {
        if (v1 != other.v1)
            return v1 < other.v1;

        return v2 < other.v2;
    }
    bool operator ==(const Value &other) const
    {
        return v1 == other.v1 && v2 == other.v2;
    }
};

struct ValueHash
{
    size_t operator()(const Value &v) const
    {
        return v.v1;
    }
};

#else
struct Value
{
    uint64_t v;
    Value()
    {
        randfill(&v, sizeof(v));
    }
    bool operator <(const Value &other) const
    {
        return v < other.v;
    }
    bool operator ==(const Value &other) const
    {
        return v == other.v;
    }
};

struct ValueHash
{
    size_t operator()(const Value &v) const
    {
        return v.v;
    }
};

#endif

int main(int argc, char **argv)
{
    srand(123);
    std::unordered_set<Value, ValueHash> values;
    std::vector<Value> lookup;
// generating addresses out of time measurements scope
    for (unsigned long i = 0; i < 10000000; ++i) {
        auto ir = values.emplace();
        if ((i % 32) == 0) {
            lookup.emplace_back(*ir.first);
            if ((i % 4) == 0) {
                lookup.emplace_back();
            }
        }
    }
    unsigned long found = 0;

    struct timespec ts1 = {0};
    clock_gettime(CLOCK_MONOTONIC, &ts1);
    for (const auto &v : lookup) {
        if (values.find(v) != values.end()) {
            found++;
        }
    }
    struct timespec ts2 = {0};
    clock_gettime(CLOCK_MONOTONIC, &ts2);
    unsigned long msec = (unsigned long)((ts2.tv_sec - ts1.tv_sec) * 1000);
    msec+= (unsigned long)(ts2.tv_nsec / 1000000);
    msec-= (unsigned long)(ts1.tv_nsec / 1000000);

    printf("found %lu time %lu msec\n", found, msec);
}