Hi, In my work I have repeatedly had the need to create a sorted array in which I can insert/lookup from using a key. This is like a map except that it uses an array. The contention is that in some cases, it is faster to insert/remove from a sorted array rather than traversing a tree (the underlying data structure for a map) which involves pointer de-referencing. I would like to call the class linear_map. Looking forward to feedback from everyone. Many thanks, - Amir
On Tuesday, July 17, 2012 03:13 PM, Amir Ansari wrote:
Hi,
In my work I have repeatedly had the need to create a sorted array in which I can insert/lookup from using a key. This is like a map except that it uses an array. The contention is that in some cases, it is faster to insert/remove from a sorted array rather than traversing a tree (the underlying data structure for a map) which involves pointer de-referencing. I would like to call the class linear_map. Looking forward to feedback from everyone.
Does it differ from boost::flat_map: http://www.boost.org/doc/libs/1_50_0/doc/html/boost/container/flat_map.html Ben
boost::flat_map seems to provide exactly what I am looking for but there is one deal breaking caveat - it stores the key separately from the data. I don't know if this problem is already solved, but the way I see it, if the data needs the key for some other computation, we either need to replicate the key (memory usage) or take the computation out of the data class, which breaks encapsulation. Do you think it would make sense to have another container which simply uses the comparator to directly compare the objects being stored? ________________________________ From: Ben Pope <benpope81@gmail.com> To: boost@lists.boost.org Sent: Tuesday, July 17, 2012 1:15 PM Subject: Re: [boost] Proposal: Linear map On Tuesday, July 17, 2012 03:13 PM, Amir Ansari wrote:
Hi,
In my work I have repeatedly had the need to create a sorted array in which I can insert/lookup from using a key. This is like a map except that it uses an array. The contention is that in some cases, it is faster to insert/remove from a sorted array rather than traversing a tree (the underlying data structure for a map) which involves pointer de-referencing. I would like to call the class linear_map. Looking forward to feedback from everyone.
Does it differ from boost::flat_map: http://www.boost.org/doc/libs/1_50_0/doc/html/boost/container/flat_map.html Ben _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wednesday 18 July 2012 06:53:45 Amir Ansari wrote:
boost::flat_map seems to provide exactly what I am looking for but there is one deal breaking caveat - it stores the key separately from the data. I don't know if this problem is already solved, but the way I see it, if the data needs the key for some other computation, we either need to replicate the key (memory usage) or take the computation out of the data class, which breaks encapsulation. Do you think it would make sense to have another container which simply uses the comparator to directly compare the objects being stored?
Does flat_set suit your requirements?
Thanks. This is exactly what I was looking for. Some questions: 1. Is there any container that allows inserting without providing a value of the contained type, but rather, some other type? Essentially, it would rely on a non-default constructor that takes the other type as input. 2. Is there some specialization for flat_set with the same semantics as ptr_vector ? ________________________________ From: Andrey Semashev <andrey.semashev@gmail.com> To: boost@lists.boost.org Sent: Wednesday, July 18, 2012 7:01 PM Subject: Re: [boost] Proposal: Linear map On Wednesday 18 July 2012 06:53:45 Amir Ansari wrote:
boost::flat_map seems to provide exactly what I am looking for but there is one deal breaking caveat - it stores the key separately from the data. I don't know if this problem is already solved, but the way I see it, if the data needs the key for some other computation, we either need to replicate the key (memory usage) or take the computation out of the data class, which breaks encapsulation. Do you think it would make sense to have another container which simply uses the comparator to directly compare the objects being stored?
Does flat_set suit your requirements? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wednesday 18 July 2012 07:40:17 Amir Ansari wrote:
Thanks. This is exactly what I was looking for. Some questions:
1. Is there any container that allows inserting without providing a value of the contained type, but rather, some other type? Essentially, it would rely on a non-default constructor that takes the other type as input.
Yes, many Boost containers support emplace*() methods. In C++11, STL containers also support it.
2. Is there some specialization for flat_set with the same semantics as ptr_vector ?
I'm not sure I understand. Do you intend to store pointers in flat_set? If so, you can store std::unique_ptr's or shared_ptr's and specify your custom ordering predicate to order pointers by their pointees.
2. Is there some specialization for flat_set with the same semantics as ptr_vector ?
I'm not sure I understand. Do you intend to store pointers in flat_set? If so, you can store std::unique_ptr's or shared_ptr's and specify your custom ordering predicate to order pointers by their pointees.
The documentation for boost::ptr_vector says that using the smart pointers inside a vector isn't ideal... it's one of the reasons why ptr_vector exists. I was wondering if that logic applies still when flat_set holds pointers and is there a solution available? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wednesday 18 July 2012 08:01:09 Amir Ansari wrote:
2. Is there some specialization for flat_set with the same semantics as ptr_vector ?
I'm not sure I understand. Do you intend to store pointers in flat_set? If so, you can store std::unique_ptr's or shared_ptr's and specify your custom ordering predicate to order pointers by their pointees.
The documentation for boost::ptr_vector says that using the smart pointers inside a vector isn't ideal... it's one of the reasons why ptr_vector exists. I was wondering if that logic applies still when flat_set holds pointers and is there a solution available?
If you have unique_ptr, standard containers can hold exclusive pointers, which practically defeats the efficiency penalty of storing shared_ptr's. Pointer containers also provide other features but if all you need is store pointers in containers, unique_ptr and STL containers are enough. The same applies to flat_set.
OK. Fair enough. But I was thinking if flat_set could be configured so that the underlying container (vector/ptr_vector) could be changed, that would be awesome. Anyway, that was just my thoughts. Many thanks for your patience and very clear answers. ________________________________ From: Andrey Semashev <andrey.semashev@gmail.com> To: boost@lists.boost.org Sent: Wednesday, July 18, 2012 8:12 PM Subject: Re: [boost] Proposal: Linear map On Wednesday 18 July 2012 08:01:09 Amir Ansari wrote:
2. Is there some specialization for flat_set with the same semantics as ptr_vector ?
I'm not sure I understand. Do you intend to store pointers in flat_set? If so, you can store std::unique_ptr's or shared_ptr's and specify your custom ordering predicate to order pointers by their pointees.
The documentation for boost::ptr_vector says that using the smart pointers inside a vector isn't ideal... it's one of the reasons why ptr_vector exists. I was wondering if that logic applies still when flat_set holds pointers and is there a solution available?
If you have unique_ptr, standard containers can hold exclusive pointers, which practically defeats the efficiency penalty of storing shared_ptr's. Pointer containers also provide other features but if all you need is store pointers in containers, unique_ptr and STL containers are enough. The same applies to flat_set. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I like to reuse tuple<> to quickly create new types as: class my_data : public boost::tuple<int, int, bool, int> { // The following could go into a macro: enum { Id, Price, Sellable, Shares, Gain } // Ensure copy constructor my_data(const my_data & d) : boost::tuple<int, int, bool, int>(d) {} }; The enum and copy constructor could be defined using a macro whose signature is: HANDLE_TUPLE4(Class, Type1, Name1, Type2, Name2, Type3, Name3, Type4, Name4) I find this to be a lot less clutter than: class my_data { int Id; int Price; bool Sellable; int Shares; int Gain; // Boiler plate code... }; Users of my_data can now access members as obj.get<my_data::Id>() The only thing in the above is that I can't declare the data to be protected so that users of my_data won't be able to do get<my_data::Price> = 0; for example. Ideally there should be a way so that some of the data members could be private to my_data and not exposed to even derived classes but I don't see a way for that. But protected could be handled through a slight modification in tuple: enum AccessSpecifier { Protected, Public } template< enum AccessSpecifier, typename... Args> class typle... template<typename.. Args> class tuple<Protected, Args...> // Make sure Args are declared protected With some specialization magic, we can let users define which arguments should be public (that is, the get<> method) and which should be protected. Does this make sense? I think we could add more magic so that users can only get and NOT set the values. Thoughts?
The goal of this idea sounds great to me. It works to solve one of the exact complaints I've received when I try to sell coworkers on the idea of using tuples. Cheers! Andrew Hundt On Fri, Jul 20, 2012 at 12:52 AM, Amir Ansari <amir.ansari80@ymail.com>wrote:
I like to reuse tuple<> to quickly create new types as:
class my_data : public boost::tuple<int, int, bool, int> {
// The following could go into a macro:
enum { Id, Price, Sellable, Shares, Gain } // Ensure copy constructor my_data(const my_data & d) : boost::tuple<int, int, bool, int>(d) {}
};
The enum and copy constructor could be defined using a macro whose signature is:
HANDLE_TUPLE4(Class, Type1, Name1, Type2, Name2, Type3, Name3, Type4, Name4)
I find this to be a lot less clutter than:
class my_data { int Id; int Price; bool Sellable; int Shares; int Gain;
// Boiler plate code... };
Users of my_data can now access members as obj.get<my_data::Id>() The only thing in the above is that I can't declare the data to be protected so that users of my_data won't be able to do get<my_data::Price> = 0; for example. Ideally there should be a way so that some of the data members could be private to my_data and not exposed to even derived classes but I don't see a way for that. But protected could be handled through a slight modification in tuple:
enum AccessSpecifier { Protected, Public }
template< enum AccessSpecifier, typename... Args> class typle...
template<typename.. Args> class tuple<Protected, Args...> // Make sure Args are declared protected
With some specialization magic, we can let users define which arguments should be public (that is, the get<> method) and which should be protected. Does this make sense? I think we could add more magic so that users can only get and NOT set the values. Thoughts?
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Please, start a new thread for each new subject instead of replaying to an existing one. Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/Proposal-Linear-map-tp4633144p4633350.htm... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (5)
-
Amir Ansari -
Andrew Hundt -
Andrey Semashev -
Ben Pope -
Vicente Botet