0

我正在尝试为自定义有序地图类实现天花板/地板/较低/较高条目功能。目前我有两个语法错误：

  1. “>> 应该是 >> 在嵌套模板中”，我已经以这种方式对其进行了修改，但仍然出现此错误。
  2. “BSTIterator 没有命名类型”。

您能否告诉我如何做 ceilingEntry （它应该返回一个迭代器到具有大于或等于k​​的最小键值的条目，或者如果没有这样的条目或 map 为空，则返回 end() ）？我试图将代码减少到最低限度，我希望它是可以理解的。

BT.h

#include<iostream>
#include<list>
#include<stdio.h>

template <typename E>
class LinkedBinaryTree {

public:
struct Node{
    E elt;
    Node* par;
    Node* left;
    Node* right;
    Node() : elt(), par(NULL), right(NULL), left(NULL){}
};

public:
class Position{
    public:
        Node* v;
    public:
        Position(Node* _v = NULL):v(_v){}
        E& operator*()
            {return v->elt;}
        Position left() const
            {return Position(v->left);}
        Position right() const
            {return Position(v->right);}
        Position parent() const
            {return Position(v->par);}
        bool isRoot() const
            {return v->par == NULL;}
        bool isExternal() const
            {return v->left == NULL && v->right == NULL;}
        bool isInternal() const
            {return !isExternal();}
        const E& operator*() const {return v->elt;}
        bool operator==(const Position& ppos) const { return this->v == 
ppos.v ;}

        friend class LinkedBinaryTree;


};
typedef std::list<Position> PositionList;

public:
LinkedBinaryTree();
int getSize() const;
bool isEmpty() const;
Position root() const;
PositionList positions() const;
void addRoot();
void expandExternal(const Position& p);
Position removeAboveExternal(const Position& p);

protected:
void preorder(Node* v, PositionList& pl) const;
private:
Node* _root;
int n;
};

template <typename E>
LinkedBinaryTree<E>::LinkedBinaryTree()
:_root(NULL), n(0) {}

template <typename E>
int LinkedBinaryTree<E>::getSize() const
{return n;}

template <typename E>
bool LinkedBinaryTree<E>::isEmpty() const
{return getSize() == 0;}

template <typename E>
typename LinkedBinaryTree<E>::Position LinkedBinaryTree<E>::root() const
{return Position(_root);}

template <typename E>
void LinkedBinaryTree<E>::addRoot()
{_root = new Node; n = 1;}

template <typename E>
void LinkedBinaryTree<E>::expandExternal(const Position& p){
Node* v = p.v;
v->left = new Node;
v->left->par = v;
v->right = new Node;
v->right->par = v;
n += 2;
}

template <typename E>
typename LinkedBinaryTree<E>::Position 
LinkedBinaryTree<E>::removeAboveExternal(const Position& p){
Node* w = p.v; Node* v = w->par;
Node* sib = (w==v->left ? v->right:v->left);
if(v == _root){
    _root = sib;
    sib->par = NULL;
}
else{
    Node* gpar = v->par;
    if(v == gpar->left) gpar->left = sib;
    else gpar->right = sib;
    sib->par = gpar;
}
delete w; delete v;
n -= 2;
return Position(sib);
};

template <typename E>
typename LinkedBinaryTree<E>::PositionList LinkedBinaryTree<E>::positions() 
const{
PositionList pl;
preorder(_root, pl);
return PositionList(pl);
}

template <typename E>
void LinkedBinaryTree<E>::preorder(Node* v, PositionList& pl) const{
pl.push_back(Position(v));
if(v->left != NULL)
    preorder(v->left, pl);
if(v->right != NULL)
    preorder(v->right, pl);
}

BST.h

template<typename K, typename V>
class Entry{
public:
typedef K Key;
typedef V Value;

public:
Entry(const K& k = K(), const V& v = V())
 :_key(k), _value(v) {}
 const K& key() const {return _key;}
 const V& value() const {return _value;}
 void setKey(const K& k) {_key = k;}
 void setValue(const V& v){_value = v;}
private:
K _key;
V _value;
};

//Search Tree
template <typename E>
class SearchTree{

public:
typedef typename E::Key K;
typedef typename E::Value V;
typedef  LinkedBinaryTree<E> BinaryTree;
typedef typename LinkedBinaryTree<E>::Position TPos;

public:
class Iterator{
public:
    TPos v;
public:
    Iterator(const TPos& vv) : v(vv) {}
    const E& operator*() const {return *v;}
    E& operator*() {return *v;}
    bool operator==(const Iterator& p) const {return v == p.v;}
    Iterator& operator++();
    friend class SearchTree;
};

public:
SearchTree();
int getSize() const ;
bool isEmpty() const ;
Iterator find(const K& k);
Iterator insert(const K& k, const V& x);
void erase(const K& k);
void erase(const Iterator& p);
Iterator begin();
Iterator end();
TPos root() const;
TPos finder(const K& k, const TPos& v);
TPos inserter(const K& k, const V& x);
TPos eraser(TPos& v);
TPos restructure(const TPos& v);

private:
BinaryTree T;
int n;
};

template <typename E>
int SearchTree<E>::getSize() const {return n ;}

template <typename E>
bool SearchTree<E>::isEmpty() const {return n==0; }


template <typename E>
typename SearchTree<E>::Iterator& SearchTree<E>::Iterator::operator++(){
TPos w = v.right();
if(w.isInternal()){
    do{v=w; w = w.left();}
    while(w.isInternal());
}
else{
    w = v.parent();
    while(v == w.right())
    {v = w; w = w.parent();}
    v = w;
}
return *this;
}

template <typename E>
SearchTree<E>::SearchTree(): T(), n(0)
{T.addRoot(); T.expandExternal(T.root());}

template <typename E>
typename SearchTree<E>::TPos SearchTree<E>::root() const
{return T.root().left();}

template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::begin(){
TPos v = root();
while (v.isInternal()) v = v.left();
return Iterator(v.parent());
}

template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::end()
{return Iterator(T.root());}

template <typename E>
typename SearchTree<E>::TPos SearchTree<E>::finder(const K& k,  const TPos& 
v){
if(v.isExternal()) return v;
if(k < (*v).key()) return finder(k,v.left());
else if((*v).key() < k) return finder(k,v.right());
else return v;
}

template <typename E>
typename SearchTree<E>::Iterator SearchTree<E>::find(const K& k){
TPos v = finder(k, root());
if(v.isInternal()) return Iterator(v);
else return end();
}

有序映射.h

#include "BST.h"

template <typename KK, typename VV>
class OrderedMap: public SearchTree<Entry<KK,VV> > {
public:
typedef  SearchTree<Entry<KK,VV> > BST;
typedef typename SearchTree<Entry<KK,VV> >::Iterator BSTIterator;
typedef typename SearchTree<Entry<KK,VV> >::TPos TPos;

public:
OrderedMap(): SearchTree<Entry<KK,VV> >(){}
bool empty () const ;
BSTIterator find ( const KK& k) const {find(k);}
BSTIterator end () {return BST::end();}
BSTIterator ceilingEntry(const KK& k);
BSTIterator ceilingEntry(const KK& k, TPos & w);
//...
};

template <typename KK, typename VV>
BSTIterator OrderedMap<KK,VV>::ceilingEntry(const KK& k) {
if (OrderedMap<KK,VV>::empty()) { return OrderedMap<KK,VV>::end(); }
return ceilingEntry(k, BST.root());
}

template <typename KK, typename VV>
BSTIterator OrderedMap<KK,VV>::ceilingEntry(const KK& k, TPos & w) {
// what to write here?
}

编辑：我扩展了代码，以便可以轻松编译它。我试图最小化，但它仍然很大，因为有很多依赖项。大部分空间都被模板占用了，我希望这很好。

4

0 回答 0