Поиск на карте stl
У меня есть карта с указателем структуры в качестве ключа.
std :: map <struct1 *, struct2>;
struct struct1 {int x; char a [10]; }; struct struct2 {int x; };
Ключ - это указатель на struct1. структура struct1 имеет член с именем x.
Мне нужно выполнить поиск на карте по члену x структуры struct1.
Можно ли искать, не просматривая все элементы на карте?
Я пробовал код ниже, но он не работает.
include <iostream>
#include <map>
struct struct1 { int x; char a[10]; };
struct struct2{ int x; };
bool operator<(const struct1 & fk1, const struct1& fk2) {
return fk1.x < fk2.x;
}
int main()
{
std::map<struct1 *, struct2> m;
struct1 *f1 = new struct1();
f1->x =1;
strcpy(f1->a,"ab");
struct2 l1;
l1.x=10;
m.insert(std::make_pair(f1, l1));
struct1 fk1;
fk1.x=1;
std::map<struct1 *, struct2>::iterator x = m.find(&fk1);
if (x != m.end())
{
std::cout << x->first->x <<std::endl;
std::cout << x->first->a <<std::endl;
}
if (f1!=NULL)
delete f1;
return 0;
}
@john -как написать собственный компаратор?
Ваша карта упорядочена по набору адресов в качестве ключей. Правильно ли это или нет, только вы можете сказать (не неслыханно, но это немного странно). Следовательно, нет простого поиска, если бы он не был вашим основным линейным обходом O (n). Это не похоже на то, что настраиваемый компаратор поможет. после карта уже заполнена и упорядочена чем-то совершенно другим. Если вы используете этот компаратор в качестве фактического упорядочивания карты при построении, тогда, это будет огромным подспорьем, но убедитесь, что он обеспечивает строгое слабое упорядочение по набору ключей.
Вы уверены, что хотите map<struct1*,struct2>, а не map<struct1,struct2>? Указатели не так полезны, как ключи
Ответы 3
Используйте настраиваемый компаратор, чтобы передать указанные значения в уже существующий operator<. Нравится
struct Cmp
{
// use pointed to value for comparison
bool operator()(const struct1* x, const struct1* y) const { return *x < *y; }
};
std::map<struct1 *, struct2, Cmp> m;
Я попробовал ваше предложение. Я получаю следующие ошибки Ошибка 3 Ошибка C2679: двоичный '! =': Не найден оператор, который принимает правый операнд типа 'std :: _ Tree <_Traits> :: iterator' (или нет приемлемого преобразование) Ошибка 1 ошибка C2676: двоичный '<': 'const struct1' не определяет этот оператор или преобразование в тип, приемлемый для предопределенного оператора Ошибка 2 ошибка C2440: 'инициализация': невозможно преобразовать из 'std :: _ Tree < _Traits> :: iterator 'в' std :: _ Tree <_Traits> :: iterator '
Вам нужно изменить std::map<struct1 *, struct2>::iterator на std::map<struct1 *, struct2, Cmp>::iterator, или вы можете использовать typedef для std::map<struct1 *, struct2, Cmp>, или вы можете использовать функции C++ 11 и сказать auto x = ...
Давайте расширим параметры m по умолчанию:
std::map<struct1 *, struct2, std::less<struct1 *>, std::allocator<std::pair<const struct1 *, struct2> >
Мы видим, что компаратором карты является std::less<struct1 *>, который будет проверять числовое значение аргументов указателя. Это не звонитstruct1::operator <.
Если у вас есть компилятор C++ 14 и вы хотите искать по члену int, вы должны использовать настраиваемый компаратор, который является прозрачный, например
struct struct1_less
{
typedef void is_transparent;
// C++11 and later: using is_transparent = void;
// compare pointers
bool operator()(const struct1* lhs, const struct1* rhs) const { return lhs->x < rhs->x; }
// compare with int
bool operator()(const struct1* lhs, int rhs) const { return lhs->x < rhs; }
bool operator()(int lhs, const struct1* rhs) const { return lhs < rhs->x; }
};
Используется как
typedef std::map<struct1 *, struct2, struct1_less> struct1_lookup;
int main()
{
struct1_lookup m;
struct1 *f1 = new struct1();
f1->x =1;
strcpy(f1->a,"ab");
struct2 l1;
l1.x=10;
m.insert(std::make_pair(f1, l1));
struct1 fk1;
fk1.x=1;
struct1_lookup::iterator x = m.find(&fk1);
if (x != m.end())
{
std::cout << x->first->x <<std::endl;
std::cout << x->first->a <<std::endl;
}
delete f1;
return 0;
}
как объявить итератор этим кодом FatKey fk1; fk1.x = 1; std :: map <FatKey *, LightKey> :: iterator it_1 = m.find (& fk1); дает мне ошибку C2679: двоичный '=': не найден оператор, который принимает правый операнд типа 'std :: _ Tree <_Traits> :: iterator' (или нет приемлемого преобразования)
@ user369287 Вам необходимо сопоставить тип итератора с типом карты точный. std::map<struct1 *, struct2, struct1_less>::iterator не связан с std::map<struct1 *, struct2>::iterator. В подобных случаях полезно использовать псевдоним типа (typedef).
Вы можете использовать функцию std :: find_if, например:
int search_value = 222;
auto it = std::find_if (m.begin(), m.end(), [search_value](const pair<struct1*, struct2> &s){ return s.first->x == search_value;});
@ как изменить приведенный выше код C++ 9.0 (Visual Studio 2008)
Это не работает, потому что указатель
&fk1отсутствует на вашей карте. Если вы хотите, чтобы поиск выполнялся с использованием того, на что указывает указатель, вместо использования самого указателя, вам понадобится настраиваемый компаратор.