作者softwind (software everywhere)
看板C_and_CPP
標題Re: [問題] 一種資料結構
時間Mon Aug 3 23:52:04 2009
※ 引述《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