How to remove duplicate values while they are being read?

Question

MRE (because license issues):

std::set<std::string> pool;

// values: 10 10 1 3 4 3 3 2 5 7 5 4 3 9 8 8 7
// (values is an iterable collection)
for (const auto& value : values) {
    pool.insert(value);
}

// expected read: 10 1 3 4 2 5 7 9 8

// actual read: 1 10 2 3 4 5 7 8 9 (10 after 1 because std::string)

what collection do I use to achieve this?

cannot store the values and then call std::unique because the file being read already crosses over 30GB — justanotherguy, Jun 20 '23 at 10:58
@463035818_is_not_an_ai I am using it to leverage its property of removing duplicates on the fly. Is there any other container which will allow me to do this and preserve the order? — justanotherguy, Jun 20 '23 at 11:00
Use 2 containers. Read into the set, using the return value of `insert` to work out if this item was new. Then add only new items to a vector. That vector will be the unique items in insertion order. — Mike Vine, Jun 20 '23 at 11:00
@MikeVine, that seems like a perfectly good idea, but it still looks pretty RAM intensive. Even now, the RAM usage is surpassing 90%. — justanotherguy, Jun 20 '23 at 11:02
You can always write them to a file rather than a vector. Then release your `std::set` and load the file into a vector. — Galik, Jun 20 '23 at 11:13
What are the bounds of the input values? Do you expect them to small or arbitrary 64-bit values? — bitmask, Jun 20 '23 at 11:27

score 6 · Accepted Answer · edited Jun 20 '23 at 11:23

6

Use 2 containers. Read into the set, using the return value of insert to work out if this item was new. Then add only new items to a vector. That vector will be the unique items in insertion order.

#include <vector>
#include <set>
#include <string>
#include <iostream>

int main()
{
    std::vector<std::set<std::string>::iterator> itemsInOrder;
    std::set<std::string> pool;

    std::vector<std::string> values = {"10", "10", "1", "3"};

    for (const auto& value : values)
    {
        auto ret = pool.insert(value);
        if (ret.second)
        {
            itemsInOrder.push_back(ret.first);
        }
    }

    for (auto item : itemsInOrder)
    {
        std::cout << *item << std::endl;
    }
}

edited Jun 20 '23 at 11:23

Jan Schultke

17,446
6
47
96

answered Jun 20 '23 at 11:04

Mike Vine

9,468
25
44

1

You could make this a bit prettier with structured bindings: `auto [it, success] = pool.insert(value)`. – Jan Schultke Jun 20 '23 at 11:23
I would use: `std::unordered_set`: https://godbolt.org/z/1nbPKdszG of course you have to remember about object lifetime (like in case where you used iterators). – Marek R Jun 20 '23 at 11:43

score 0 · Answer 2 · answered Jun 21 '23 at 12:07

"pool.insert" return a pair, pair.second is the bool type which was inserted a element or not

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int main(void) {
    set<int> pool;
    pair<set<int>::iterator, bool> k;
    vector<int> v={10, 10, 1, 3, 6, 3, 3, 2, 5, 7, 5, 6, 3, 9, 8, 8, 7};
    vector<int> result;
    // values: 10 10 1 3 6 3 3 2 5 7 5 6 3 9 8 8 7
    // (values is an iterable collection)
    for(int i = 0; i < v.size(); i++) {
        k = pool.insert(v[i]);
        if(k.second==true) {
            result.push_back(v[i]);
        }
    }
    // expected read: 10 1 3 6 2 5 7 9 8
    // actual read: 10 1 3 6 2 5 7 9 8
    int i = 0;
    return 0;
}

How to remove duplicate values while they are being read?

2 Answers2