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

Question

If I understand correctly, both std :: map and std :: unordered_map lines explicitly save (store key / value pairs). Is there any other container ready for use (std, boost, or another widespread implementation) that will not save the key, but rather allow to derive the key from the stored value using a function (for example, to use an implicit key?).

Answer 1

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

However, the search will be performed using the type of the stored value, not the key, so you will also need a way to create a temporary object from the key.

Answer 2

You may be looking for Boost.Intrusive . Boost Intrusive container "hook" on your value types to provide the characteristics of a specific container (for example, set, list, AVL tree, etc.) Directly from objects.

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

Answer 3

All ordered containers in a C ++ library, for example. std::set allow fewer comparison template templates, pass it as the second template parameter ( my_less in the example below). If you do not, operator< will be scanned through ADL and used if found (compilation error, if not); It should be suitable for a large number of cases.

Your own attribute or operator< can be used to determine the order according to the data stored in the keyless set. For comparison, no data is copied, note that these are links to const.

If you do not want to create a stack object and prefer to use heap pointers instead, you can obviously save boost::shared_ptr in a standard ordered container and write your less comparative attribute accordingly. In this case, you can also use boost ptr container

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 an example of a user-specified functor for comparison. Edited to add boost::shared_ptr to container