bslalg_rangecompare Component

Provide algorithms to compare iterator-ranges of elements. More...

Namespaces
namespace	bslalg

Detailed Description

Outline

Purpose
Classes
Description
- Usage
  - Example 1: Defining Equality-Comparison Operators on a Container

Purpose:: Provide algorithms to compare iterator-ranges of elements.

Classes:

bslalg::RangeCompare

comparison algorithms for iterator ranges

See also:: Component bslmf_isbitwiseequalitycomparable

Description:: This component provides a utility struct, bslalg::RangeCompare, that defines two overloaded class methods, equal and lexicographical, for comparing two ranges, each specified by a pair of input iterators that are compliant with the C++11 standard [24.2.3]. The equal method determines whether two specified ranges compare equal. The lexicographical method determines whether the first range compares lexicographically less than, equal to, or greater than the second range. Under certain circumstances, bslalg::RangeCompare::equal and bslalg::RangeCompare::lexicographical may perform optimized comparisons, as described below.

bslalg::RangeCompare::equal may perform a bit-wise comparison of the two ranges when the following two criteria are met:

The input iterators are convertible to a pointer type.
The trait bslmf::IsBitwiseEqualityComparable is declared for the type of the objects in the ranges being compared.

bslalg::RangeCompare::lexicographical may perform a bit-wise comparison of the two ranges when the following criterion is met:

The input iterators are convertible to pointers to a wide or unsigned

character type.

Note that a class having the bslmf::IsBitwiseEqualityComparable trait can be described as bit-wise comparable and should meet the following criteria:

The values represented by two objects belonging to the class are the same if and only if each of the data members in the class has the same value in both objects.
The class layout includes no padding.
The class has no virtual members.

: Note that this component is for use primarily by the bslstl package. Other clients should use the STL algorithms (in headers <bsl_algorithm.h> and <bsl_memory.h>).

Usage:: This section illustrates intended use of this component.

Example 1: Defining Equality-Comparison Operators on a Container:: In this example we will use the bslalg::RangeCompare::equal class method to implement the equality-comparison operators for an iterable container type residing in the bslstl package, and highlight the circumstances under which the optimization provided by the class method may be applied.

: Suppose that we have a new iterable container type that will be included in the bslstl package, and we wish to define comparison operators for the container. If the container has an iterator that provides access to the container's elements in a consistent order, and the elements themselves are equality-comparable, we can implement the container's equality-comparison operators by pair-wise comparing each of the elements over the entire range of elements in both containers. In such cases the container can use the bslalg::RangeCompare::equal class method to equal-compare the container's elements, taking advantage of the optimizations the class method provides for bit-wise equality-comparable objects.

First, we create an elided definition of a container class, MyContainer, which provides read-only iterators of the type MyContainer::ConstIterator:

  template <class VALUE_TYPE>
  class MyContainer {
      // This class implements a container, semantically similar to
      // 'std::vector', holding objects of the (template parameter) type
      // 'VALUE_TYPE'.

    private:
      // DATA
      // ...

    public:
      // PUBLIC TYPES
      typedef const VALUE_TYPE *ConstIterator;
          // This 'typedef' provides an alias for the type of iterator
          // providing non-modifiable access to the elements in the
          // container.

      // CREATORS
      explicit MyContainer(bslma::Allocator *basicAllocator = 0);
          // Create an empty 'MyContainer' object having no capacity.
          // Optionally specify a 'basicAllocator' used to supply memory.  If
          // 'basicAllocator' is 0, the currently installed default allocator
          // is used.

      // ...

      // MANIPULATORS
      // ...

      void push_back(const VALUE_TYPE& value);
          // Append the specified 'value' at the past-the-end position in
          // this container, increasing the container's capacity if needed.

      // ...

      // ACCESSORS
      ConstIterator begin() const;
          // Return an iterator providing non-modifiable access to the first
          // element in this container.

      ConstIterator end() const;
          // Return an iterator providing non-modifiable access to the
          // past-the-end element in this container.

      std::size_t size() const;
          // Return the number of elements in this container.

      // ...
  };

Notice that ConstIterator is defined as a pointer type, which is one of the criteria required to enable the optimizations provided by the bslalg::RangeCompare::equal class method.

Then, we declare the equality-comparison operators for MyContainer:

  template <class VALUE_TYPE>
  bool operator==(const MyContainer<VALUE_TYPE>& lhs,
                  const MyContainer<VALUE_TYPE>& rhs);
      // Return 'true' if the specified 'lhs' and 'rhs' objects have the same
      // value, and 'false' otherwise.  Two 'MyContainer' objects have the
      // same value if they have the same length, and each element in 'lhs'
      // has the same value as the corresponding element in 'rhs'.

  template <class VALUE_TYPE>
  bool operator!=(const MyContainer<VALUE_TYPE>& lhs,
                  const MyContainer<VALUE_TYPE>& rhs);
      // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
      // the same value, and 'false' otherwise.  Two 'MyContainer' objects do
      // not have the same value if they do not have the same length, or if
      // any element in 'lhs' does not have the same value as the
      // corresponding element in 'rhs'.

Next, we implement the equality-comparison operators using bslalg::RangeCompare::equal:

  template <class VALUE_TYPE>
  inline
  bool operator==(const MyContainer<VALUE_TYPE>& lhs,
                  const MyContainer<VALUE_TYPE>& rhs)
  {
      return BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
                                                      lhs.end(),
                                                      lhs.size(),
                                                      rhs.begin(),
                                                      rhs.end(),
                                                      rhs.size());
  }

  template <class VALUE_TYPE>
  inline
  bool operator!=(const MyContainer<VALUE_TYPE>& lhs,
                  const MyContainer<VALUE_TYPE>& rhs)
  {
      return !BloombergLP::bslalg::RangeCompare::equal(lhs.begin(),
                                                       lhs.end(),
                                                       lhs.size(),
                                                       rhs.begin(),
                                                       rhs.end(),
                                                       rhs.size());
  }

Then, we create the elided definition of a value-semantic class, MyString, together with its definition of operator==:

  class MyString {
      // This class provides a simple, elided string class that conforms to
      // the 'bslma::Allocator' model.

    private:
      // DATA
      char             *d_start_p;      // storage for the string
      std::size_t       d_length;       // length of the string
      bslma::Allocator *d_allocator_p;  // memory allocator (held, not owned)

      // ...

      // FRIENDS
      friend bool operator==(const MyString&, const MyString&);
      // ...

    public:
      // CREATORS
      explicit MyString(const char       *string,
                        bslma::Allocator *basicAllocator = 0);
          // Create a 'MyString' object initialized to the value of the
          // specified 'string'.  Optionally specify a 'basicAllocator' used
          // to supply memory.  If 'basicAllocator' is 0, the currently
          // installed default allocator is used.

      // ...
  };

  bool operator==(const MyString& lhs, const MyString& rhs)
  {
      return lhs.d_length == rhs.d_length
          && 0 == std::strncmp(lhs.d_start_p, rhs.d_start_p, lhs.d_length);
  }

Notice that MyString is not bit-wise comparable because the address values of the d_start_p pointer data members in two MyString objects will be different, even if the string values of the two objects are the same.

Next, we create two MyContainer<MyString> objects, and compare them using operator==:

  MyContainer<MyString> c1;
  MyContainer<MyString> c2;

  c1.push_back(MyString("hello"));
  c1.push_back(MyString("goodbye"));

  c2.push_back(MyString("hello"));
  c2.push_back(MyString("goodbye"));

  assert(c1 == c2);

Here, the call to the bslalg::RangeCompare::equal class method in operator== will perform an unoptimized pair-wise comparison of the elements in c1 and c2.

Then, we create the elided definition of another value-semantic class, MyPoint, together with its definition of operator==:

  class MyPoint {
      // This class provides a simple, elided point type that is bit-wise
      // comparable with other objects of the same type.

    private:
      // DATA
      int d_x;  // the x-coordinate of the point
      int d_y;  // the y-coordinate of the point

      // FRIENDS
      friend bool operator==(const MyPoint&, const MyPoint&);
      // ...

    public:
      // TRAITS
      BSLMF_NESTED_TRAIT_DECLARATION(MyPoint,
                            BloombergLP::bslmf::IsBitwiseEqualityComparable);

      // CREATORS
      MyPoint(int x, int y);
          // Create a 'MyPoint' object whose x- and y-coordinates have the
          // specified 'x' and 'y' values, respectively.

      // ...
  };

  bool operator==(const MyPoint& lhs, const MyPoint& rhs)
  {
      return lhs.d_x == rhs.d_x && lhs.d_y == rhs.d_y;
  }

Notice that the value of a MyPoint object derives from the values of all of its data members, and that no padding is required for alignment. Furthermore, MyPoint has no virtual methods. Therefore, MyPoint objects are bit-wise comparable, and we can correctly declare the bslmf::IsBitwiseEqualityComparable trait for the class, as shown above under the public TRAITS section.

Now, we create two MyContainer<MyPoint> objects and compare them using operator==:

  MyContainer<MyPoint> c3;
  MyContainer<MyPoint> c4;

  c3.push_back(MyPoint(1, 2));
  c3.push_back(MyPoint(3, 4));

  c4.push_back(MyPoint(1, 2));
  c4.push_back(MyPoint(3, 4));

  assert(c3 == c4);  // potentially optimized

Here, the call to bslalg::RangeCompare::equal in operator== may take advantage of the fact that MyPoint is bit-wise comparable and perform the comparison by directly bit-wise comparing the entire range of elements contained in the MyContainer<MyPoint> objects. This comparison can provide a significant performance boost over the comparison between two MyContainer<MyPoint> objects in which the nested bslmf::IsBitwiseEqualityComparable trait is not associated with the MyPoint class.

Finally, note that we can instantiate MyContainer with int or any other primitive type as the VALUE_TYPE and still benefit from the optimized comparison operators, because primitive (i.e.: fundamental, enumerated, and pointer) types are inherently bit-wise comparable:

  MyContainer<int> c5;
  MyContainer<int> c6;

  c5.push_back(1);
  c5.push_back(2);
  c5.push_back(3);

  c6.push_back(1);
  c6.push_back(2);
  c6.push_back(3);

  assert(c5 == c6);  // potentially optimized

Component bslalg_rangecompare [Package bslalg]

Namespaces

Detailed Description

Component bslalg_rangecompare
[Package bslalg]