Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Collections comparison
PrevUpHomeNext

Collections comparison

Instead of comparing a single value against another, there is often a need for comparing collections of values. A collection and indirectly the values it contains may be considered in several ways:

  • collection as a sequence of values: this is the case for instance when N values are stored in a container. Containers in this case are used for storing several values, and iterating over the containers yields sequences that can be compared element-wise. The iteration should be in an order that is a priori known [10], for being able to compare the sequences. The values in the collection are independent each other, and subsets can be compared as well.
  • collection as an ensemble: this is the case where the elements of the collection define an entity, and no element can be dissociated from the others. An example would be a collection of letters for a specific word in the natural language; in this settings any of the character in the word/collection depends semantically on the other and it is not possible to take a subset of it without breaking the meaning of the word. Another example would be a vector of size N representing a point in a N dimensional space, compared to another point with the relation "<": the comparison is application specific and a possible comparison would be the lexicographical ordering [11].

The following observations can be done:

  • the methods employed for comparing collections should be chosen adequately with the meaning of the collection,
  • comparing sequences element-wise often involves writing loops in the test body, and if a dedicated tool is already in place the test body would gain in clarity and expressiveness (including the report in case of failure),
  • some comparison methods such as the lexicographical one, have good general behavior (e.g. total ordering, defined for collections of different size), but are sometimes inappropriate.

BOOST_TEST provides specific tools for comparing collections:

  • using the native [12] operator of the container of the collection, which is mentioned as the default behavior.
  • using element-wise comparison for which extended failure diagnostic is provided,
  • and using lexicographical comparison for which extended failure diagnostic is provided,

More details about the concept of collection in the Unit Test Framework is given here.

Default comparison

The default comparison dispatches to the existing overloaded comparison operator. The Unit Test Framework distinguishes two use cases

  1. none of the comparison operand is a C-Array, in which case we use the container default behavior
  2. one of the comparison operand is a C-array, in which case we mimic std::vector behavior
Container default behavior

Given two containers c_a and c_b that are not C-arrays, 

BOOST_TEST(c_a op c_b)

is equivalent, in terms of test success, to 

auto result = c_a op c_b;
BOOST_TEST(result);

In the example below, operator== is not defined for std::vector of different types, and the program would fail to compile if the corresponding lines were uncommented (std::vector uses lexicographical comparison by default).

[Note] Note

In the case of default comparison, there is no additional diagnostic provided by the Unit Test Framework. See the section BOOST_TEST_SPECIALIZED_COLLECTION_COMPARE below.

Example: BOOST_TEST containers comparison default

Code 

#define BOOST_TEST_MODULE boost_test_sequence
#include <boost/test/included/unit_test.hpp>
#include <vector>

BOOST_AUTO_TEST_CASE( test_collections_vectors )
{
  std::vector<int> a{1,2,3}, c{1,5,3,4};
  std::vector<long> b{1,5,3};

  // the following does not compile
  //BOOST_TEST(a == b);
  //BOOST_TEST(a <= b);

  // stl defaults to lexicographical comparison
  BOOST_TEST(a < c);
  BOOST_TEST(a >= c);
  BOOST_TEST(a != c);
}

Output 

> ./boost_test_container_default --log_level=all
Running 1 test case...
Entering test module "boost_test_sequence"
test.cpp(13): Entering test case "test_collections_vectors"
test.cpp(23): info: check a < c has passed
test.cpp(24): error: in "test_collections_vectors": check a >= c has failed
test.cpp(25): info: check a != c has passed
test.cpp(13): Leaving test case "test_collections_vectors"; testing time: 208us
Leaving test module "boost_test_sequence"; testing time: 286us

*** 1 failure is detected in the test module "boost_test_container_default"
C-arrays default behavior

As soon as one of the operands is a C-array, there is no default behavior the Unit Test Framework can dispatch to. This is why in that case, the comparison mimics the std::vector behavior.

Example: BOOST_TEST C-arrays

Code 

#define BOOST_TEST_MODULE boost_test_containers_c_arrays
#include <boost/test/included/unit_test.hpp>
#include <vector>

namespace tt = boost::test_tools;

BOOST_AUTO_TEST_CASE( test_collections_on_c_arrays )
{
  int a[] = {1, 2, 3};
  int b[] = {1, 5, 3, 4};
  std::vector<long> c{1, 5, 3, 4};
  BOOST_TEST(a == a); // element-wise compare
  BOOST_TEST(a == b); // element-wise compare
  BOOST_TEST(a != b);
  BOOST_TEST(a < b); // lexicographical compare
  BOOST_TEST(b < c); // lexicographical compare
  BOOST_TEST(c < a); // lexicographical compare
}

Output 

> ./boost_test_containers_c_arrays --log_level=all
Running 1 test case...
Entering test module "boost_test_containers_c_arrays"
test.cpp:15: Entering test case "test_collections_on_c_arrays"
test.cpp:20: info: check a == a has passed
test.cpp:21: error: in "test_collections_on_c_arrays": check a == b has failed.
Collections size mismatch: 3 != 4
test.cpp:22: info: check a != b has passed
test.cpp:23: info: check a < b has passed
test.cpp:24: error: in "test_collections_on_c_arrays": check b < c has failed.
Collections appear to be equal.
test.cpp:25: error: in "test_collections_on_c_arrays": check c < a has failed.
Failure at position 1: 5 >= 2.
test.cpp:15: Leaving test case "test_collections_on_c_arrays"; testing time: 204us
Leaving test module "boost_test_containers_c_arrays"; testing time: 240us

*** 3 failures are detected in the test module "boost_test_containers_c_arrays"

Element-wise comparison

By specifying the manipulator boost::test_tools::per_element, the comparison of the elements of the containers are performed element-wise, in the order given by the forward iterators of the containers. This is a comparison on the sequences of elements generated by the containers, for which the Unit Test Framework provides advanced diagnostic.

In more details, let c_a = (a_1,... a_n) and c_b = (b_1,... b_n) be two sequences of same length, but not necessarily of same type. Those sequences correspond to the content of the respective containers, in the order given by their iterator. Let op be one of the binary comparison operators. 

BOOST_TEST(c_a op c_b, boost::test_tools::per_element() );

is equivalent to 

if(c_a.size() == c_b.size())
{
  for(int i=0; i < c_a.size(); i++)
  {
    BOOST_TEST_CONTEXT("index " << i)
    {
      BOOST_TEST(a_i op b_i);
    }
  }
}
else
{
  BOOST_TEST(c_a.size() == c_b.size());
}
[Warning] Warning

this is fundamentally different from using the containers' default comparison operators (default behavior).

[Warning] Warning

this is not an order relationship on containers. As a side effect, it is possible to have 

BOOST_TEST(c_a == c_b)

and 

BOOST_TEST(c_a != c_b)

failing at the same time

Sequences are compared using the specified operator op, evaluated on the left and right elements of the respective sequences. The order of the compared elements is given by the iterators of the respective containers [13]. In case of failure, the indices of the elements failing op are returned.

Example: BOOST_TEST sequence comparison

Code 

#define BOOST_TEST_MODULE boost_test_sequence_per_element
#include <boost/test/included/unit_test.hpp>
#include <vector>
#include <list>
namespace tt = boost::test_tools;

BOOST_AUTO_TEST_CASE( test_sequence_per_element )
{
  std::vector<int> a{1,2,3};
  std::vector<long> b{1,5,3};
  std::list<short> c{1,5,3,4};

  BOOST_TEST(a == b, tt::per_element()); // nok: a[1] != b[1]

  BOOST_TEST(a != b, tt::per_element()); // nok: a[0] == b[0] ...
  BOOST_TEST(a <= b, tt::per_element()); // ok
  BOOST_TEST(b  < c, tt::per_element()); // nok: size mismatch
  BOOST_TEST(b >= c, tt::per_element()); // nok: size mismatch
  BOOST_TEST(b != c, tt::per_element()); // nok: size mismatch
}

BOOST_AUTO_TEST_CASE( test_compare_c_arrays_element_wise )
{
  int a[] = {1, 2, 3};
  int b[] = {1, 5, 3};
  std::vector<long> c{1, 5, 3};
  BOOST_TEST(a == b, boost::test_tools::per_element());
  BOOST_TEST(a != b, boost::test_tools::per_element());
  BOOST_TEST(a < b, boost::test_tools::per_element());
  BOOST_TEST(b < c, boost::test_tools::per_element());
  BOOST_TEST(c < a, boost::test_tools::per_element());
}

Output 

> ./boost_test_sequence_per_element
Running 2 test cases...
test.cpp:21: error: in "test_sequence_per_element": check a == b has failed
Mismatch at position 1: 2 != 5.
test.cpp:23: error: in "test_sequence_per_element": check a != b has failed
Mismatch at position 0: 1 == 1.
Mismatch at position 2: 3 == 3.
test.cpp:25: error: in "test_sequence_per_element": check b < c has failed
Collections size mismatch: 3 != 4
test.cpp:26: error: in "test_sequence_per_element": check b >= c has failed
Collections size mismatch: 3 != 4
test.cpp:27: error: in "test_sequence_per_element": check b != c has failed
Collections size mismatch: 3 != 4
test.cpp:35: error: in "test_compare_c_arrays_element_wise": check a == b has failed
Mismatch at position 1: 2 != 5.
test.cpp:36: error: in "test_compare_c_arrays_element_wise": check a != b has failed
Mismatch at position 0: 1 == 1.
Mismatch at position 2: 3 == 3.
test.cpp:37: error: in "test_compare_c_arrays_element_wise": check a < b has failed
Mismatch at position 0: 1 >= 1.
Mismatch at position 2: 3 >= 3.
test.cpp:38: error: in "test_compare_c_arrays_element_wise": check b < c has failed
Mismatch at position 0: 1 >= 1.
Mismatch at position 1: 5 >= 5.
Mismatch at position 2: 3 >= 3.
test.cpp:39: error: in "test_compare_c_arrays_element_wise": check c < a has failed
Mismatch at position 0: 1 >= 1.
Mismatch at position 1: 5 >= 2.
Mismatch at position 2: 3 >= 3.

*** 10 failures are detected in the test module "boost_test_sequence_per_element"
Requirements

For the sequences to be comparable element-wise, the following conditions should be met:

  • the containers should meet the sequence definition,
  • the containers should yield the same number of elements,
  • op should be one of the comparison operator ==, !=, <, <=, >, >=
  • the a_i op b_i should be defined, where the type of a_i and b_i are the type returned by the dereference operator of the respective collections.
[Caution] Caution

the resulting type of "c_a == c_b" is an assertion_result: it is not possible to compose more that one comparison on the BOOST_TEST statement: 

BOOST_TEST(c_a == c_b == 42, boost::test_tools::per_element() ); // does not compile

Lexicographic comparison

By specifying the manipulator boost::test_tools::lexicographic, the containers are compared using the lexicographical order and for which the Unit Test Framework provides additional diagnostic in case of failure. 

BOOST_TEST(c_a op c_b, boost::test_tools::lexicographic() );

The comparison is performed in the order given by forward iterators of the containers.

[Tip] Tip

lexicographic comparison yields a total order on the containers: the statements c_a < c_b and c_b <= c_a are mutually exclusive.

[Note] Note

The equality == and inequality != are not available for this type of comparison.

Example: BOOST_TEST container comparison using lexicographical order

Code 

#define BOOST_TEST_MODULE boost_test_container_lex
#include <boost/test/included/unit_test.hpp>
#include <vector>

namespace tt = boost::test_tools;

BOOST_AUTO_TEST_CASE( test_collections_vectors_lex )
{
  std::vector<int> a{1,2,3}, b{1,2,2}, c{1,2,3,4};

  BOOST_TEST(a < a, tt::lexicographic());
  BOOST_TEST(a < b, tt::lexicographic());
  BOOST_TEST(a < c, tt::lexicographic());
  BOOST_TEST(a >= c, tt::lexicographic());

  //BOOST_TEST(a == c, tt::lexicographic()); // does not compile
  //BOOST_TEST(a != c, tt::lexicographic()); // does not compile
}

BOOST_AUTO_TEST_CASE( test_compare_c_arrays_lexicographic )
{
  int a[] = {1, 2, 3};
  int b[] = {1, 5, 3};
  std::vector<long> c{1, 5, 3};
  // BOOST_TEST(a == b, boost::test_tools::lexicographic()); // does not compile
  // BOOST_TEST(a != b, boost::test_tools::lexicographic()); // does not compile
  BOOST_TEST(a < b, boost::test_tools::lexicographic());
  BOOST_TEST(b < c, boost::test_tools::lexicographic());
  BOOST_TEST(c < a, boost::test_tools::lexicographic());
}

Output 

> ./boost_test_container_lex --log_level=all
Running 2 test cases...
Entering test module "boost_test_container_lex"
test.cpp:15: Entering test case "test_collections_vectors_lex"
test.cpp:19: error: in "test_collections_vectors_lex": check a < a has failed
Collections appear to be equal.
test.cpp:20: error: in "test_collections_vectors_lex": check a < b has failed
Failure at position 2: 3 >= 2.
test.cpp:21: info: check a < c has passed
test.cpp:22: error: in "test_collections_vectors_lex": check a >= c has failed
Second collection has extra trailing elements.
test.cpp:15: Leaving test case "test_collections_vectors_lex"; testing time: 178us
test.cpp:28: Entering test case "test_compare_c_arrays_lexicographic"
test.cpp:35: info: check a < b has passed
test.cpp:36: error: in "test_compare_c_arrays_lexicographic": check b < c has failed
Collections appear to be equal.
test.cpp:37: error: in "test_compare_c_arrays_lexicographic": check c < a has failed
Failure at position 1: 5 >= 2.
test.cpp:28: Leaving test case "test_compare_c_arrays_lexicographic"; testing time: 88us
Leaving test module "boost_test_container_lex"; testing time: 323us

*** 5 failures are detected in the test module "boost_test_container_lex"

Extended diagnostic by default for specific containers

As seen above,

  • for testing equality, the == relation is either explicit (using boost::test_tools::per_element()) or implicit when the container overloads/implements this type of comparison,
  • for testing inequality, lexicographical comparison for < (and derived operations) is either explicit (using boost::test_tools::lexicographic()) or implicit when the container overloads/implements uses this type of comparison.

When the default is to using the container implementation, it is not possible to benefit from an extended failure diagnostic. The Unit Test Framework provides a mechanism for performing the same comparisons through the Unit Test Framework instead of the container operator, through the macro BOOST_TEST_SPECIALIZED_COLLECTION_COMPARE that might be used as follow:

Example: Default std::vector<int> to lexicographic with extended diagnostic

Code 

#define BOOST_TEST_MODULE boost_test_container_lex_default
#include <boost/test/included/unit_test.hpp>
#include <vector>

namespace tt = boost::test_tools;

BOOST_TEST_SPECIALIZED_COLLECTION_COMPARE(std::vector<int>)

BOOST_AUTO_TEST_CASE( test_collections_vectors_lex )
{
  std::vector<int> a{1,2,3}, b{1,2,2};
  std::vector<long int> c{1,2,3,5}, d{1,2,3,4};

  BOOST_TEST(a < a); // lexcographic
  BOOST_TEST(a < b); // lexcographic
  BOOST_TEST(a == b); // element-wise
  BOOST_TEST(a != b); // extended diagnostic
  BOOST_TEST(c < d); // no extended diagnostic
  BOOST_TEST(c == d); // no extended diagnostic
}

Output 

> ./boost_test_container_lex_default --log_level=all
Running 1 test case...
Entering test module "boost_test_container_lex_default"
test.cpp:17: Entering test case "test_collections_vectors_lex"
test.cpp:22: error: in "test_collections_vectors_lex": check a < a has failed.
Collections appear to be equal.
test.cpp:23: error: in "test_collections_vectors_lex": check a < b has failed.
Failure at position 2: 3 >= 2.
test.cpp:24: error: in "test_collections_vectors_lex": check a == b has failed.
Mismatch at position 2: 3 != 2.
test.cpp:25: info: check a != b has passed
test.cpp:26: error: in "test_collections_vectors_lex": check c < d has failed
test.cpp:27: error: in "test_collections_vectors_lex": check c == d has failed
test.cpp:17: Leaving test case "test_collections_vectors_lex"; testing time: 155us
Leaving test module "boost_test_container_lex_default"; testing time: 177us

*** 5 failures are detected in the test module "boost_test_container_lex_default"
Requirements
  • the containers should meet the sequence definition,
  • the containers should be of the exact same type
  • op should be one of the comparison operator ==, !=, <, <=, >, >=
[Note] Note

Note that the operation != is in this case not an element-wise comparison,

What is a sequence?

A sequence is given by the iteration over a forward iterable container. A forward iterable container is:

  • either a C-array,
  • or a class/struct that implements the member functions begin and end.

For collection comparisons, both sequences are also required to be different than string sequences. In that case, the sequences are dispatched to string comparison instead.

[Warning] Warning

string (or wstring) meets the sequence concept by definition, but their handling with BOOST_TEST is done differently. See Strings and C-strings comparison for more details.

[Tip] Tip

If the behavior of BOOST_TEST is not the one you expect, you can always use raw comparison. See this section for details.

[Note] Note

Since Boost.Test 3.6 (Boost 1.65) the requirements for the collection concepts have been relaxed to include C-arrays as well

[Note] Note

Since Boost.Test 3.7 (Boost 1.67) the definition of const_iterator and value_type in the collection type is not required anymore (for the compilers properly supporting decltype).

The detection of the types that meet these requirements containers is delegated to the class boost::unit_test::is_forward_iterable, which for C++11 detects the required member functions and fields. However for C++03, the types providing the sequences should be explicitly indicated to the Unit Test Framework by a specialization of boost::unit_test::is_forward_iterable [14].


[10] this might not be the case for e.g. std::unordered_map, for which the buckets might be filled differently depending on the insertion order.

[11] in this case v_a < v_b means that the point v_a is inside the rectangle (origin, v_b)

[12] either defined by the container or by the user

[13] the containers should yield the same sequences for a fixed set of elements they contain

[14] Standard containers of the STL are recognized as forward iterable container.

Copyright © 2001-2022 Boost.Test contributors

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

PrevUpHomeNext