Request for conditional index feature in boost multi-index
Hi, First of all thanks for the great library, which had reduced our development time by a lot. In boost multi-index, we currently have almost all the indexing concepts integrated. Hence i am requesting for a new feature called conditional indexes, where in an index/view inside multi-index will only index a portion of the entries inside the entire multi-index(Say something that satisfies a functor). This is in resemblance to the partial indexes in Postgresql. I feel that would provide elegant solutions to lot of issues without forming round about solutions. For example i have a requirement where in there are two sets of data with the same search criteria, but different eviction criteria Say i have two sets of data with same search condition, but one set needs a MRU(Most Recently Used) list of 100 and the other set requires a MRU of 200. Say the entry is like this class Student { int student_no; char sex; std::string address; }; The search criteria is student_no, but for sex='m', we need MRU of 200 and for sex='f', we need a MRU of 100. Now i have a solution where in i introduce a new ordered index to maintain ordering. For example the IndexSpecifierList will be something like this typedef multi_index_container< Student, indexed_by< ordered_unique< member<Student, int, &Student::student_no> >, ordered_unique< composite_key< member<Student, char, &Student::sex>, member<Student, int, &Student::sex_specific_student_counter> > >
student_set
Here i have to introduce a new counter called sex_specific_student_counter, and during the eviction time, i need a logn search. Insertion also involves a extra logn complexity. Now instead if i have two sequenced indexes (like mentioned in the MRU example) in the place of second ordered index, but both with a condition on indexing only a few items, this would have looked more elegant and with better performance. Thanks in advance, Gokul.
Gokulakannan Somasundaram escribió:
Hi, First of all thanks for the great library, which had reduced our development time by a lot. In boost multi-index, we currently have almost all the indexing concepts integrated. Hence i am requesting for a new feature called conditional indexes, where in an index/view inside multi-index will only index a portion of the entries inside the entire multi-index(Say something that satisfies a functor). This is in resemblance to the partial indexes in Postgresql. I feel that would provide elegant solutions to lot of issues without forming round about solutions. For example i have a requirement where in there are two sets of data with the same search criteria, but different eviction criteria
Say i have two sets of data with same search condition, but one set needs a MRU(Most Recently Used) list of 100 and the other set requires a MRU of 200. Say the entry is like this [...]
The general request (composing partial indices to cover the whole sequence) is interesting and a considered it some years ago, though I never found the time to implement it (and I'm suspicious it might be a little too "smart" for the general public). In any case, I think you can solve your particular problem without that feature in a convenient manner. Please see the attached example and report whether it satisfies your needs. Best regards, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo #include <algorithm> #include <boost/multi_index_container.hpp> #include <boost/multi_index/hashed_index.hpp> #include <boost/multi_index/member.hpp> #include <boost/multi_index/random_access_index.hpp> #include <iostream> #include <iterator> #include <string> using namespace boost::multi_index; struct student { student(int num,char sex):num(num),sex(sex){} int num; char sex; friend std::ostream& operator<<(std::ostream& os,const student& s) { os<<"("<<s.num<<","<<s.sex<<") "; return os; } }; class student_mru_list { typedef multi_index_container< student, indexed_by< random_access<>, hashed_unique<member<student,int,&student::num> > >
student_list;
public: typedef student_list::iterator iterator; student_mru_list(std::size_t max_male,std::size_t max_female): max_male(max_male),max_female(max_female), size_male(0),size_female(0){} void insert(const student& s) { bool is_male=(s.sex=='m'); std::size_t& size =is_male? size_male :size_female; std::size_t max_size=is_male? max_male :max_female; iterator it =is_male? male_begin():female_begin(); std::pair<iterator,bool> p=sl.insert(it,s); if(!p.second){ /* duplicate item */ sl.relocate(it,p.first); /* put in front */ } else{ ++size; if(size>max_size){ /* keep the length bounded */ sl.erase(is_male?male_end()-1:female_end()-1); --size; } } } iterator male_begin(){return sl.begin();} iterator male_end(){return male_begin()+size_male;} iterator female_begin(){return male_end();} iterator female_end(){return sl.end();} iterator begin(){return male_begin();} iterator end(){return female_end();} private: student_list sl; std::size_t max_male,max_female; std::size_t size_male,size_female; }; void dump(student_mru_list& sl) { std::copy(sl.begin(),sl.end(),std::ostream_iterator<student>(std::cout)); std::cout<<std::endl; } int main() { student_mru_list sl(3,2); sl.insert(student(0,'m')); sl.insert(student(1,'f')); sl.insert(student(2,'m')); sl.insert(student(3,'f')); sl.insert(student(4,'m')); sl.insert(student(5,'f')); sl.insert(student(6,'m')); dump(sl); sl.insert(student(3,'f')); sl.insert(student(4,'m')); dump(sl); return 0; }
Hi, Thanks for the reply. But there is a mention in random_access<> like this "This added flexibility comes at a price: insertions and deletions at positions other than the end of the index have linear complexity" So isn't this a O(n) operation? But i quite gives me a hint that the random_access<> is more like std::deque than std::vector. Can you throw me little bit light on this? But the approach even suggests me to keep a iterator of sequenced<> cached and use it for male insertions. Thanks, Gokul. On Wed, Dec 22, 2010 at 3:59 PM, <joaquin@tid.es> wrote:
Gokulakannan Somasundaram escribió:
Hi, First of all thanks for the great library, which had reduced our development time by a lot. In boost multi-index, we currently have almost all the indexing concepts integrated. Hence i am requesting for a new feature called conditional indexes, where in an index/view inside multi-index will only index a portion of the entries inside the entire multi-index(Say something that satisfies a functor). This is in resemblance to the partial indexes in Postgresql. I feel that would provide elegant solutions to lot of issues without forming round about solutions. For example i have a requirement where in there are two sets of data with the same search criteria, but different eviction criteria
Say i have two sets of data with same search condition, but one set needs a MRU(Most Recently Used) list of 100 and the other set requires a MRU of 200. Say the entry is like this [...]
The general request (composing partial indices to cover the whole sequence) is interesting and a considered it some years ago, though I never found the time to implement it (and I'm suspicious it might be a little too "smart" for the general public).
In any case, I think you can solve your particular problem without that feature in a convenient manner. Please see the attached example and report whether it satisfies your needs.
Best regards,
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Wed, Dec 22, 2010 at 8:59 AM, <joaquin@tid.es> wrote:
The general request (composing partial indices to cover the whole sequence) is interesting and a considered it some years ago, though I never found the time to implement it (and I'm suspicious it might be a little too "smart" for the general public).
Sorry to wake up an old thread, but I've just encountered a problem where partial indices would be the perfect solution. I'm working on a problem where I have several unique identifiers for each object, but I'm not guaranteed that I have all of them at the same time. I can get updates from two sources, which don't necessarily don't use the same ID, yet they will sooner or later be linked. Using postgresql a simplified version could look like this: CREATE TABLE test( a text, b text, data text); CREATE UNIQUE INDEX test_a_par_uidx ON test(a) WHERE a IS NOT NULL; CREATE UNIQUE INDEX test_b_par_uidx ON test(b) WHERE a IS NOT NULL; Are we thinking of the same sort of partial indices? ... and is this something that is feasible to implement in multi_index_container? -- Eld på åren og sol på eng gjer mannen fegen og fjåg. [Jøtul] <demo> 2011 Tore Halvorsen || +052 0553034554
participants (3)
-
Gokulakannan Somasundaram
-
joaquin@tid.es
-
Tore Halvorsen