Union of sets

[dontknow]

Hello, I have a problem and I don´t know, how to solve it.
I have two .txt files, there is 1,000,000 numbers in each file, one number on each row. Lists are not sorted ascending or descending. I need to unite these two sets into a new file, delete duplicated numbers and sort ascending. I´m beginner in C++, so I have absolutely no idea, how to solve it. Thanks for any idea.

[Banfa]

1,000,000 numbers if they were ints would take about 4mbyte of RAM. On to-days systems with gigabytes of ram it is probably acceptable to allocate that much memory so for each of the 2 files

• Load the file into memory
• Sort the data in memory
• Remove duplicates, if this didn't happen at stage 2

you can use a std::vector or std::list to hold the data from the file, this will making sorting easy since sorting algorithms are provided for standard containers.

Once you have the data from the 2 files in memory in 2 separate containers sorted and with duplicates removed it is fairly simple to then merge these 2 datasets into a single dataset.

Then finally you can write the resulting dataset out to a result file.

[donbock]

It would complicate the logic of the merge, but the program might run faster if you didn't worry about removing duplicates until the merge step. That would eliminate the cost of deleting duplicates from the two big arrays.

Hmmm. On the other hand, consider reading the input files directly into a binary tree that you sort as you go, but don't insert duplicate values. Then all you have to do is create the output file by traversing the tree.

The binary tree technique triples the memory usage; and you're totally screwed if you run out of memory before acquiring all the input data.

[Banfa]

Actually C++ provides an easy method to implement Dons suggestion. The std::set. This is often implemented as a binary search tree, it is stored using a strict weak ordering and it can not contain duplicates.

Just read the 2 files adding all entries to a single std::set, the insert operation will fail in a gracefully for any values already in the std::set and you can just extract the data in the set to get the ordered list once both files have been read.

[donbock]

Darn! Why is it that all my most insightful design solutions seem to be built in to C++ where they're available to everybody?

[Banfa]

lol because those pesky C++ designers looked round at all the things that C programmers found useful and then included them in their standard library so that everyone would have easy access to them.