Re: [問題] 一種資料結構

看板C_and_CPP (C/C++)作者softwind (software everywhere)時間16年前 (2009/08/03 23:52)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《softwind (software everywhere)》之銘言： : 就像之前有人問的 : 要模仿資料庫的運作 : 可以執行 select * from table natural join another_table : 我大概想了一下設計發現有一個問題 : 表格中的欄位設計最簡單的就是 1 對 1 自問自答我大概用兩組 set 組合出差不多的效果不過幾乎都是手工敲code... #include <set> #include <utility> using namespace std; typedef pair<int,int> Row; //一份資料 struct cmp_ColA{ // 針對 column A bool operator()(const Row *nl, const Row *nr) const { return nl->first - nr->first < 0; } }; struct cmp_ColB{ // 針對 column B bool operator()(const Row *nl, const Row *nr) const { return nl->second - nr->second < 0; } }; class key2Key{ typedef set<Row*, cmp_ColA>::iterator iA; typedef set<Row*, cmp_ColB>::iterator iB; private: set< Row*, cmp_ColA> pair_1; set< Row*, cmp_ColB> pair_2; public: key2Key(){} void addPair(const int &A, const int &B); }; //sample int main(){ key2Key key2; key2.addPair(1,5); key2.addPair(4,2); key2.addPair(3,3); key2.addPair(2,4); key2.addPair(5,1); key2.addPair(1,5); // 重複不做事 key2.addPair(1,6); // 更新 (1,5)->(1,6), resort pair_2 key2.addPair(3,4); // 先看4:del (2,4), 再看3:(3,3)->(3,4), resort at pair_2 } // 運作方式 add | table (1,5) |1| (1,5) |2| (1,5) (4,2) |1| (1,5)(4,2) |2| (4,2)(1,5) (3,3) |1| (1,5)(3,3)(4,2) |2| (4,2)(3,3)(1,5) (2,4) |1| (1,5)(2,4)(3,3)(4,2) |2| (4,2)(3,3)(2,4)(1,5) (5,1) |1| (1,5)(2,4)(3,3)(4,2)(5,1) |2| (5,1)(4,2)(3,3)(2,4)(1,5) (1,5) |1| (1,5)(2,4)(3,3)(4,2)(5,1) |2| (5,1)(4,2)(3,3)(2,4)(1,5) ---------------------------------------------- (1,6) |1| (1,6)(2,4)(3,3)(4,2)(5,1) |2| (5,1)(4,2)(3,3)(2,4) ;del entry at pair_2 ---------------------------------------------- |1| (1,6)(2,4)(3,3)(4,2)(5,1) |2| (5,1)(4,2)(3,3)(2,4)(1,6) ;add (1,6), force resort ---------------------------------------------- (3,4) |1| (1,6)(3,3)(4,2)(5,1) ;del entry (2,4) |2| (5,1)(4,2)(3,3)(1,6) ;del entry (2,4) ---------------------------------------------- |1| (1,6)(3,3)(4,2)(5,1) |2| (5,1)(4,2)(1,6) ;del entry (3,3) ---------------------------------------------- |1| (1,6)(3,4)(4,2)(5,1) ;change (3,3)->(3,4) |2| (5,1)(4,2)(1,6) ---------------------------------------------- |1| (1,6)(3,4)(4,2)(5,1) |2| (5,1)(4,2)(3,4)(1,6) ;add (3,4) ---------------------------------------------- // ================================================================= // codes 應該是這樣吧 // ================================================================= void addPair(const int &A, const int &B){ Row _row = make_pair<int ,int >(A,B); iA ia = pair_1.find( &_row ); iB ib = pair_2.find( &_row ); if( ia != pair_1.end() ){ if( ib == pair_2.end() ){ // B not found!, just modified it pair_2.erase( &Row(0, (*ia)->second) ); (*ia)->second=B; pair_2.insert( (*ia) ); // resort return; } else{ // B found at pair_2 if( B != (*ia)->second ){ // kill B's // 1. remove pair_1 entry // 2. delete the data pointer // 3. remove pair_2 entry pair_1.erase( &Row((*ib)->first,0) ); //remove entry at pair_1 delete (*ib); pair_2.erase(ib); ///////////////////////////////////////////////// pair_2.erase( &Row(0, (*ia)->second ) ); (*ia)->second = B; pair_2.insert( (*ia) ); // resort return; } else{ // hit! the same one. return; } } } if( ib != pair_2.end() ){ if( ia == pair_1.end() ){ pair_1.erase( &Row((*ib)->first, 0) ); (*ib)->first = A; pair_1.insert(*ib); //resort entry at pair_1 return; } else{ // error! cout<<"error"<<endl; system("pause"); } } //a new one! Row *p_row = new Row; p_row->first = A, p_row->second = B; pair_1.insert(p_row); pair_2.insert(p_row); } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.120.253