How can I use a custom type as key for a map in C++?
I suspect you need
bool operator<(const Foo& foo1) const;
Note the const
after the arguments, this is to make "your" (the left-hand side in the comparison) object constant.
The reason only a single operator is needed is that it is enough to implement the required ordering. To answer the abstract question "does a have to come before b?" it is enough to know whether a is less than b.
std::map with custom key
If you don't care about the specific order and just want to satisfy the requirements for sorting, a common and simple pattern is to use std::tie
with all of the class members of the compared instances, and compare those results instead.
std::tie
creates a std::tuple
of references to the members, and std::tuple
implements operator<
which compares its elements (the members of the object in this case) lexicographically.
In your case, using member operator<
:
bool operator<(const ParserKey & other) const
{
return std::tie(compno_, resno_, precinctIndex_) <
std::tie(other.compno_, other.resno_, other.precinctIndex_);
}
Live example https://godbolt.org/z/v433v54jz
C++ map with custom key
Try to consider the case that key1 > rhs.key1
and key2 == rhs.key2
and key3 < rhs.key3
, the operator <
would return true
which is not expected.
You could keep (key1 == rhs.key1)
in the last brance of the operator ||
in the operator <
. e.g.
bool operator < (const CustomKey & rhs) const {
return ((key1 < rhs.key1) ||
((key1 == rhs.key1) && (key2 < rhs.key2)) ||
((key1 == rhs.key1) && (key2 == rhs.key2) && (key3 < rhs.key3)));
}
LIVE
How to create a map with custom class/comparator as key
Why isn't your version working?
You did well to create your own comparison function. To answer your question, you have an error in your operator<()
function such that only returns true if m_f
is outside of tolerance and m_t
is within tolerance, which I'm guessing is not what you desired. Let's take a look.
int s_cmp = (abs(itemKey.m_f - m_f) > m_fEpsilon);
The above line basically is checking whether this->m_f
and itemKey.m_f
are within tolerance of eachother (meaning equal to each other). That is probably what was intended. Then you say
if (s_cmp == 0)
{
return (abs(itemKey.m_t - m_t) > m_tEpsilon);
}
If s_cmp
is true
, then it will have the value of 1
, and it will have a value of 0
for false
(meaning that they are not within tolerance of each other). Then you return true if the m_t
value is within tolerance. Up to this point, you return true
if m_f
is not equal (according to tolerance) and if m_t
is equal (according to tolerance). Then your last line of code
return s_cmp < 0;
will return true
always since a boolean converted to an integer cannot ever be negative.
How to get it working?
#include <iostream>
#include <string>
#include <map>
#include <cmath>
#include <vector>
struct ItemKey
{
double m_t;
double m_f;
static constexpr double t_eps = 3;
static constexpr double f_eps = 0.1;
ItemKey(double t, double f) : m_t(t), m_f(f) {}
bool operator<(const ItemKey& other) const
{
// Here it is assumed that f_eps and t_eps are positive
// We also ignore overflow, underflow, and NaN
// This is written for readability, and assumed the compiler will be
// able to optimize it.
auto fuzzy_less_than = [] (double a, double b, double eps) {
return a < b - eps;
};
bool f_is_less_than = fuzzy_less_than(this->m_f, other.m_f, f_eps);
bool f_is_greater_than = fuzzy_less_than(other.m_f, this->m_f, f_eps);
bool f_is_equal = !f_is_less_than && !f_is_greater_than;
bool t_is_less_than = fuzzy_less_than(this->m_t, other.m_t, t_eps);
return f_is_less_than || (f_is_equal && t_is_less_than);
}
};
int main()
{
using namespace std;
// The pairs are the respective values of m_t and m_f.
vector<pair<double, double>> pairs;
// These two should belong in one bucket
// -> (109.9, 9.0), because m_f differs by 0.09 and m_t differs by just 1
pairs.emplace_back(109.9, 9.0);
pairs.emplace_back(110.9, 9.09);
// This one is separate from above two beause even though m_t is in range,
// m_f is beyong tolerance level
pairs.emplace_back(109.5, 10.0);
// Same for this as well, here both m_t and m_f are beyong tolerance of any
// of the two categories found above
pairs.emplace_back(119.9, 19.0);
// This one matches the second bucket - (109.5, 10.0)
pairs.emplace_back(109.9, 10.05);
// And this one too.
pairs.emplace_back(111.9, 9.87);
map<ItemKey, size_t> itemMap;
for (const auto& item: pairs)
{
ItemKey key(item.first, item.second);
auto iter = itemMap.find(key);
if (iter == itemMap.end())
{
itemMap[key] = 1;
}
else
{
itemMap[iter->first] = itemMap[iter->first] + 1;
}
}
// The map should have three keys
// - (109.9, 9.0) -> count 2
// - (109.5, 10.0) -> count 3
// - (119.9, 19.0) -> count 1
cout << itemMap.size();
cout << "itemMap contents:" << endl;
for (auto& item : itemMap) {
cout << " (" << item.first << ", " << ")" << endl;
}
return 0;
}
There are a few things I changed above. I have a few suggestions also unrelated to the programming mistake:
- Do not store boolean values into integer variables.
There's a reason that C++ introduced thebool
type. - Write your code to be readable and in a way that the compiler
can easily optimize. You may notice I used a lambda expression
and multiple booleans. Smart compilers will inline the calls to
that lambda expression since it is only used within the local scope.
Also smart compilers can simplify boolean logic and make it
performant for me. - The
m_tEpsilon
andm_fEpsilon
are probably not good to be
changable variables of the class. In fact, it may be bad if one
object has a different epsilon than another one. If that were the
case, which do you use when you do the<
operator? For this
reason, I set them asstatic const
variables in the class. - For constructors, it is better to initialize your variables in the
initializer list rather than in the body of the constructor. That
is unless you are doing dynamic resource allocation, then you would
want to do it in the constructor and make sure to clean it up if
you end up throwing an exception (preferrably using the RAII
pattern). I'm starting to get too far off topic :) - Even though
class
andstruct
are basically identical except for
the default protection level (class
is private by default andstruct
is public by default). It is convention to have it as a
struct if you want direct access to the member variables. Although,
in this case, I would probably set your class as immutable. To do
that, set them_t
andm_f
as private variables and have a getterm()
andf()
. It might be a bad idea to modify anItemKey
instance in a map after it has been inserted.
Potential problems with this approach
One of the problems you have with your approach here is that it will be dependent on the order in which you add elements. Consider the following pairs to be added: (3.0, 10.0) (5.0, 10.0) (7.0, 10.0)
. If we add them in that order, we will get (3.0, 10.0) (7.0, 10.0)
, since (5.0, 10.0)
was deemed to be equal to (3.0, 10.0)
. But what if we were to have inserted (5.0, 10.0)
first, then the other two? Well then the list would only have one element, (5.0, 10.0)
, since bother of the others would be considered equal to this one.
Instead, I would like to suggest that you use std::multiset
instead, of course this will depend on your application. Consider these tests:
void simple_test_map() {
std::map<ItemKey, size_t> counter1;
counter1[{3.0, 10.0}] += 1;
counter1[{5.0, 10.0}] += 1;
counter1[{7.0, 10.0}] += 1;
for (auto &itempair : counter1) {
std::cout << "simple_test_map()::counter1: ("
<< itempair.first.m_t << ", "
<< itempair.first.m_f << ") - "
<< itempair.second << "\n";
}
std::cout << std::endl;
std::map<ItemKey, size_t> counter2;
counter2[{5.0, 10.0}] += 1;
counter2[{3.0, 10.0}] += 1;
counter2[{7.0, 10.0}] += 1;
for (auto &itempair : counter2) {
std::cout << "simple_test_map()::counter2: ("
<< itempair.first.m_t << ", "
<< itempair.first.m_f << ") - "
<< itempair.second << "\n";
}
std::cout << std::endl;
}
This outputs:
simple_test_map()::counter1: (3, 10) - 2
simple_test_map()::counter1: (7, 10) - 1
simple_test_map()::counter2: (5, 10) - 3
And for the multiset variant:
void simple_test_multiset() {
std::multiset<ItemKey> counter1 {{3.0, 10.0}, {5.0, 10.0}, {7.0, 10.0}};
for (auto &item : counter1) {
std::cout << "simple_test_multiset()::counter1: ("
<< item.m_t << ", "
<< item.m_f << ")\n";
}
std::cout << std::endl;
std::multiset<ItemKey> counter2 {{5.0, 10.0}, {3.0, 10.0}, {7.0, 10.0}};
for (auto &item : counter2) {
std::cout << "simple_test_multiset()::counter2: ("
<< item.m_t << ", "
<< item.m_f << ")\n";
}
std::cout << std::endl;
std::cout << "simple_test_multiset()::counter2.size() = "
<< counter2.size() << std::endl;
for (auto &item : counter1) {
std::cout << "simple_test_multiset()::counter2.count({"
<< item.m_t << ", "
<< item.m_f << "}) = "
<< counter1.count(item) << std::endl;
}
std::cout << std::endl;
}
This outputs
simple_test_multiset()::counter1: (3, 10)
simple_test_multiset()::counter1: (5, 10)
simple_test_multiset()::counter1: (7, 10)
simple_test_multiset()::counter2: (5, 10)
simple_test_multiset()::counter2: (3, 10)
simple_test_multiset()::counter2: (7, 10)
simple_test_multiset()::counter2.count({3, 10}) = 2
simple_test_multiset()::counter2.count({5, 10}) = 3
simple_test_multiset()::counter2.count({7, 10}) = 2
simple_test_multiset()::counter2.size() = 3
Note that count()
here returns the number of elements within the multiset that are considered equal to the ItemKey
passed in. This may be advantageous for situations where you want to ask "how many of my points are within my tolerance of a new point?"
Good luck!
Related Topics
How to Read a File into Vector in C++
Of Memory Management, Heap Corruption, and C++
C++ Opencv Image Sending Through Socket
Qtcpsocket: Reading and Writing
Loop with a Zero Execution Time
How to Force Gcc to Assume That a Floating-Point Expression Is Non-Negative
Why Does the C++ Standard Algorithm "Count" Return a Difference_Type Instead of Size_T
How Are the _Cplusplus Directive Defined in Various Compilers
Eclipse C++:"Program "G++" Not Found in Path"
Is Wchar_T Needed for Unicode Support
Why and How to Use Namespaces in C++
How to Determine the Amount of Linux System Ram in C++
Standard Way to Build a Chrome Extension into Chromium
How to Serialize Derived Template Classes with Boost.Serialize
Opencv Surf Function Is Not Implemented
Debug Assertion Failed! Expression: _Acrt_First_Block == Header