如何在c ++中实现实例之间的通信？ [英] How should I implement communication between instances in c++?
问题描述
我有两个AVL树，每个按不同的参数排序相同的数据（例如，其中一个树实际上存储数据，另一个只是指向它）。在示例中，左侧的树按照左侧数字排序，右侧的树按照右侧数字排序：
58 64
/ \ / \
22 73 22 58
/ \ / \ / \ / \
19 36 64 81 81 73 36 19
说我要移除一个项目（两个树都是相同的资料），但我只给出了左边的数字。例如，在调用 removeLeft（6）后，我的树将如下所示：
58 36
/ \ / \
22 73 22 58
/ \ \ / \ \
19 36 81 81 73 19
我可以在 log（n）时间，如果我在节点我希望删除，我可以从每棵树中删除它 log（n）每棵树。 p>
但是，我需要一个从左侧树中的节点到右侧节点的链接：
58 ------> 64
/ \ | / \
22 73 | 22 58
/ \ /\ | / \ / \
19 36 64 81 | 81 73 36 19
| ______ |
否则，我需要在 n
我别无选择，只能实现我的数据结构作为 Tree 类的 friend 类？这甚至工作吗？
这里是我打算做什么，如果有人会碰到这个问题...
如果我有任何有说服力的意见，为什么这是一个坏主意，我会删除答案/编辑它。
基本上，我将创建一个 Forrest 类，它本质上是一个 List 与数据本身，以及专门的AVL树（ Sapling s）的内部列表，我会使 Forrest
<$ p> $ p>
_______________ ... _______
数据：| 19 | 22 | ... | 81 |
| PTR-> M7 | PTR-> M2 | ... | PTR-> M1 |
| PTR-> N1 | PTR-> N2 | ... | PTR-> N7 |
_____
树苗：| T1 | T2 |
T1：
N4：PTR-> 58
/ \
N2：PTR-> 22 N6：PTR-> 73
/ \ / \
N1：PTR-> 19 N3：PTR-> 36 N5：PTR-> 64 N7：PTR-> 81
T2：
M4：PTR-> 64
/ \
M2：PTR-> 22 M6：PTR-> 58
/ \ / \
M1： PTR-> 81 M3：PTR-> 73 M5：PTR-> 36 M7：PTR-> 19
此外，我将创建一个比较类，因此相同 Tree 类型的不同实例可以排序并允许 Forrest 定义对数据的指针进行排序的 Sapling 的方法。
基本AVL树：
//基本AVL类型，这个问题它会做
模板< typename T>
class AVL {
public：
//比较类型，所以不同的树可以排序不同
class Compare {
public：
virtual bool less（const& ; T，const& T）= 0;
virtual bool equals（const& T，const& T）= 0;
};
protected：
//默认比较类型，以利用类型T的默认比较运算符
class DefaultCompare：public AVL< T> ::比较{
public：
bool （const& T a，const& T b）{return a< b; }
bool equal（const& T a，const& T b）{return a == b; }
};
// AVL树节点。将在sapling中扩展
类Node {
public：
Node * _parent，* _left，* _right;
T _data
};
public：
AVL（const& AVL< T> :: Compare = DefaultCompare（））;
};
扩展它，用于 Forrest ：
template< typename T>
class Sapling：public AVL< T> {
public：
friend class Forrest;
};
这是 List use：
template< typename T>
class List {
protected：
//列表节点：prev，next和data
class Node {
public：
Node * _next， _prev;
T _data;
};
//列表本身
Node * _head;
public：
... // Setters，getter，iterator ...等等。
};
定义 Forrest strong>是列表）：
template< typename T>
class Forrest：public List< T> {
private：
//扩展列表节点以包括指向此数据的所有Sapling节点
class Node：public List< T> :: Node {
List< AVL :: Node *> _sapling_nodes;
};
// Saplings本身存储指向列表节点的指针，所以数据本身
//存储在主列表（_head字段，继承自List< T>）中
List< AVL ; Forrest :: Node *> > _saplings;
//创建一个Compare对象，这样可以在树中比较数据的指针：
class ComparePtrs：public AVL< Forrest :: Node *> :: Compare {
public：
bool less（const& Node * a，const& Node * b）{return a-> _data& b-> _data; }
bool equal（const& Node *，const& Node *）{return a-> _data == b-> _data; }
};
};
Whew ...
工作。
I have two AVL trees, each sort the same data by different parameters (say, one of the trees actually stores the data, the other just points to it). In the example, the tree on the left sorts by the left digit and the tree on the right sorts by the right digit:
58 64
/ \ / \
22 73 22 58
/ \ / \ / \ / \
19 36 64 81 81 73 36 19
Say I want to remove an item (from both trees, as it's the same data), but I'm only given the number on the left. For example, after removeLeft(6) is called, my trees would look like:
58 36
/ \ / \
22 73 22 58
/ \ \ / \ \
19 36 81 81 73 19
I can find the node in the left tree in log(n) time, and if I'm at the node I wish to remove, I can remove it from each tree in another log(n) per tree.
However, I need a link from a node in the left tree to a node on the right:
58 ------>64
/ \ | / \
22 73 | 22 58
/ \ / \ | / \ / \
19 36 64 81 | 81 73 36 19
|______|
Otherwise I'd need to find the node in the right tree in n time, because it isn't sorted by the left digit.
My Tree class doesn't allow direct access to nodes, only to data (and I'd like to keep it that way).
Do I have no choice but to implement my data structure as a friend class of the Tree class? Would that even work? Or is there some elegant way of doing something like this?
Here's what I plan on doing, if anybody should come across this question...
If I get any persuasive comments on why this is a bad idea, I'll remove the answer / edit it.
Basically, I'll create a Forrest class, which is in essence a List with the data itself, along with an inner list of specialized AVL trees (Saplings), and I'll make the Forrest a friend of said Saplings.
_______________ ... _______
Data: |19 |22 |...|81 |
|PTR->M7|PTR->M2|...|PTR->M1|
|PTR->N1|PTR->N2|...|PTR->N7|
_____
Saplings: |T1|T2|
T1:
N4:PTR->58
/ \
N2:PTR->22 N6:PTR->73
/ \ / \
N1:PTR->19 N3:PTR->36 N5:PTR->64 N7:PTR->81
T2:
M4:PTR->64
/ \
M2:PTR->22 M6:PTR->58
/ \ / \
M1:PTR->81 M3:PTR->73 M5:PTR->36 M7:PTR->19
Also, I'll create a Compare class so different instances of the same Tree type may sort differently, and allow the Forrest to define the Sapling's method of sorting pointers to the data.
Basic AVL tree:
// Base AVL type, incomplete but for the purpose of this question it'll do
template<typename T>
class AVL {
public:
// Compare type, so different trees can sort differently
class Compare {
public:
virtual bool less(const& T, const& T) = 0;
virtual bool equal(const& T, const& T) = 0;
};
protected:
// Default compare type, to utilize type T's default comparison operators
class DefaultCompare : public AVL<T>::Compare {
public:
bool less(const& T a, const& T b) { return a<b; }
bool equal(const& T a, const& T b) { return a==b; }
};
// AVL tree node. Will be extended in the Sapling
class Node {
public:
Node *_parent, *_left, *_right;
T _data;
};
public:
AVL(const& AVL<T>::Compare = DefaultCompare());
};
Extend it, for use with a Forrest:
template<typename T>
class Sapling: public AVL<T> {
public:
friend class Forrest;
};
This is the List class I'll use:
template<typename T>
class List {
protected:
// A list node: prev, next and data
class Node {
public:
Node *_next, *_prev;
T _data;
};
// The list itself
Node* _head;
public:
... // Setters, getters, iterator... etc.
};
Define the Forrest class (the Forrest is a list, in fact):
template<typename T>
class Forrest: public List<T> {
private:
// Extend the list node to include all the Sapling nodes pointing to this data
class Node: public List<T>::Node {
List<AVL::Node*> _sapling_nodes;
};
// The Saplings themselves store pointers to list nodes, so the data itself
// is stored in the main list (the _head field, inherited from List<T>)
List<AVL<Forrest::Node*> > _saplings;
// Create a Compare object so pointers to the data can be compared in the saplings:
class ComparePtrs: public AVL<Forrest::Node*>::Compare {
public:
bool less(const& Node* a, const& Node* b) { return a->_data < b->_data; }
bool equal(const& Node*, const& Node*) { return a->_data == b->_data; }
};
};
Whew...
Hope this works.
这篇关于如何在c ++中实现实例之间的通信？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
