check if a variable is inside a set of values

Hi

I wanted to know if there was a way to check if a variable was inside a set of values.

Like in the below given example, I want to know if n1 is either 5, 8, 27 or 2567
Is there a better way to do it than just using "if statement" ?

Code:

---

#include <iostream>

int main()
{
    int n1;

    if(n1 == 5 || n1 == 18 || n1 == 27 || n1 == 2567) //Is there a better way of achieving this
        std :: cout << "good\n";
    else
        std :: cout << "bad\n";

    return(0);
}

---

Thanks,
Muthu

Yes, there are many ways: the if/else or the switch statement, these two are for a small number of values.
But if you have a big number of values use an array or std::vector to store values and a function to search.

well as far as i see not really,

the thing you have now is ok for this amount of numbers, if you had more like 20 or something you could use an array or like Zlatomir said std::vector and using a loop check all the values inside the array/vector

If your values are iterable, then std::find should do just fine. If you plan on doing this search many times, you can sort your elements, and use std::binary_search for increased performance.

The simplest option would be to use an std::map though.

Quote:

---

or like Zlaand using a loop check all the values inside the array/vector

---

No need for a loop in this case -- just use std::find().

Regards,

Paul McKenzie

Thank you so much for all your replies.

I had this vague view that there was a function called "any" ... hahah .. I was so wrong.

I suppose std :: find would suit my needs.

Thanks all
Muthu

If the set of numbers you're checking changes often, then use a std::set. If it does not, then use a sorted vector with std::binary_search.

If it's a constant set of numbers, use a switch.

Code:

---

switch (n){
    case 5:
    case 18:
    case 27:
    case 2567:
          std::cout << "good" << std::endl;
          break;
    default:
          std::cout << "bad" << std::endl;
          break;
}

---

Quote:

---

Originally Posted by Muthuveerappan

I had this vague view that there was a function called "any"

---

Any is a keyword in Cobol and in SQL, not in C/C++.

Anyway, you can have something shorter and quicker than

Code:

---

    if(n1 == 5 || n1 == 18 || n1 == 27 || n1 == 2567)
        std :: cout << "good\n";
    else
        std :: cout << "bad\n";

---

With:

Code:

---

    if (t[n1] == 'Y')
        std :: cout << "good\n";
    else
        std :: cout << "bad\n";

---

But this requires a few lines of initialization:

Code:

---

char t[3000];
memset(t, 'N', sizeof(t));
t[5] = t[18] = t[27] = t[2567] = 'Y';

---

That strikes me as potentially dangerous since you could end up trying to read an invalid location. Not as big a deal as writing one, but who knows, there could be a 'Y' there.

The O(log n) options I outlined above are pretty good. Using a hash table is another option, but serious overkill unless the number of values you're checking is large, eg, over a thousand.

Quote:

---

Originally Posted by Lindley

That strikes me as potentially dangerous since you could end up trying to read an invalid location. Not as big a deal as writing one, but who knows, there could be a 'Y' there.

The O(log n) options I outlined above are pretty good. Using a hash table is another option, but serious overkill unless the number of values you're checking is large, eg, over a thousand.

---

If you are only looking for a range of integral values "existence" or "flag", you can use a bit array to store the "boolean bit flags", there's no need for a full blown hash table.

Code:

---

class CBitArray
{
public:
        CBitArray(unsigned long dwMinValue,unsigned long dwMaxValue);
        ~CBitArray();

        bool IsValueBitSet(unsigned long dwValue) const throw(std::exception);
        void SetValueBit(unsigned long dwValue,bool bValue) throw(std::exception);

        static CBitArray * CreateFromVector(const std::vector<unsigned long> & vValues);
protected:
        unsigned long m_dwMinValue;
        unsigned long m_dwMaxValue;
        unsigned long m_dwRangeSize;

        unsigned char * m_pData;
        unsigned long & m_dwBitCount; // refers to m_dwRangeSize
        unsigned long m_dwByteCount;
};

CBitArray::CBitArray(unsigned long dwMinValue,unsigned long dwMaxValue) : m_dwMinValue(dwMinValue),
        m_dwMaxValue(dwMaxValue),m_dwRangeSize(dwMaxValue - dwMinValue + 1),m_pData(0),m_dwBitCount(m_dwRangeSize),
        m_dwByteCount(0)
{
        m_dwByteCount = m_dwBitCount >> 3;

        if (m_dwBitCount & 7)
        {
                ++m_dwByteCount;
        }

        m_pData = new unsigned char[m_dwByteCount];

        for (unsigned long i = 0; i < m_dwByteCount; ++i)
        {
                m_pData[i] = 0;
        }
}

CBitArray::~CBitArray()
{
        if (m_pData != 0)
        {
                delete [] m_pData;
        }
}

bool CBitArray::IsValueBitSet(unsigned long dwValue) const throw(std::exception)
{
        bool bValueSet = false;

        if (dwValue < m_dwMinValue || dwValue > dwValue)
        {
                std::exception e("Value out of range.");

                throw(e);
        }

        const unsigned long dwTempValue = dwValue - m_dwMinValue;
        const unsigned long dwByteIndex = dwTempValue >> 3;
        const unsigned long dwBitIndex = dwTempValue & 7;
        const unsigned char ucBitMask = 1 << dwBitIndex;

        bValueSet = ( m_pData[dwByteIndex] & ucBitMask) != 0 ;

        return bValueSet;
}

void CBitArray::SetValueBit(unsigned long dwValue,bool bValue) throw(std::exception)
{
        if (dwValue < m_dwMinValue || dwValue > m_dwMaxValue)
        {
                std::exception e("Value out of range.");

                throw(e);
        }

        const unsigned long dwTempValue = dwValue - m_dwMinValue;
        const unsigned long dwByteIndex = dwTempValue >> 3;
        const unsigned long dwBitIndex = dwTempValue & 7;
        const unsigned char ucBitMask = 1 << dwBitIndex;

        if (bValue == true)
        {
                m_pData[dwByteIndex] |= ucBitMask;
        }
        else
        {
                m_pData[dwByteIndex] &= ~ucBitMask;
        }
}

CBitArray * CBitArray::CreateFromVector(const std::vector<unsigned long> & vValues)
{
        CBitArray * pObject = 0;
        unsigned long dwMinValue = 0xFFFFFFFF;
        unsigned long dwMaxValue = 0;

        std::vector<unsigned long>::const_iterator it = vValues.cbegin();
        std::vector<unsigned long>::const_iterator end = vValues.cend();

        while (it != end)
        {
                const unsigned long dwTempValue = *it;

                if (dwTempValue < dwMinValue)
                {
                        dwMinValue = dwTempValue;
                }

                if (dwTempValue > dwMaxValue)
                {
                        dwMaxValue = dwTempValue;
                }

                ++it;
        }

        pObject = new CBitArray(dwMinValue,dwMaxValue);

        it = vValues.cbegin();
        end = vValues.cend();

        while (it != end)
        {
                pObject->SetValueBit(*it,true);
                ++it;
        }

        std::cout << "The minimum value is: " << dwMinValue << " The max value is " << dwMaxValue << std::endl;

        return pObject;
}

int wmain(int argc, wchar_t * argv[])
{
        std::vector<unsigned long> arValues;

        std::cout << "Enter the amount of numbers you wish to enter: ";

        unsigned long dwCount = 0;

        std::cin >> dwCount;

        if (dwCount != 0)
        {
                unsigned long dwValue = 0;

                for (unsigned long i = 0; i < dwCount; ++i)
                {
                        std::cout << "Enter the number: ";
                        std::cin >> dwValue;

                        arValues.push_back(dwValue);
                }

                CBitArray * pBitArray = CBitArray::CreateFromVector(arValues);

                std::cout << "Can you remember one of those numbers? Enter one: ";
                std::cin >> dwValue;

                try
                {
                        if (pBitArray->IsValueBitSet(dwValue) == true)
                        {
                                std::cout << "That was one of the numbers you entered." << std::endl;
                        }
                        else
                        {
                                std::cout << "That was not one of the numbers you entered." << std::endl;
                        }
                }
                catch(const std::exception & e)
                {
                        std::cout << "Exception: " << e.what() << std::endl;
                }

                system("pause");

                delete pBitArray;
        }

        return 0;
}

---

True, but no need to write your own; a std::bitset will work fine. (If you need to make it dynamic, then a std::vector<bool> will serve, although you should prefer a boost::dynamic_bitset if you have access to Boost.)

The set/hash set options become more appealing when the range of possible values is large.

Quote:

---

Originally Posted by Lindley

If the set of numbers you're checking changes often, then use a std::set. If it does not, then use a sorted vector with std::binary_search.

---

IIRC std::set is usually implemented as a binary search tree, so would using a vector offer any real advantage? Especially considering how much uglier it is to write "std::binary_search(myVec.begin(), myVec.end(), value)" everywhere as compared to "mySet.count(value)".

Quote:

---

Originally Posted by Speedo

IIRC std::set is usually implemented as a binary search tree, so would using a vector offer any real advantage? Especially considering how much uglier it is to write "std::binary_search(myVec.begin(), myVec.end(), value)" everywhere as compared to "mySet.count(value)".

---

I'm just echoing Effective STL here. Since a vector stores all the values in one place, looking something up in it with binary_search is going to be much more cache-efficient than in a std::set, unless your particular STL implementation takes steps to ensure that nodes in a single container are usually close together in memory.

If you need a "sorted vector" container, ie, a set with an array implementation, no need to write your own:

http://www.codeproject.com/KB/stl/sorted_vector.aspx

I've never tried it, so I can't grantee how good it is, but I doubt it's bad.

According to the article, a sorted_vector out performs a set for search operations by a factor of two (as explained by Meyers and echoed by Lindley).

The downside is the o(n) complexity on insertions.

Sounds like it's just syntactic sugar wrapping the vector/algorithm approach. Still, keeping the interface consistent is a nice touch since it would make timing the speed difference between the approaches similar.

I'd imagine that inserting everything via the set interface would be O(n^2 lg n). However, as stated in the link, you can use the "low level interface" (read: underlying vector push_back) to insert everything in O(n lg n) by only doing the sort once at the end rather than on every insertion.

Quote:

---

Originally Posted by Lindley

Sounds like it's just syntactic sugar wrapping the vector/algorithm approach.

---

Well it's kinda like a priorty_queue. All it does is wrap another container, and provide a modified interface for a specific use.

So yeah, syntactic sugar, but that's what we're asking for.

Quote:

---

Originally Posted by Lindley

I'd imagine that inserting everything via the set interface would be O(n^2 lg n). However, as stated in the link, you can use the "low level interface" (read: underlying vector push_back) to insert everything in O(n lg n) by only doing the sort once at the end rather than on every insertion.

---

You are probably right, I didn't do a full study of that container. but as said previously, the goal of such a container is really to be filled only once, and then never touched again. So being able to optimize that phase is just the cherry on the cake :).

PS. If you know what you are doing, you could fill it in o(n) by using insertion with hint. That would require the input being pre-sorted, but not an impossible assumption. But again, who cares?