Qualified's blog

Data structure that keeps elements in chronological order and doesn't contain duplicates
By Qualified, history, 4 years ago, In English

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.

  • Vote: I like it
  • +19
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not use a HashSet? Is it faster?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

And again sorry for my bad English!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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);
    }
}
→ Reply