Searching in a stl map

Question

I have a map with the pointer of a struct as key.

std::map < struct1*, struct2>;

struct struct1{ int x; char a[10]; }; struct struct2 { int x; };

The key is the pointer to struct1. the struct1 has the member called x.

I have to search the map by the member x of struct1.

Is it possible to search without looping through all the elements in the map?

I tried below code but it is not working.

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;
}

It's not working because the *pointer* `&fk1` is not present in your map. If you want lookup to occur using what is being pointed to instead of using the pointer itself then you need a custom comparator. — john, Dec 03 '18 at 10:04
Your map is ordered by a collection of addresses as keys. Whether that is proper or not only you can say (not unheard of, but it is a little odd). Therefore there is no simple search without being your basic O(n) linear traversal. It's not like a custom comparator is going to be any help *after* the map is already populated and ordered by something completely different. If you use that comparator as as the actual ordering of the map when being built, *then* it will be a tremendous help, but be sure it provides strict weak ordering over the key set. — WhozCraig, Dec 03 '18 at 10:11
Are you sure you want a `map` and not a `map` ? Pointers are not really that useful as keys — 463035818_is_not_an_ai, Dec 03 '18 at 11:19

score 0 · Answer 1 · answered Dec 03 '18 at 10:11

0

Use a custom comparator to pass the values being pointed at to your already existing operator<. Like this

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;

answered Dec 03 '18 at 10:11

john

85,011
4
57
81

I tried your suggestion I am getting following errors Error 3 error C2679: binary '!=' : no operator found which takes a right-hand operand of type 'std::_Tree<_Traits>::iterator' (or there is no acceptable conversion) Error 1 error C2676: binary '<' : 'const struct1' does not define this operator or a conversion to a type acceptable to the predefined operator Error 2 error C2440: 'initializing' : cannot convert from 'std::_Tree<_Traits>::iterator' to 'std::_Tree<_Traits>::iterator' – user369287 Dec 03 '18 at 10:25
You need to change `std::map::iterator` to `std::map::iterator`, or you could use a typedef for `std::map` or you could use C++11 features and say `auto x = ...` – john Dec 03 '18 at 10:33

Caleth · Answer 2 · 2018-12-03T11:50:29.983

Let's expand the default parameters of m:

std::map<struct1 *, struct2, std::less<struct1 *>, std::allocator<std::pair<const struct1 *, struct2> >

We see that the comparator of the map is std::less<struct1 *>, which will test the numeric value of it's pointer arguments. It does not call struct1::operator <.

If have a C++14 compiler, and want to look up by the int member, you should use a custom comparator that is transparent, e.g.

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; }
};

Used like

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;
}

how to declare iterator this code FatKey fk1; fk1.x=1; std::map::iterator it_1 = m.find(&fk1); gives me the error C2679: binary '=' : no operator found which takes a right-hand operand of type 'std::_Tree<_Traits>::iterator' (or there is no acceptable conversion) — user369287, Dec 03 '18 at 11:21
@user369287 You need to match the type of iterator to the **exact** map type. `std::map::iterator` is unrelated to `std::map::iterator`. In cases like this, a type alias (`typedef`) is helpful. — Caleth, Dec 03 '18 at 11:53

score 0 · Answer 3 · answered Dec 03 '18 at 11:29

0

You can use std::find_if function, like that:

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;});

answered Dec 03 '18 at 11:29

snake_style

1,139
7
16

@how to modify above code c++9.0(visual studio 2008) – user369287 Dec 03 '18 at 11:38

Searching in a stl map

3 Answers3