DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 25

Thread: Bitset constructor

  1. #1
    Join Date
    Jan 2005
    Posts
    42

    Bitset constructor

    Hi everyone,

    I am stuck with a very silly problem while using the bitset container of C++.While declaring a bitset,to specify the number of bits in the bitset we have to use an integer constant.

    so if i want to use a variable number for the bit size there are compilation errors
    :(

    for e.g; std::bitset<num> comb();
    I want this num to be variabke rather than a constant integer.Is there any way around this??

    Thanks a lot in advance.

    Regards

    tdas

  2. #2
    Join Date
    Nov 2003
    Posts
    4,118
    Quote Originally Posted by tdas
    Hi everyone,

    I am stuck with a very silly problem while using the bitset container of C++.While declaring a bitset,to specify the number of bits in the bitset we have to use an integer constant.

    so if i want to use a variable number for the bit size there are compilation errors
    :(

    for e.g; std::bitset<num> comb();
    I want this num to be variabke rather than a constant integer.Is there any way around this??

    Thanks a lot in advance.

    Regards

    tdas
    Not really. Templates in general impose certain restrictions on their arguments, when these arfuments are non-types (i.e., values). A non-type argument must be a constant, which means that you have two options: either use a hard-coded value, say 32 or a constant such as

    const int BITS=32;

    Using an ordinary variable is impossible because the template is only a mold from which a concrete class is generated at compile time. The argument must therefore be known at compile time too.
    Danny Kalev

  3. #3
    Join Date
    Jul 2005
    Posts
    26
    Templates generate code statically at compile-time, so they can not be instantiated with runtime variables, not even with constant values.

    Note that std::vector is also specialized for bool, maybe you can use this.

  4. #4
    Join Date
    Nov 2003
    Posts
    4,118
    vector<bool> could work but the main problem with it is this: it doesn't support the bitwise functionality (say bit shift operators, conversion to bitstring representation).
    Danny Kalev

  5. #5
    Join Date
    Jan 2005
    Posts
    42
    Thanks a lot guys,

    Actually I needed to find out all possible combination of n tokens in binary...so I thought i might use the bitset to get all the 2^n combinations but the number of tokens being variable I had some problems using bitset.Hence thought of writing up a UDF to convert all the decimal numbers from 0->(2^n-1) to binary and hence get the possible combinations.It works fine but I am not sure about the performance.I thought of using the vector<bool> / bit_vector but it didn't support the functionality to convert the number to binary like bitset.

    Thanks once again for ur time and help.

    Regards

    tdas

  6. #6
    Join Date
    Jul 2005
    Posts
    26
    Consider using std::vector<bool> with std::next_permutation(BidIt,BidIt).

  7. #7
    Join Date
    Nov 2003
    Posts
    4,118
    Quote Originally Posted by Oliver
    Consider using std::vector<bool> with std::next_permutation(BidIt,BidIt).
    I didn't want to state the other reason why vector<bool> might not be an ideal choice, but here it is:
    I doubt that you can use STL algorithms with vector<bool>, at least as far as C++98 vector is concerned. The main problem is that vector<bool> stores bits, which aren't an addressable datatype. This means that you can't create iterators that point to individual bits, at leats no directly. Since STL algorithms syc as nex_permutation rely on iterators, this is a real problem. That's why members of the C++ standards committee proposed more than once that vector<bool> should be removed from the Standard.
    Danny Kalev

  8. #8
    Join Date
    Jul 2005
    Posts
    26
    Quote Originally Posted by Danny
    I doubt that you can use STL algorithms with vector<bool>, at least as far as C++98 vector is concerned. The main problem is that vector<bool> stores bits, which aren't an addressable datatype. This means that you can't create iterators that point to individual bits, at leats no directly.
    I have no problems using it. Why shouldn't you be able to write an iterator that adresses bits (although it might be slower)?
    Code:
    	typedef std::vector<bool> tboolvec;
    
    	tboolvec vec;
    	vec.push_back(true );
    	vec.push_back(true );
    	vec.push_back(false);
    
    		for (tboolvec::const_iterator cit = vec.begin(); cit != vec.end(); ++cit)
    		{
    			std::cout << (*cit ? "true  " : "false ");
    		}
    But there is another problem with next_permutation I initially overlooked:
    next_permutation
    No two elements may have equivalent ordering.
    bummer.

    Apart from this, it all depends. What I understand from the OP was that he used a bitset to make the permutation:
    Quote Originally Posted by tdas
    Actually I needed to find out all possible combination of n tokens in binary...so I thought i might use the bitset to get all the 2^n combinations but the number of tokens being variable I had some problems using bitset.Hence thought of writing up a UDF to convert all the decimal numbers from 0->(2^n-1) to binary and hence get the possible combinations.
    Well, unfortunately it won't work with vector<bool> and next_permutation because at least two or more values have equivalent ordering (for n>1 probably, for n>2 guaranteed).


    But here's another idea (concerning the permutation): use a vector<int> with values that designate the bit state indices. Let's say for 32 bits you push_back([0..31]). You can then permutate the vector<int> with next_permutation(BidIt,BidIt). For each permutation, you can use the vector<int> as a lookup table for whatever bit you want to access, say, in a bitset. Just added a level of indirection.

  9. #9
    Join Date
    Nov 2003
    Posts
    4,118
    I'm not saying that it's impossible to design as a special case, iterators that operate on bits but it's not going to be an easy task, to say the least. Remmeber that you need to support the overloaded * and -> as well. Similary, certain STL operations such as reallocating and raw memory copying can't handle indvidual bits, they must operate on addressable datattypes so you would need to adjust them as well, which isn't really worth the trouble.
    The problem is not whether bit iterators are feasible. With a lot of effort and sacrifice, they are. However, they simply don't exist in C++98. This problem with vector <bool> was discovered only after the ratification of the Standard so we're stuck with a very probelamtic specialization called vetcor<bool>. There are some innovative proposals for C++0x that address in a generic fashion the problem of bit iterators. They look promising and pretty efficient but I don't know when and if they will make it into C++.
    Danny Kalev

  10. #10
    Join Date
    Jul 2005
    Posts
    26
    Quote Originally Posted by Danny
    The problem is not whether bit iterators are feasible. With a lot of effort and sacrifice, they are. However, they simply don't exist in C++98.
    Maybe I do not understand you correctly: Is the code in my last post not standard conforming? Why does it actually work (at least on MSVS6)?

  11. #11
    Join Date
    Nov 2003
    Posts
    4,118
    It works because your compiler treats vector<bool> as literally, a vector of bool's, not as a vector of bits. Many compilers use this workaround to overcome the serious problems associated with vector<bool>. But this doesn't really solve the problem because the aim of adding the std::vector<bool> was indeed to allow programmers to create a vector of bits, not bytes.

    BTW, there's another problem with vector<bool>: size() and capacity() report the wrong results. These functions weren't designed to count bits, needless to say. The more I look into it I'm more convinced that vector<bool> is a can of worms. I believe that a better approach would have been to create a special class called bit_vector that has nothing to do with vector. Then again even that class wouldn't have been STL compatible...
    Last edited by Danny; 07-29-2005 at 03:06 AM.
    Danny Kalev

  12. #12
    Join Date
    Jul 2005
    Posts
    26
    Quote Originally Posted by Danny
    It works because your compiler treats vector<bool> as literally, a vector of bool's, not as a vector of bits.
    Indeed, you're right: VC6 does not have a specialization of vector<bool>. I never peeked into the STL implementation code of vector, and this issue seems not to be documented in the MSDN...

    But the VC6 implementation offers a specialization of vector<_Bool, _Bool_allocator>. I've never used this one, although a quick test and stepping through the code revealed that this specialization seems to work with bits:
    Code:
    	typedef std::vector<std::_Bool, std::_Bool_allocator> t_Boolvec;
    
    	t_Boolvec vec_Bool;
    
    	vec_Bool.push_back(true );
    	vec_Bool.push_back(false);
    	vec_Bool.push_back(true );
    
    	assert(vec_Bool.size() == 3); // well, size is 3.
    	assert(vec_Bool.capacity() == 32); // capacity is 32 bits.
    
    	for (t_Boolvec::const_iterator cit = vec_Bool.begin(); cit != vec_Bool.end(); ++cit)
    	{
    		std::cout << (*cit ? "true  " : "false ");
    	}
    Can you please elaborate in which cases size() and capacity() return false values? Or what algorithms will probably not work with this implementation?

    Well, it'd really good to know such things about my favorite compiler...


    PS: Hope that we do not get too much off-topic.

  13. #13
    Join Date
    Nov 2003
    Posts
    4,118
    Quote Originally Posted by Oliver
    Indeed, you're right: VC6 does not have a specialization of vector<bool>. I never peeked into the STL implementation code of vector, and this issue seems not to be documented in the MSDN...

    But the VC6 implementation offers a specialization of vector<_Bool, _Bool_allocator>. I've never used this one, although a quick test and stepping through the code revealed that this specialization seems to work with bits:
    Code:
    	typedef std::vector<std::_Bool, std::_Bool_allocator> t_Boolvec;
    
    	t_Boolvec vec_Bool;
    
    	vec_Bool.push_back(true );
    	vec_Bool.push_back(false);
    	vec_Bool.push_back(true );
    
    	assert(vec_Bool.size() == 3); // well, size is 3.
    	assert(vec_Bool.capacity() == 32); // capacity is 32 bits.
    
    	for (t_Boolvec::const_iterator cit = vec_Bool.begin(); cit != vec_Bool.end(); ++cit)
    	{
    		std::cout << (*cit ? "true  " : "false ");
    	}
    Can you please elaborate in which cases size() and capacity() return false values? Or what algorithms will probably not work with this implementation?
    Well, it'd really good to know such things about my favorite compiler...


    PS: Hope that we do not get too much off-topic.
    It certainly isn't OT. This forum is meant to host this very type of discussions:)


    As for the previous question regarding size and capacity: Normally, these member functions return the number of objects, allowing you to do something like:
    vec[vec.size()-1]; //obtain the last element.

    If they report the number of bits, most other algorithms and classes that operate on addressable elements (i.e., any datatype with size(T)=1 or higher) might incur undefined behavior. This means that the implementation must completely rewire every STL concept such as adaptors, iterators, overaloded operators, sequence mutating algorithms and so on to make this code work.

    Generally speaking, every element type of an STL container must meet the following requirements: it must be copy-constructible, assignable, and have an associated < operator. A single bit doesn't meet the first two criteria as far as I know, so any usage of STL algorithms with a container of bits might cause undefined behavior. To add to the confusion, Visual C++ 6.0 is way behind C++98 with respect to its core language and Standard Library compliance. For more information about the problems of vector<bool> see :http://www.gotw.ca/publications/N1211.pdf
    Last edited by Danny; 07-29-2005 at 09:03 PM.
    Danny Kalev

  14. #14
    Join Date
    Jul 2005
    Posts
    26
    Quote Originally Posted by Danny
    it must be copy-constructible, assignable, and have an associated < operator. A single bit doesn't meet the first two criteria as far as I know, so any usage of STL algorithms with a container of bits might cause undefined behavior.
    From what I've seen, the VC6 implementation uses a wrapper object.

    Quote Originally Posted by Danny
    To add to the confusion, Visual C++ 6.0 is way behind C++98 with respect to its core language and Standard Library compliance.
    Oh boy, I can tell you about that! I get "INTERNAL COMPILER ERROR" very often when I work with templates, and I really miss some features like member function templates. Unfortunately, my workgroup currently sticks with VC6...

    Quote Originally Posted by Danny
    For more information about the problems of vector<bool> see :http://www.gotw.ca/publications/N1211.pdf
    Thanks for the article. I know the GOTW of Herb Sutter, although I seem to have left out this article (among others).

  15. #15
    Join Date
    Nov 2003
    Posts
    4,118
    The bottom line is this:

    Code:
    template<class T>
    void g( vector<T>& v ) 
    {
     T& r = v.front();
    // ...
    } 
    
    vector <int> vi;
    g<int>(vi); //ok
    vector <bool> vb;
    g<bool>(vb); //crash!
    Try to compile this code with T as any type but bool, and it works fine. Use bool and it crashes.
    Danny Kalev

Similar Threads

  1. Constructor question
    By FededS in forum C++
    Replies: 4
    Last Post: 07-03-2005, 01:42 PM
  2. Need help with writing a constructor!
    By Falcone in forum Java
    Replies: 3
    Last Post: 06-18-2005, 01:13 PM
  3. Copy Constructor
    By dubbu in forum C++
    Replies: 2
    Last Post: 04-04-2005, 04:31 PM
  4. Replies: 3
    Last Post: 04-13-2001, 09:13 PM
  5. C# constructor
    By Morten Dahl in forum .NET
    Replies: 3
    Last Post: 02-27-2001, 06:39 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center