Getting elements from structs in std::map with "partial values"?

[BytePtr]

Hello all.
It was hard to make title for this topic.

I have a simple code:

#include <iostream>
#include <map>

using namespace std;

struct car
{
       char* color;
       int nr_of_gears;
       int nr_of_doors;
       int max_speed;
};

int main(int argc, char *argv[])
{
    map<unsigned long, car> cars;
    
    car car1;
    car car2;
    
    car1.color = "black";
    car1.max_speed = 250;
    car1.nr_of_doors = 2;
    car1.nr_of_gears = 5;    
    
    car2.color = "red";
    car2.max_speed = 350;
    car2.nr_of_doors = 4;
    car2.nr_of_gears = 6;    
    
    cars[111] = car1;
    cars[222] = car2;
    
    cout << cars[111].color << endl;
    cout << cars[222].color << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

As you can see, i can access the group of items with unique key: 111 or 222 in this example and display values of structs individually.

But is it possible somehow just supply to this std::map just for example string: red or integer value: 350 and it tells me to which car this color name or max_speed belongs?
In this case here, it should say: car2, because car2 has these values.

Is std::map even able to do that?


Im using DevC++ if it matters.

[Paul McKenzie]

But is it possible somehow just supply to this std::map just for example string: red or integer value: 350 and it tells me to which car this color name or max_speed belongs?

What will happen if there is more than one red car or more than one care with max speed of 350?

You will have to search the map yourself, or create a single key that represents all the information in the struct.

Im using DevC++ if it matters.

So why post in the Visual C++ forum when you have the non-Visual C++ forum for these types of questions?

Regards,

Paul McKenzie

[VictorN]

... is it possible somehow just supply to this std::map just for example string: red or integer value: 350 and it tells me to which car this color name or max_speed belongs?
In this case here, it should say: car2, because car2 has these values.

Is std::map even able to do that?

But what does car2 mean in this context? You cannot an object identifier in your run-time processing because such an identifier not more exists.
It only exists while compiling.

And it has nothing to do with the std::map. The same is for std::vector and just any plain array of struct car objects.

Hello all.
It was hard to make title for this topic.

I have a simple code:

#include <iostream>
#include <map>

using namespace std;

struct car
{
       char* color;
       int nr_of_gears;
       int nr_of_doors;
       int max_speed;
};

Woldn't you like to change the the type of color member from char* to string?

[BytePtr]

Hi Paul.
Thanks for reply.

Actually i forgot to tell that, the struct values will be always unique.
At least i hope so. I just encountered the problem, that i need to figure out, to which item in std::map the supplied parameter belongs.
And it must be as fast as possible. Because there will be a lot of work for it.


Sorry for the wrong subforum. Somebody please move it.


VictorN:

string is better maybe yes.


Well, i guess i have to group somehow my data then in std::map. Make an map of vectors or something, or whatever. I have seen similar thing, i didn't know it's possible. But code was pretty messy.

I know for sure that std::map must contain structs, to which i pass item values at runtime. Like in my example above.
Later i must have to do the reverse, figure out somehow to which "thing" in std::map the supplied example value (250,6 or whatever) belongs.


Seems harder than i thought.

[VictorN]

Actually i forgot to tell that, the struct values will be always unique.
At least i hope so.

But the struct car you showed does not support any object "uniqueness"!

[Philip Nicoletti]

As has been pointed out, there is really nothing unique about your fields. If you
have a large number of entries as you stated, there are still on a few unique values
for items such as number of doors.

At any rate, in general if you have a large number of entries and you need to search
on multiple fields, you would use a database.

You can simulate this using a number of multimaps ... one for each field. A small example:
(uses shared_ptr)

#include <iostream>
#include <string>
#include <map>
#include <memory>

using namespace std;

struct car
{
   string color;
   int nr_of_gears;
   int nr_of_doors;
   int max_speed;
   
   car(const string & color_in="", int gears=6 , int doors = 4 , int speed = 100) :
      color(color_in) , nr_of_gears(gears) , nr_of_doors(doors) , max_speed(speed) {}
};

typedef multimap< string,shared_ptr<car> > StringMap;
typedef multimap<    int,shared_ptr<car> > IntMap;

void AddCar(StringMap & map_color , IntMap & map_gears , IntMap & map_doors , 
      IntMap & map_speed , const string & color , int gears , int doors , 
      int speed)
{
   shared_ptr<car> p ( new car(color,gears,doors,speed) );
   
   map_color.insert( make_pair(color,p) );
   map_gears.insert( make_pair(gears,p) );
   map_doors.insert( make_pair(doors,p) );
   map_speed.insert( make_pair(speed,p) );
}

int main()
{
   StringMap map_color;
   IntMap    map_gears;
   IntMap    map_doors;
   IntMap    map_speed;
   
   AddCar(map_color , map_gears , map_doors , map_speed ,
	  "red" , 6 , 4 , 100);
   AddCar(map_color , map_gears , map_doors , map_speed ,
	  "blue" , 6 , 5 , 120);
   AddCar(map_color , map_gears , map_doors , map_speed ,
	  "white" , 6 , 4 , 110);
   AddCar(map_color , map_gears , map_doors , map_speed ,
	  "red" , 6 , 2 , 100);
	  
   StringMap::iterator its;
   IntMap::iterator    iti;
   	  
   // find all red cars
   
   for (its=map_color.lower_bound("red"); its!= map_color.upper_bound("red"); ++its)
   {
     cout << its->second->color       << " : " << its->second->nr_of_gears << " : " 
          << its->second->nr_of_doors << " : " << its->second->max_speed
          << "\n";
   }
   
   cout << "\n\n";
   
   // find all cars with a speed between 110 and 120
   
   for (iti=map_speed.lower_bound(110); iti!= map_speed.upper_bound(120); ++iti)
   {
     cout << iti->second->color       << " : " << iti->second->nr_of_gears << " : " 
          << iti->second->nr_of_doors << " : " << iti->second->max_speed
          << "\n";
   }
   
   return 0;
}

[Lindley]

You should check out the Boost.MultiIndex library.

If you'd prefer not to use boost, then here's what it does. The actual objects are stored in some data structure, perhaps a vector. Then, additional containers of indexes into that vector are created, and each container of indexes is sorted according to some criteria in the objects. This enables fast lookups on any field by using the appropriate index container.

[BytePtr]

Lindley, so you say that without sorting it will not be as fast as it should?

Pretty bad, i think in the code i will use, the additional sorting each time would hit the performance of whole application.

But i will not know unless i try it out.


Thanks. Im gonna try to write some code.

[Lindley]

Lindley, so you say that without sorting it will not be as fast as it should?

If you want fast lookups, then you either need your container to be hashed or sorted by the field you are interested in looking up. Sorting is often more intuitive, and has better worst-case time guarantees, but can be slightly slower than hash lookups on average.

Pretty bad, i think in the code i will use, the additional sorting each time would hit the performance of whole application.

There are different ways to keep things sorted. Using an array or vector is best if insertions and deletions are rare compared to lookups. If insertions are rare but deletions are not, a std:eque may be slightly preferable since it won't have to move as many entries around in memory on deletions.

On the other hand, if you expect insertions and deletions to be common and you also want fast lookups, then a tree-based data structure such as a std::set or std::map (or multiset or multimap) may be a better choice.

Any of these options can be done in such a way that it stores indexes or iterators into a different container rather than the objects of interest themselves, so long as an appropriate functor is defined to do the lookup.

[BytePtr]

Thanks, you gave me great push, i will try to code out something.
It will be interesting.

Will let you know how it goes and what solution i found.

[BytePtr]

Lindley or somebody.

How efficient or not efficient is looping through map with iterator, if it has lot's of items, let's say, 500-10000.
Does it get's slower the more items the map has?

How is the performance if i am doing it alot?

I know that std::map itself is pretty fast thing and i like it. But i don't know much about the speed of other it's "parts".

[Lindley]

Looping through all elements with an iterator is O(n). That is likely to be the case with any container.

That's not the preferred way to do a search, of course. The map's find() method is O(log n).