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

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

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

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
6 лет назад
10

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

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

AnandOza

6 лет назад, скрыть # |

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

6 лет назад, скрыть # ^ |

Why not use a HashSet? Is it faster?

→ Ответить

MasterMind

6 лет назад, скрыть # ^ |

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

→ Ответить

skittles1412

6 лет назад, скрыть # ^ |

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

6 лет назад, скрыть # ^ |

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

6 лет назад, скрыть # |

← 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

6 лет назад, скрыть # ^ |

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

→ Ответить

lov.ish

6 лет назад, скрыть # ^ |

← 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

6 лет назад, скрыть # |

+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);
    }
}

→ Ответить