std::map<> - like structure for other than std::pair<>?
Several times I have run into a use case where I have some object that I would like to access via something like a std::map<>, but which already contains a member that I would like to use as a key. Is there any data structure that "acts like a map", but instead of storing std::pair<key,value> allows me to store an object directly, and specify what member of that object is the key value? I can give a specific use case for this: For those of you not familiar with the SCA, there is an object called CF::Properties. This is a CORBA sequence (think std::vector) of objects of {string name, CORBA::Any value}, used to store metadata. Ideally, I'd like to have an object that I could initialize from that sequence that would allow me to do things like this: inline string &getKey(CF::Property &x) { return x.name; } void foo(CF::Properties &meta) { mapLikeThing<CF::Property,getKey> myMap(meta); double sampleRate; myMap["SampleRate"] >> sampleRate; setHardwareSampleRate(sampleRate); }
On 14 Apr 2015, at 13:26, David Hagood <david.hagood@gmail.com> wrote:
Several times I have run into a use case where I have some object that I would like to access via something like a std::map<>, but which already contains a member that I would like to use as a key. Is there any data structure that "acts like a map", but instead of storing std::pair<key,value> allows me to store an object directly, and specify what member of that object is the key value?
I can give a specific use case for this:
For those of you not familiar with the SCA, there is an object called CF::Properties. This is a CORBA sequence (think std::vector) of objects of {string name, CORBA::Any value}, used to store metadata. Ideally, I'd like to have an object that I could initialize from that sequence that would allow me to do things like this:
inline string &getKey(CF::Property &x) { return x.name; }
void foo(CF::Properties &meta) { mapLikeThing<CF::Property,getKey> myMap(meta); double sampleRate; myMap["SampleRate"] >> sampleRate; setHardwareSampleRate(sampleRate); }
You can store your objects in a std::set instead of a map and then provide a custom compare function that compared your objects given your key in them. E.g. struct my_compare { bool operator() (const MyObj& lhs, const MyObj& rhs) const{ return lhs.name < rhs.name; } }; std::set<MyObj, my_compare> s;
On Tue, Apr 14, 2015 at 1:37 PM, M.A. van den Berg <thijs@sitmo.com> wrote:
You can store your objects in a std::set instead of a map and then provide a custom compare function that compared your objects given your key in them. E.g.
struct my_compare { bool operator() (const MyObj& lhs, const MyObj& rhs) const{ return lhs.name < rhs.name; } };
std::set<MyObj, my_compare> s;
set entries are const so this isn't usable in all cases. -- Olaf
One problem I see with using a set is that the whole data type is used as the key - if you do a find you have to supply the whole data type, not just the key, even though a custom compare operator may only consider part of the object as the key (to use the example use case I gave, you would have to supply a whole CF::Property to the find() function, not just the string). The data elements being const isn't really a problem - if you can remove and replace, it's almost as good as the elements being non-const, and it would be hard for a container to require the key element of the data to be const (so the sorting order of the list is not screwed up), but allow modification of the rest of the item.
On Wed, Apr 15, 2015 at 1:23 PM, David Hagood <david.hagood@gmail.com> wrote:
One problem I see with using a set is that the whole data type is used as the key - if you do a find you have to supply the whole data type, not just the key, even though a custom compare operator may only consider part of the object as the key (to use the example use case I gave, you would have to supply a whole CF::Property to the find() function, not just the string).
See http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/reference/hash_ind... and its concept of Compatible Key. This does exactly what you want I believe. --DD
Dominique Devienne <ddevienne <at> gmail.com> writes:
On Wed, Apr 15, 2015 at 1:23 PM, David Hagood <david.hagood <at> gmail.com> wrote:
One problem I see with using a set is that the whole data type is used as the key [...]
Adding to Dominique's answer, here's an example of how the thing could be done with Boost.MultiIndex: #include <boost/multi_index_container.hpp> #include <boost/multi_index/ordered_index.hpp> #include <boost/multi_index/member.hpp> #include <iostream> #include <string> #include <vector> using namespace boost::multi_index; struct Property { std::string name; int payload; }; typedef multi_index_container< Property, indexed_by< ordered_unique<member<Property,std::string,&Property::name>> > > set_t; int main() { std::vector<Property> meta= {{"hello",0},{"bye",1},{"world",3},{"boost",4}}; set_t s{meta.begin(),meta.end()}; std::cout<<s.find("boost")->payload<<"\n"; // prints 4 // change payload of "hello" to 5 auto it=s.find("hello"); s.modify(it,[](Property& x){x.payload=5;}); std::cout<<it->payload<<"\n"; // prints 5 } Joaquín M López Muñoz Telefónica
Thanks to everyone - yes, I think that is the solution I was looking for. I knew there had to be a solution - it just didn't make sense that something that solved problems like this didn't exist.
On Tue, Apr 14, 2015 at 4:26 AM, David Hagood <david.hagood@gmail.com> wrote:
Several times I have run into a use case where I have some object that I would like to access via something like a std::map<>, but which already contains a member that I would like to use as a key. Is there any data structure that "acts like a map", but instead of storing std::pair<key,value> allows me to store an object directly, and specify what member of that object is the key value?
You want Boost.MultiIndex: http://www.boost.org/doc/libs/release/libs/multi_index/doc/index.html
In my library Countertree ( set, multiset, map multimap concurrent and with access by position like the vectors ) I implemented the map as a data structure and a filter. Applying the filter you obtain the key. With the same nodes of the tree you can build a different maps, only changing the filter used. Imagine you have a map and each node have a code and a name, The map is sorted by the code. Extracting the nodes of the map, putting in a vector and inserting in map sorted by name,(the filter provide the name as key) it a easy operation. The access by positionof the trees , permit you new fast algorithms for create a map from a vector ( a 30000000 nodes need 6 seconds with 1 thread for to create a map, with 4 threads you can do in less than 3 seconds) The STL map need 35 seconds for to do it. All the implementations I know (GCC, VC++, Intel...) use a pair, and don't permit the change of the key The true problem is not to access to other element as use as second key, the problem is the sorting. If you need the data sorted by several keys simultaneously, you need multiindex. If when you sort by a second key, unsort the data by the first key, the procedure described could be good *The library countertree is pending of the final approval . You can find in https://github.com/fjtapia/countertree_2.0)
participants (7)
-
David Hagood -
Dominique Devienne -
Francisco José Tapia -
Joaquin M Lopez Munoz -
M.A. van den Berg -
Matt Calabrese -
Olaf van der Spek