0

I am doing a problem and i need to do this task.

I want to add pairs (p1,q1),(p2,q2)..(pn,qn) in such way that

(i) Duplicate pair added only once(like in set).
(ii) I store count how many time each pair are added to set.For ex : (7,2) pair will present in set only once but if i add 3 times count will 3.

Which container is efficient for this problem in c++?

Little example will be great!

Please ask if you cant understand my problem and sorry for bad English.

Poojan Patel
  • 5
  • 4
  • You should take a look to vector. [Check this link](http://stackoverflow.com/questions/1041620/whats-the-most-efficient-way-to-erase-duplicates-and-sort-a-vector) – Matriac Apr 12 '16 at 02:54
  • Use a hashmap with key as a tuple and value as number of times you add it. – lobo Apr 12 '16 at 02:55
  • 2
    You may want to have a look at [`std::map`](http://en.cppreference.com/w/cpp/container/map) or [`std::unordered_map`](http://en.cppreference.com/w/cpp/container/unordered_map). – Lingxi Apr 12 '16 at 02:55
  • vector will allow duplicate and i want no duplication. – Poojan Patel Apr 12 '16 at 02:55
  • @Matriac But it will not inefficient and i also have too keep track of each pair count.. – Poojan Patel Apr 12 '16 at 03:04
  • `using Key = std::pair; using Container = std::map;` would be my first inclination. You add a pair to such a container with `Container c; c[Key{7, 2}]++;` (the value associated with the key is the count). `unordered_map` should work, too, I think. – Igor Tandetnik Apr 12 '16 at 03:12
  • Thanks i try to implement that way! @IgorTandetnik – Poojan Patel Apr 12 '16 at 03:14

1 Answers1

4

How about a std::map<Key, Value> to map your pairs (Key) to their count and as you insert, increment a counter (Value).

using pairs_to_count = std::map<std::pair<T1, T2>, size_t>;

std::pair<T1, T2> p1 = // some value;
std::pair<T1, T2> p2 = // some other value;

pairs_to_count[p1]++;
pairs_to_count[p1]++;

pairs_to_count[p2]++;
pairs_to_count[p2]++;
pairs_to_count[p2]++;

In this code, the operator[] will automatically add a key in the map if it does not exist yet. At that moment, it will initialize the key's corresponding value to zero. But as you insert, even the first time, that value is incremented.

Already after the first insertion, the count of 1 correctly reflects the number of insertion. That value gets incremented as you insert more.

Later, retrieving the count is a matter of calling operator[] again to get value associated with a given key.

size_t const p2_count = pairs_to_count[p2]; // equals 3
screwnut
  • 1,367
  • 7
  • 26