Data structure that keeps elements in chronological order, allows erases in O(log(n)) or less, and allows insertions.

Блог пользователя Qualified

Автор Qualified, история, 4 года назад, По-английски

I want a data structure that keeps elements in the way that you inserted them and allows erases in $$$O(log(n))$$$ or less. For example, if the initial array is empty and you insert 5, 2, 4, then the array would be [5, 2, 4]. Erase 4 and it is [5, 2]. Insert a 3 and it is [5, 2, 3]. I know that set allows erases in $$$O(log(n))$$$ and insertions but it keeps the elements in sorted order, not in the way that I inserted them.

Qualified
4 года назад
4

Комментарии (4)

Написать комментарий?

Qualified

4 года назад, # |

Auto comment: topic has been updated by Qualified (previous revision, new revision, compare).

→ Ответить

navneet.h

4 года назад, # |

+16

Self understandable code

struct DS
{
	set<pair<int,int>> st;
	map<int,int> idx;
	int time = 0;
	void insert(int x){
		st.insert({idx[x] = time++, x});
	}
	void erase(int x){
		auto itr = st.find({idx[x],x});
		if(itr == st.end()) {cout << "Element does not exist\n";}
		else st.erase(itr);
	}
	void printDS(){
		for(auto pr: st){
			cout << pr.second << " ";
		}
		cout << "\n";
	}
};

→ Ответить

_dp95

4 года назад, # ^ |

+13

You can get rid of the log factor to achieve O(1) for Insert and Delete operations by using std::list and std::unordered_map.

Code

struct DS{
    list<int> lst ;
    unordered_map< int, list<int>::iterator > has ;
    void insert( int x ){
        lst.push_back( x ) ;
        has[x] = --lst.end() ;
    }
    void erase( int x ){
        if(has.find(x)==has.end()){
            cout << "Element not found" << '\n' ;
            return ;
        }
        lst.erase(has[x]);
        has.erase(x) ;
    }
    void print(){
        for(auto itr:lst)
            cout << itr << " " ;
        cout << '\n' ;
    }
};

→ Ответить