Getting values not equals x in boost's multi_index_container

Question

I'm trying to get a iterator to all values that are not equal a certain value in boost::multi_index_container.

The index I want to access is a hashed_non_unique integer. Using equal_range(0) on my container which serves as a mapping database, I'm able to access all container entries that have this specific index set to zero.

What I need is a function that returns me all entries where the index is not zero. I searched the web for hours and only found the overloaded function

std::pair<iterator,iterator> equal_range(
    const CompatibleKey& x,
    const CompatibleHash& hash,const CompatiblePred& eq)const;

But the boost documentation only has few examples and there is none for this specific problem. I do not know what a CompatibleHash or a CompatiblePred is, but I tried with:

    m_mappingDb->get<tags::myIndex>().equal_range(m_mappingDb->begin(), 0, 
        [=](uint32_t lhs, uint32_t rhs) { return lhs != rhs; });

after finding examples of people using an lambda as sort function in the multi_index_container.

When compiling, I then receive a C2664 in that lambda expression that a conversion from boost::multi_index::detail::hashed_index_iterator<Node,BucketArray,Category> to uint32_t is not possible. So, I'm expecting that my lambda must use iterators as parameters, but which exactly? What is Node, BucketArray and Category?

There is another C2064 in that lambda expression that states that this is not a function that takes 1 argument. Of course, it takes 2. Do I have to compare against this instead?

My alternative is to use lower_bound and upper_bound instead and set the lower bound to 1 and the upper bound to the maximum value of uint32_t. But, in my opinion, this is ugly as hell. There must be a correct way to implement something like a not equals function.

Answer 1

Note that equal_range(k) returns a range (a pair of iterators in this context) as it relies on the fact that elements whose key is k are stored adjacently along the container sequence:

On the other hand, the elements whose key is not equal to k are not adjacent, but belong in two disjoint ranges:

So there is no way equal_range can be twisted to return this pair of ranges. If you absolutely need to treat the two ranges as one logical range you can resort to Boost.Range's join:

template<typename Container,typename Key>
auto not_equal_range(const Container& c,const Key& k)
{
  auto rng=c.equal_range(k);
  return boost::range::join(
    boost::make_iterator_range(c.begin(),rng.first),
    boost::make_iterator_range(rng.second,c.end()));
}

Complete example follows.

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/range/iterator_range_core.hpp>
#include <boost/range/join.hpp>

template<typename Container,typename Key>
auto not_equal_range(const Container& c,const Key& k)
{
  auto rng=c.equal_range(k);
  return boost::range::join(
    boost::make_iterator_range(c.begin(),rng.first),
    boost::make_iterator_range(rng.second,c.end()));
}

using namespace boost::multi_index;
using container=multi_index_container<
  int,
  indexed_by<
    hashed_non_unique<identity<int>>
  >
>;

#include <iostream>

int main()
{
  container c={0,0,1,1,2,2,3,4,4,4,5,6,6,6,7};
  for(auto x:not_equal_range(c,4))std::cout<<x<<" ";
}

Output

0 0 1 1 2 2 3 5 6 6 6 7