Should I avoid using pointers here?

Question

I have this simple code:

std::vector<std::map<double,double>> v;
//populate v

//we know each map already has correct key order (enforced by c++)
//but i also want to make sure the different maps have correct key order
//this is how I do it using a pointer:

const double *last_key = nullptr;
for (const auto &map : v)
{
  if (map.size() > 0) //ignore empty maps
  {
    if (last_key)
    {
      const auto &new_key = map.cbegin()->first;
      if (!(*last_key < new_key))
        throw std::runtime_error("invalid key order");
    }
    last_key = &(--map.cend())->first;
  }
}

Is this a good use for pointers? How would you do it instead?

The only real alternative I know (if I want to avoid pointers) is to do this:

double last_key;
bool last_key_has_been_set = false;

This works, but it requires that the key is default constructible and it involves unnecessary copying of keys (problem for different key types than double).

Answer 1

OK, since I now (think I) understand what your code is about, here's my take on it:

auto iter = v.begin();
auto end = v.end();
while (iter != end && iter->empty())
  ++iter;
if (iter != end)
{
  while (true) // loop and a half
  {
    auto next = iter+1; // at this point, we know iter != end
    while (next != end && next->empty())
      ++next;
    if (next == end)
      break;
    auto lhslast = lhs.end();
    --lhslast;
    if (lhslast->first > next->begin()->first)
      throw std::runtime_error("invalid key order");
    iter = next;
  }
}

Edit:

The code above can be further improved using another algorithm:

Replace

while (iter != end && iter->empty())
  ++iter;

with

iter = std::find_if(iter, end,
                    [](std::map<double, double> const& m) { return m.empty(); });

and analogous for the next loop.

Another option is to notice that if it were not empty maps, you could just use adjacent_find. Therefore another option is to make use of Boost's filter_iterator to get rid of the empty maps. Thus do

#include <boost/iterator/filter_iterator.hpp>

struct is_not_empty
{
  template<typename Container> bool operator()(Container const& c) const
  {
    return !c.empty();
  }
};

and then at the place of your code

auto fbegin = boost::make_filter_iterator(is_not_empty(), v.begin(), v.end());
auto fend =  boost::make_filter_iterator(is_not_empty(), v.end(), v.end());

if (std::adjacent_find(fbegin, fend,
                       [](std::map<double, double> const& lhs,
                          std::map<double, double> const& rhs) -> bool
                       {
                         auto lhslast = lhs.end();
                         --lhslast;
                         return lhslast->first > rhs.begin()->first;
                       }) != fend)
  throw std::runtime_error("invalid key order");

The filter iterator makes sure that only the non-empty maps are considered.

Answer 2

I don't think there is a suitable predefined algorithm in the standard library that does this. In particular, std::adjacent_find could be used for this if you were to define a relatively complex and stateful predicate for it, but that would really amount to misusing std::adjacent_find as some kind of replacement for std::for_each, i.e. it would not have much to do with the original purpose of std::adjacent_find.

However, instead of naked pointers, you should be using iterators. I'd also suggest putting the checking code into a separate function, perhaps named check. Here is what I would suggest:

#include <vector>
#include <map>
#include <iostream>

bool check(const std::vector<std::map<double,double>> &v)
{
  /* Fast-forward to the first non-empty entry. */
  auto it = begin(v);
  for( ; it != end(v) ; ++it)
    if (!it->empty())
      break;

  /* We might be done by now. */
  if (it == end(v))
    return true;

  /* Else, go through the remaining entries,
     skipping empty maps. */
  auto prev = it->end();
  advance(prev,-1);
  ++it;

  for ( ; it != end(v) ; ++it)
    {
      if (!it->empty())
        {
          if (it->begin()->first < prev->first)
            return false;
          prev = it->end();
          advance(prev,-1);
        }
    }

  return true;
}

int main()
{
  std::vector<std::map<double,double>> v;

  /* Two entries for the vector, invalid order. */    
  v.push_back({ {1.0,1.0} , {2.0,4.0} });
  v.push_back({ {3.0,9.0} , {1.0,16.0} });

  if (!check(v))
    throw std::runtime_error("Invalid order of the maps in the vector.");

  return 0;
}

Note: It would be even more C++-like (or, at least more like the algorithms in the standard library) if you were to define the check function as an algorithm that takes a range of iterators, rather than a reference to a container, as argument. Rewriting the function to match this concept is straight-forward.

Note 2: The advantage of using iterators instead of naked pointers is that you get a better and cleaner abstraction of what you need: Something that references an item in the map, whereas a double* pointer could be pointing to all kinds of things. However, there is also a disadvantage of using iterators: If you were to modify your algorithm such that it alters maps while iterating through the vector, the iterator may be invalidated, whereas the pointer would not (unless you delete the element it points to). (The pointers might be invalidated if you alter the vector, though.)

But as long as the checking procedure is only used for checking and nothing else (which my code indicates by putting the code into a separate function dedicated to this purpose, and by taking the vector as a const-reference), iterator invalidation is not an issue.

Answer 3

This uses a C++1y feature (std::tr2::optional), but should work with any container and any ordering on the elements of the containers:

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  // or boost::optional:
  std::tr2::optional< decltype( begin(begin(meta)) ) > last_valid;

  for( auto&& Map : std::forward<Meta>(meta) ) {
    auto b = begin(Map);
    auto e = end(Map);
    if (b==e)
      continue;
    if (last_valid)
      if (!order( **last_valid, *b ))
        return false;
    last_valid = e;
  }
  return true;
}

optional is a prettier, less error prone way of dealing with the "this element may or may not exist" than a pointer-that-can-be-nullptr. If you are using boost or have access to a std::tr2::optional (or you are reading this in the future, when std::optional exists), it is a better idea than a pointer.

You could also move the "is there a last_valid out of state and into program code location:

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  auto it = begin(meta);
  while( it != end(meta) && (begin(*it) == end(*it)) {
    ++it;
  }
  if ( it == end(meta) )
    return true;
  auto last_valid_end = end(*it);
  for( ++it; it != end(meta); ++it ) {
    auto b = begin(*it);
    auto e = end(*it);
    if (b==e)
      continue;
    if (!order( *last_valid_end, *b ))
      return false;
    last_valid = e;
  }
  return true;
}

this would let the same algorithm run on vectors-of-vectors-of-pairs, or even check if vectors-of-vectors have sorted endpoints (with a different order).

Answer 4

Best noted comment gives the answer : use adjacent_find.

First a little bit of logic. If there is n < m indexes verifying key[n] > key[m], then an index i exists, n <= i < m where key[i] > key[i+i].

You can demonstrate this with absurdity reasoning : If there is no such i, then for all i between n and m we have order, and because order relation is transitive, key[n] <= key[m] : absurd. This means, ignoring the empty maps, if you have bad order on your keys, then you have two adjacent keys in bad order.

So your algorithm shoud be:

typedef map<double, double> map_t;
vector<map_t> v;
remove_if(v.begin(), v.end(), [](map_t const& m){return m.empty();});
if(adjacent_find(v.begin(), v.end(), [](map_t const& l, map_t const& r)
    {
        return (--l.cend())->first > r.cbegin()->first;
    }) != v.end())
    throw std::runtime_error("invalid key order");

This is, of course, if you can remove the empty maps from your vector first. (we can assume that, as empty maps may not be so meaningful, but it depends on the whole situation, for sure).