bslstl_equalto

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Creating and Using a List Set
    • Example 2: Using Our List Set For a Custom Type

Purpose

Provide a binary functor conforming to the C++11 equal_to spec.

Classes

• equal_to: C++11-compliant binary functor applying operator==

Canonical header: bsl_functional.h

See also

bslstl_unorderedmap, bslstl_unorderedset

Description

This component provides the C+11 standard binary comparison functor, bsl::equal_to, that evaluates equality of two VALUE_TYPE objects through the operator==. The application of the functor to two different objects o1 and o2 returns true if o1 == o2. Note that this the for use as keys in the standard unordered associative containers such as bsl::unordered_map and bsl::unordered_set. Also note that this class is an empty POD type.

Usage

This section illustrates intended usage of this component.

Example 1: Creating and Using a List Set

Suppose we want to keep a set of a small number of elements, and the only comparison operation we have on the type of the elements is an equality operator. We can keep a singly-linked list of the elements, and exhaustively use the comparison operator to see if a given value exists in the list, forming a primitive set.

First, we define our ListSet template class:

/// This class implements a crude implementation of a set, that will
/// keep a set of values and be able to determine if an element is a
/// member of the set.  Unlike a `bsl::set` or `bsl::unordered_set`, no
/// hash function or transitive `operator<` is required -- only a
/// transitive `EQUALS` operator.
///
/// The `TYPE` template parameter must have a public copy constructor
/// and destructor available.
///
/// The `EQUALS` template parameter must a function with a function
/// whose signature is
/// ```.
///  bool operator()(const TYPE& lhs, const TYPE& rhs) const;
/// ```
/// and which returns `true` if `lhs` and `rhs` are equivalent and
/// `false` otherwise.  This equivalence relation must be transitive and
/// symmetric.  The comparator must have a default constructor and
/// destructor which are public.
template <typename TYPE, typename EQUALS = bsl::equal_to<TYPE> >
class ListSet {
 
    // PRIVATE TYPES
    struct Node {
        TYPE  d_value;
        Node *d_next;
    };
 
    // DATA
    EQUALS            d_comparator;
    Node             *d_nodeList;
    bslma::Allocator *d_allocator_p;
 
  private:
    // NOT IMPLEMENTED
    ListSet(const ListSet&);
    ListSet& operator=(const ListSet&);
 
  public:
    // CREATORS
 
    /// Create an empty `ListSet` using the specified `allocator`, or
    /// the default allocator if none is specified.
    explicit
    ListSet(bslma::Allocator *allocator = 0)
    : d_comparator()
    , d_nodeList(0)
    , d_allocator_p(bslma::Default::allocator(allocator))
    {}
 
    /// Release all memory used by this `ListSet`
    ~ListSet()
    {
        for (Node *node = d_nodeList; node; ) {
            Node *toDelete = node;
            node = node->d_next;
 
            d_allocator_p->deleteObject(toDelete);
        }
    }
 
    // MANIPULATOR
 
    /// If `value` isn't contained in this `ListSet`, add it and return
    /// `true`, otherwise, return `false` with no change to the
    /// `ListSet`.
    bool insert(const TYPE& value)
    {
        if (count(value)) {
            return false;                                         // RETURN
        }
 
        Node *node =
                 bslma::AllocatorUtil::allocateObject<Node>(d_allocator_p);
        bslma::ConstructionUtil::construct(&node->d_value,
                                           d_allocator_p,
                                           value);
        node->d_next = d_nodeList;
        d_nodeList = node;
 
        return true;
    }
 
    /// Return the number of nodes whose `d_value` field is equivalent
    /// to the specified `value`, which will always be 0 or 1.
    int count(const TYPE& value) const
    {
        for (Node *node = d_nodeList; node; node = node->d_next) {
            if (d_comparator(node->d_value, value)) {
                return 1;                                         // RETURN
            }
        }
 
        return 0;
    }
};

Then, in main, we declare an instance of ListSet storing ints. The default definition of bsl::equal_to will work nicely:

ListSet<int> lsi;

Now, we insert several values into our ListSet. Note that successful insertions return true while redundant ones return false with no effect:

assert(true  == lsi.insert( 5));
assert(false == lsi.insert( 5));
assert(false == lsi.insert( 5));
assert(true  == lsi.insert(11));
assert(true  == lsi.insert(17));
assert(true  == lsi.insert(81));
assert(true  == lsi.insert(32));
assert(false == lsi.insert(17));

Finally, we observe that our count method successfully distinguishes between values that have been stored in our ListSet and those that haven't:

assert(0 == lsi.count( 7));
assert(1 == lsi.count( 5));
assert(0 == lsi.count(13));
assert(1 == lsi.count(11));
assert(0 == lsi.count(33));
assert(1 == lsi.count(32));

Example 2: Using Our List Set For a Custom Type

Suppose we want to have a list set containing objects of a custom type. We can declare an operator== for our custom type, and equal_to will use that. We will re-use the ListSet template class from example 1, and create a new custom type.

First, we define a type StringThing, which will contain a const char * pointer, it will be a very simple type, that is implicitly castable to or from a const char *.

/// This class holds a pointer to zero-terminated string.  It is
/// implicitly convertible to and from a `const char *`.  The difference
/// between this type and a `const char *` is that `operator==` will
/// properly compare two objects of this type for equality of strings
/// rather than equality of pointers.
class StringThing {
 
    // DATA
    const char *d_string;    // held, not owned
 
  public:
    // CREATOR
 
    /// Create a `StringThing` object out of the specified `string`.
    StringThing(const char *string)                             // IMPLICIT
    : d_string(string)
    {}
 
    // ACCESSOR
 
    /// Implicitly cast this `StringThing` object to a `const char *`
    /// that refers to the same buffer.
    operator const char *() const
    {
        return d_string;
    }
};

Then, we create an operator== for StringThings

  bool operator==(const StringThing& lhs, const StringThing& rhs)
      {
          return !strcmp(lhs, rhs);
      }

Next, in main, we declare a ListSet containing StringThings:

ListSet<StringThing> lsst;

Then, we insert a number of values, and observe that redundant inserts return false with no effect:

assert(true  == lsst.insert("woof"));
assert(true  == lsst.insert("meow"));
assert(true  == lsst.insert("arf"));
assert(false == lsst.insert("woof"));
assert(true  == lsst.insert("bark"));
assert(false == lsst.insert("meow"));
assert(false == lsst.insert("woof"));

Now, we observe that our count method successfully distinguishes between values that have been stored in lsst and those that haven't:

assert(1 == lsst.count("meow"));
assert(0 == lsst.count("woo"));
assert(1 == lsst.count("woof"));
assert(1 == lsst.count("arf"));
assert(0 == lsst.count("chomp"));

Finally, we copy values into a buffer and observe that this makes no difference to counts results:

char buffer[10];
strcpy(buffer, "meow");
assert(1 == lsst.count(buffer));
strcpy(buffer, "bite");
assert(0 == lsst.count(buffer));