如何處理十萬級別的數據信息？

Node (int key, int size, Node *left, Node *right) :
key(key), size(size), left(left), right(right) {}

Node *update() {
size = left-&>size + 1 + right-&>size;
return this;
}

#include "ElementNotExist.h"
#include &

using namespace std;

/**
* TreeMap is the balanced-tree implementation of map. The iterators must
* iterate through the map in the natural order (operator&<) of the key. */ template&
class TreeMap
{
private:
static int ran()
{
static int x = 1;
x += (x &<&< 1) + 1; return x 2147483647; } struct Node; typedef pair & Pair;

Node *null;

struct Node
{
K key;
V val;
int size;
Node *left, *right;

Node () {}

Node (int size, Node *left, Node *right) :
size(size), left(left), right(right) {}

Node (K key, V val, int size, Node *left, Node *right) :
key(key), val(val), size(size), left(left), right(right) {}

Node *Update()
{
size = left-&>size + 1 + right-&>size;
return this;
}

const V find2(K x) const
{
if (!(x &< key) !(key &< x)) return val; if (key &< x) return right-&>find2(x);
else
return left-&>find2(x);
}

bool find(K x, Node *null) const
{
if (this == null)
return false;
if (!(x &< key) !(key &< x)) return true; if (key &< x) return right-&>find(x, null);
else
return left-&>find(x, null);
}

bool findV(V x, Node *null) const
{
if (this == null)
return false;
if (!(x &< val) !(val &< x)) return true; return left-&>findV(x, null) || right-&>findV(x, null);
}

void getNext(K x, K ans_key, V ans_val, Node *null)
{
if (this == null)
return;
if (x &< key) { ans_key = key; ans_val = val; left-&>getNext(x, ans_key, ans_val, null);
}

else
right-&>getNext(x, ans_key, ans_val, null);
}

Pair Split(K x, Node *null)
{
if (this == null)
return make_pair(null, null);
if (x &< key) { Pair ret = left-&>Split(x, null);
left = ret.second;
return make_pair(ret.first, this-&>Update());
}

Pair ret = right-&>Split(x, null);
right = ret.first;
return make_pair(this-&>Update(), ret.second);
}

Pair SplitLess(K x, Node *null)
{
if (this == null)
return make_pair(null, null);
if (!(key &< x)) { Pair ret = left-&>SplitLess(x, null);
left = ret.second;
return make_pair(ret.first, this-&>Update());
}

Pair ret = right-&>SplitLess(x, null);
right = ret.first;
return make_pair(this-&>Update(), ret.second);
}
};

void treapClear(Node *now)
{
if (now == null)
return;
treapClear(now-&>left);
treapClear(now-&>right);
delete now;
}

Node *Merge(Node *a, Node *b)
{
if (a == null)
return b;
if (b == null)
return a;
if (ran() % (a-&>size + b-&>size) &< a-&>size)
{
a-&>right = Merge(a-&>right, b);
return a-&>Update();
}

b-&>left = Merge(a, b-&>left);
return b-&>Update();
}

int _size;

public:

Node *_root;

class Entry
{
K key;
V value;
public:

Entry () {}

Entry(K k, V v)
{
key = k;
value = v;
}

const K getKey() const
{
return key;
}

const V getValue() const
{
return value;
}
};

class Iterator
{
private:
int _now;
K _key;
Entry ret;
const TreeMap & _temp;

public:

Iterator (int _now, const TreeMap & temp, K _key) :
_now(_now), _temp(temp), _key(_key) {}
/**
* Returns true if the iteration has more elements.
*/
bool hasNext() {
return _now &< _temp.size(); } /** * Returns the next element in the iteration. * @throw ElementNotExist exception when hasNext() == false */ const Entry next() { if (!hasNext()) throw ElementNotExist(); if (_now == 0) { Node *now = _temp._root; while (now-&>left != _temp.null)
now = now-&>left;
ret = Entry(now-&>key, now-&>val);
_now++;
_key = ret.getKey();
return ret;
}

else
{
K ans_key;
V ans_val;
int tag = 0;
Node *nnow = _temp.null;
_temp._root-&>getNext(_key, ans_key, ans_val, nnow);
_now++;
ret = Entry(ans_key, ans_val);
_key = ans_key;
return ret;
}
}
};

/**
* Constructs an empty tree map.
*/
TreeMap() {
null = new Node(0, null, null);
_size = 0;
_root = null;
}

/**
* Destructor
*/
~TreeMap() {
treapClear(_root);
delete null;
}

/**
* Assignment operator
*/
TreeMap operator=(const TreeMap x) {
if (this == x)
return *this;
treapClear(_root);
_root = null;
_size = 0;
Iterator it = x.iterator();
while (it.hasNext())
{
Entry now = it.next();
put(now.getKey(), now.getValue());
}

return *this;
}

/**
* Copy-constructor
*/
TreeMap(const TreeMap x) {
null = new Node(0, null, null);
_size = 0;
_root = null;
Iterator it = x.iterator();
while (it.hasNext())
{
Entry now = it.next();
put(now.getKey(), now.getValue());
}
}

/**
* Returns an iterator over the elements in this map.
*/
Iterator iterator() const {
K know;
return Iterator(0, *this, know);
}

/**
* Removes all of the mappings from this map.
*/
void clear() {
treapClear(_root);
_root = null;
_size = 0;
}

/**
* Returns true if this map contains a mapping for the specified key.
*/
bool containsKey(const K key) const {
Node *nnow = null;
return _root-&>find(key, nnow);
}

/**
* Returns true if this map maps one or more keys to the specified value.
*/
bool containsValue(const V value) const {
Node *nnow = null;
return _root-&>findV(value, nnow);
}

/**
* Returns a const reference to the value to which the specified key is mapped.
* If the key is not present in this map, this function should throw ElementNotExist exception.
* @throw ElementNotExist
*/
const V get(const K key) const {
Node *nnow = null;
if (!_root-&>find(key, nnow))
throw ElementNotExist();
return _root-&>find2(key);
}

/**
* Returns true if this map contains no key-value mappings.
*/
bool isEmpty() const {
return _size == 0;
}

/**
* Associates the specified value with the specified key in this map.
*/
void put(const K key, const V value) {
Pair ret1 = _root-&>SplitLess(key, null), ret2 = ret1.second-&>Split(key, null);
if (ret2.first-&>size == 0)
{
_size++;
_root = Merge(ret1.first, Merge(new Node(key, value, 1, null, null), ret2.second));
return;
}

ret2.first-&>val = value;
_root = Merge(ret1.first, Merge(ret2.first, ret2.second));
}

/**
* Removes the mapping for the specified key from this map if present.
* If there is no mapping for the specified key, throws ElementNotExist exception.
* @throw ElementNotExist
*/
void remove(const K key) {
Pair ret1 = _root-&>SplitLess(key, null), ret2 = ret1.second-&>Split(key, null);
if (ret2.first-&>size == 0)
{
_root = Merge(ret1.first, ret2.second);
throw ElementNotExist();
}

_size--;
_root = Merge(ret1.first, ret2.second);
delete ret2.first;
}

/**
* Returns the number of key-value mappings in this map.
*/
int size() const {
return _size;
}
};