CODEWITHSUNDEEP
c++hashtablecontainers
Suma
Suma

Reputation: 34393

std, boost or other widespread implementation of a hash table container with implicit keys

If I understand it correctly, both std::map and std::unordered_map store keys explicitely (store pairs of keys / values). Is there some other ready to use container (std, boost or other widespread implementation) which would not store the key, but rather allow deriving the key from the stored value using a function (i.e. to use implicit key?).

Upvotes: 6

Views: 338

Answers (3)

bronekk
bronekk

Reputation: 2129

All ordered containers in C++ library e.g. std::set allow for less comparison template trait, pass it as a second template parameter (my_less in example below). . If you don't do it, operator< will be looked up via ADL and used if found (compilation error if not); it should be appropriate for plenty of cases.

Your own trait or operator< can be used to define order according to data stored in a set i.e. without key. No data is copied to perform this comparison, please note it takes const references.

If you don't want to create stack object and prefer to use heap pointers instead, you can obviously store boost::shared_ptr in standard ordered container and write your less comparison trait accordingly. In this case you may also consider using boost ptr containers

Example:

#include <boost/shared_ptr.hpp>
#include <set>
#include <iterator>
#include <iostream>

struct order_by_AB { int a; int b; int c; 
  order_by_AB(int a, int b, int c) : a(a), b(b), c(c) {}
};

struct my_less
{
  bool operator()(const boost::shared_ptr<order_by_AB>& lh, const boost::shared_ptr<order_by_AB>& rh)
  {
    if (lh->a == rh->a)
      return lh->b < rh->b;
    return lh->a < rh->a;
  }
};

std::ostream& operator<< (std::ostream& os, const boost::shared_ptr<order_by_AB>& rh)
{
  os << "(" << rh->a << "," << rh->b << "," << rh->c << ")";
  return os;
}

int main()
{
    std::set<boost::shared_ptr<order_by_AB>, my_less> data;
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 1, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 3, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 3, 2)));
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 1, 2)));
    std::copy(data.begin(), data.end(), std::ostream_iterator<boost::shared_ptr<order_by_AB>>(std::cout, "\n"));
    return 0;
}

Edited to give example of user-specified functor for comparison. Edited to add boost::shared_ptr in a container

Upvotes: 0

Mike Seymour
Mike Seymour

Reputation: 254431

std::set or std::unordered_set, with suitable hash and/or comparison functions for the stored value type.

However, lookup will be done by the stored value type, not the key, so you'll also need a way to fabricate a temporary object from a key.

Upvotes: 4

Daniel Trebbien
Daniel Trebbien

Reputation: 39208

You might be looking for Boost.Intrusive. Boost Intrusive containers "hook into" your value types to provide the characteristics of a certain container (e.g. set, list, AVL tree, etc.) directly from the objects.

See Differences between intrusive and non-intrusive containers for an overview of the differences between STL containers and Boost Intrusive containers.

Upvotes: 2

Related Questions