Untitled

#include <iostream>
#include <set>
using namespace std;

/*

add/remove/contains O(log n)
iterator O(1)
iterator::for O(m)
m為snapahot時元素個數


call 了 interator() 后，只能iterator element by that time， 新的添加的remove 不会影响interator result!!!!!!!!!!!!

*/

template <typename T>
class SnapshotSet {
public:
    void add(T e);
    void remove(T e);
    bool contains(T e);

    set<T> myiterator(); // not efficient

private:
	set<T> myset;
};

template <typename T>
void SnapshotSet<T>::add(T e){
	myset.insert(e);
}

template <typename T>
void SnapshotSet<T>::remove(T e){
	myset.erase(e);
}

template <typename T>
bool SnapshotSet<T>::contains(T e){
	return myset.find(e) != myset.end();
}

template <typename T>
set<T> SnapshotSet<T>::myiterator(){
	set<T> copy = myset;
	return copy;
}


int main() {
    SnapshotSet<int> intSet;

    intSet.add(5);
    intSet.add(2);
    intSet.add(8);
    intSet.remove(5);

    auto it = intSet.myiterator();

    intSet.add(1);
    cout << intSet.contains(2) << endl; // true
    intSet.remove(2);
    cout << intSet.contains(2) << endl; // false

    // traverse iterator
    for(auto a : it){
    	cout << a << " ";
    }

    return 0;
}










/*
template <typename T>
class SnapshotSet {
public:
    void add(T e);
    void remove(T e);
    bool contains(T e);

    // iterator* iterator();

    typename set<T>::iterator begin() {
    	return myset.begin();
    }

    typename set<T>::iterator end() {
    	return myset.end();
    }

private:
	set<T> myset;
};

template <typename T>
void SnapshotSet<T>::add(T e){
	myset.insert(e);
}

template <typename T>
void SnapshotSet<T>::remove(T e){
	myset.erase(e);
}

template <typename T>
bool SnapshotSet<T>::contains(T e){
	return myset.find(e) != myset.end();
}


int main() {
    SnapshotSet<int> intSet;

    intSet.add(5);
    intSet.add(2);
    intSet.add(8);
    intSet.remove(5);

    auto it1 = iterator();

    intSet.add(1);
    cout << intSet.contains(2) << endl; // true
    intSet.remove(2);
    cout << intSet.contains(2) << endl; // false

    // traverse iterator

    for(auto it1 = intSet.begin(); it != intSet.end(); ++it){
    	cout << *it << " ";
    }

    return 0;
}

*/