Data structure that keeps elements in chronological order and doesn't contain duplicates

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

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

I know that set doesn't contain duplicates, but it sorts the elements. I want a data structure that doesn't sort the elements and doesn't contain duplicates.

For example if the data structure contains ints,

Input: 5 4 1 2 5 4 9

Elements in data structure

5 4 1 2 9

Please help.

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

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

Показать архивные | Написать комментарий?

AnandOza

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

in Java, you can use a LinkedHashSet

in any language, you can do it yourself using a list (or vector) and a set in combination

→ Ответить

skittles1412

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

Why not use a HashSet? Is it faster?

→ Ответить

MasterMind

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

When using the hashset the elements will be sorted and will lose order of element

→ Ответить

skittles1412

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

I think you're thinking of the TreeSet which maintains elements in order. The HashSet does not. I was just asking if there was any specific reason for a LinkedHashSet over the HashSet (e.g. faster time, less memory, etc)

→ Ответить

AnandOza

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

Qualified said they didn't want to sort the elements, and technically HashSet doesn't. But I assume they actually meant they want to maintain the original order, and HashSet doesn't do that either. LinkedHashSet is exactly the same as HashSet except it also stores the original insertion order for iteration.

→ Ответить

Sadik

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

← Rev. 2 →

-10

Sorry for mistake in the first time!

You can use map to check if the element in the array or not and a vector array to save the elements.

code

map<int,int>mp;
vector<int>v;
for(int i=0;i<n;i++)
{ 
   if(mp[arr[i]]==0)
   {  
      mp[arr[i]] =1;
      v.push_back(arr[i]);
   }
}
for(int i=0;i<v.size();i++) cout<<v[i]<<" ";

And again sorry for my bad English!

→ Ответить

Qualified

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

When I put in the elements in the unordered set it outputs 2 1 5 9 4 and not 5 4 1 2 9

→ Ответить

ma_da_fa_ka

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

← Rev. 3 →

Just do hashmap such that if for each x if mp.count(x) then skip else mp[x] = 1

P.S. I see no reason for downvotes in this blog just because of his rating

→ Ответить

Gassa

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

+10

As said above, you can actually use two data structures for the two properties you desire: one will maintain the order (vector with push_back), and the other will check for duplicates before inserting (set or unordered_set). Code for insertion will be something like this:

vector <int> order;
set <int> seen;

void insert (int element) {
    if (!seen.count (element)) {
        order.push_back (element);
        seen.insert (element);
    }
}

→ Ответить