Я создал структуру для использования в качестве ключа на карте, чтобы избежать дублирования элементов. Структура содержит указатели на дочерние и одноуровневые элементы своего типа. Для карты я создал собственный компаратор, который должен рекурсивно просматривать элемент, дочерние элементы и братья и сестры, пока не будет найдено различие, чтобы убедиться, что элементы одинаковы. Однако по какой-то причине это не работает, и я все еще получаю дубликаты. Проверив их в отладчике, я пришел к выводу, что они действительно одинаковы насквозь, поэтому проблема, вероятно, должна быть где-то там.
Это структура.
struct controlIdentifier
{
DWORD m_dwID;
DWORD m_dwDefaultID;
DWORD m_dwDisableID;
BYTE m_bType;
int m_nWidth;
int m_nHeight;
int m_nMargineH;
int m_nMargineV;
shared_ptr<controlIdentifier> m_pCHILD;
shared_ptr<controlIdentifier> m_pNEXT;
bool operator<(const controlIdentifier& id) const
{
if (m_dwDefaultID < id.m_dwDefaultID)
return true;
if (m_dwDisableID < id.m_dwDisableID)
return true;
if (m_bType < id.m_bType)
return true;
if (m_nWidth < id.m_nWidth)
return true;
if (m_nHeight < id.m_nHeight)
return true;
if (m_nMargineH < id.m_nMargineH)
return true;
if (m_nMargineV < id.m_nMargineV)
return true;
if (!m_pCHILD && id.m_pCHILD)
return true;
if (m_pCHILD && !id.m_pCHILD)
return false;
if (!m_pNEXT && id.m_pNEXT)
return true;
if (m_pNEXT && !id.m_pNEXT)
return false;
bool smaller = false;
if (m_pCHILD && id.m_pCHILD)
smaller = *m_pCHILD < *id.m_pCHILD;
if (!smaller)
{
if (m_pNEXT && id.m_pNEXT)
return *m_pNEXT < *id.m_pNEXT;
}
else
return smaller;
return false;
}
};
И вот как это используется.
struct cmpBySharedPtr {
bool operator()(const shared_ptr<controlIdentifier>& a, const shared_ptr<controlIdentifier>& b) const {
return *a < *b;
}
};
std::set<FRAMEDESC_SHAREDPTR> m_curFrames;
std::map<shared_ptr<controlIdentifier>, FRAMEDESC_SHAREDPTR, cmpBySharedPtr> m_serialFrames;
for (auto&& frame : m_curFrames)
{
shared_ptr<controlIdentifier> id;
makeIdentifiers(frame, id);
id->m_dwID = newId;
auto find = m_serialFrames.find(id);
if (find == m_serialFrames.end())
{
m_serialFrames.insert(std::pair(id, frame));
newId++;
}
}
m_dwID не сравнивается намеренно.
Рассмотрим A = (child = 5, next = 6)
и B = (child = 6, next = 5)
. Теперь A<B
истинно, поскольку (A.child < B.child)
истинно, и он просто возвращает это. Теперь рассмотрим B<A
. B.child < A.child
равно false, поэтому он проверяет поля next
. Теперь B.next < A.next
истинно, поэтому ваше сравнение возвращает true.
Так что это бессмысленно -> A<B
верно и B<A
верно. Это означает, что ваш компаратор недействителен.
Технический термин для этого — компаратор требует строгого слабого упорядочения — см. https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings. Ваш компаратор нарушает требование асимметрии.
Вдобавок к этому более безопасным шаблоном (для более ранних участников) является if (x.m1 < y.m1) return true; else if (y.m1 < x.m1) return false; else if (x.m2 < y.m2) return true; else if
... Или, что более удобно, const auto members1 = std::make_tuple(x.m1, x.m2, ...); const auto members2 = std::make_tuple(y.m1, y.m2, ...); if (members1 < members2) return true; else if (members2 < members1) return false; else
...
Вы можете построить operator <
, сравнивая поле за полем. Но то, что ты сделал, слишком мало. В основном это должно выглядеть так:
bool operator < (const A& left, const A& right)
{
if (left.firstField < right.firstField) return true;
if (right.firstField < left.firstField) return false; // this case is missing
if (left.secondField < right.secondField) return true;
if (right.secondField < left.secondField) return false; // this case is missing
....
return false;
}
Вы упускаете случаи, когда можно сделать вывод, что левый объект наверняка "больше", чем правый.
Из здесь: «Говоря неточно, два объекта a и b считаются эквивалентными (не уникальными), если ни один из них сравнивается меньше, чем другой:
!comp(a, b) && !comp(b, a)
». Это кажется хорошим началом для создания тестового примера.