You are here:

C++/inserting bitset into set

Advertisement


Question
Hello,

I am writing code which uses a set of bitset<4>'s. Constructing the bitset works fine, but I get some unintelligible compile-time errors whe I try to insert the bitset into the bitset-set. I've spent quite some time trying to figure out the problem, but to no avail. I'd really appreciate your help! Here is the code, with the problematic line commented out:

#include <iostream>
#include <sstream>
#include <bitset>
#include <set>

using namespace std;

int main() {
 set<bitset <4> > circuits ;
 int elt;

 string circuit_string = "1 2 4";
 istringstream circuit_stream;
 circuit_stream.str(circuit_string);

 bitset<4> circuit_bs;

 while (circuit_stream >> elt) {circuit_bs.set(elt-1,1);}

 //  circuits.insert(circuit_bs);

}


Answer
The C++ standard library associative collection types, such as std::set and std::map, are sorted collections of values. To be able to determine where in a sorted collection a given value should go (e.g. when inserting a value into a std::set) the values in that collection have to be arranged in some sort of order, such that give two values (key values in the case of a map) it can be determined which of them should come before the other, or if they are equivalent (inserting an equivalent value into a std::set or key into a std::map is not permitted but allowable for std::multiset and std::multimap). The default operation for performing these checks is provided by std::less which uses operator< for the type in question.

Note that equivalence is determined as (assuming the default std::less operation is used):

   if ( ! (elem1<elem2 || elem2<elem1) )

Which in more general terms can be thought of as:

   "elem1 and elem2 are equivalent
    if elem1 is not before elem2
    and elem2 is not before elem1"

(the difference in operators shown in the if statement and the English language above is due to the application of De Morgan's theorem, see http://en.wikipedia.org/wiki/De_Morgan's_laws).

The type in question in this case is std::bitset<4>. This type has no defined operator<, and so you cannot insert values of this type into a std::set< std::bitset<4> >. The obvious solution is to provide a sorting operation for this type.

Before delving into the correct way to do this let us examine the most obvious solution. You could define an operator< for std::bitset<4>, thus:

   typedef bitset<4> CircuitType;

   bool operator<( CircuitType const & c1, CircuitType const & c2 )
   {
       return c1.to_ulong() < c2.to_ulong();
   }

The above implementation simply compares the values of the std::bitset<4> parameters after they have been converted to unsigned long values. Note that I have provided a type alias called CircuitType for std::bitset<4>, so CircuitType can be used wherever you were using bitset<4> before. If later you find you need say a std::bitset<5> then you will only need to change the typedef rather than all uses of std::bitset<4> used as a circuit type (some may not be used in such a context!). As with naming magic numbers by creating constants, this practice also makes what the type is used for more explicit. The rest of your code I changed to suit:

   typedef set< CircuitType >  CircuitSetType;

   int main()
   {
       CircuitSetType circuits;

       int elt;

       string circuit_string = "1 2 4";
       istringstream circuit_stream;
       circuit_stream.str(circuit_string);

       CircuitType circuit_bs;

       while (circuit_stream >> elt)
       {
         circuit_bs.set(elt-1,1);
       }
     
       circuits.insert(circuit_bs);
   }

The only problem is that this still does not compile. This is because the C++ compiler looks in the 'wrong' places for the operator< function definition and fails to locate our definition. As std::bitset is defined in the std namespace it does look there, so we could place our definition in there:

   namespace std
   {
       bool operator<(CircuitType const & c1, CircuitType const & c2)
       {
         return c1.to_ulong() < c2.to_ulong();
       }
   }

However, mere language users like us are not allowed to add things to the C++ std namespace, this is forbidden by the C++ standard.

So what is the correct way to provide a sorting operation for our set of circuits?

The std::set class template has a second type parameter that defaults to std::less. You can explicitly provide this parameter to specify that std::set uses your own sorting class type. Such types provide an operator() (the call operator) that takes two objects of the set's value type and returns a bool value indicating which should be before the other. As the operator() member function does not (errmm, should not) modify any instance state it is defined as being a const member function.

In addition std:set provides opportunity to pass a specific instance of the sorting class to a constructor. This is useful if we need to initialise such a type with to some state at runtime.

In your case no state is needed by the comparison operation, so we can just use the first method. The revised code looks like so:

   typedef bitset<4> CircuitType;

   class CircuitLess
   {
   public:
       bool operator()
       ( CircuitType const & c1, CircuitType const & c2 ) const
       {
         return c1.to_ulong() < c2.to_ulong();
       }
   };

   typedef set< CircuitType, CircuitLess >  CircuitSetType;

The main function remains as I showed before. However note that:

- The operator< function has now become the operator() function in a class called CircuitLess.

- The CircuitLess class type is now specified as the second template parameter of the std::set type used for the CircuitSetType typedef type alias.

- Because CircuitSetType is a type alias the code (in main) that uses an instance of CircuitSetType, rather than the type it aliases does not need any modifications.

- A side effect of the quick conversion from the original operator< function is that the CircuitLess::operator() function is defined inline in the class definition. This is probably OK in this case as the implementation is simple and small. If the implementation were complex and long then it would obviously be better to declare it in the class definition and define it out of line elsewhere. However such things are really optimisation territory and should not concern us at this point in development.

If you are making much use of the C++ standard library the I strongly suggest that you get yourself a good reference such as "The C++ Standard Library A Tutorial and Reference" by Nicolai M. Josuttis.  

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Ralph McArdell

Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials

©2016 About.com. All rights reserved.