4
\$\begingroup\$

My special case: home project, automatic downloader for podcasts.

Overall algorithm is:

  1. Download a list of available podcasts
  2. hash the podcasts
  3. load metadata + hash of downloaded podcasts from sqlite db
  4. Algorithm this questions is about - throw out all already downloaded.
  5. Download new podcasts
  6. save metadata to sqlite db

Algorithm discussion

I'm hoping for comments on using std::rotate, performance, and the implementation.

For downloaded data, I currently use a vector. For data from DB, I also use a vector.

I merge both together and sort them according to the hashes (obviously).

And algorithm doubleEraser on the merged vector.

#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
#include <string>

template <typename ForwardItr>
ForwardItr doubleEraser(ForwardItr first, ForwardItr last)
{
 auto itr = first;
 typename std::iterator_traits<ForwardItr>::value_type firstMatch = *first;
 bool hasFirstMatch(false);

 while(itr != last)
 {
  auto next = std::next(itr);
  if(next != last && *itr == *next)
  {
    if(!hasFirstMatch)
    {
     hasFirstMatch = true;
     firstMatch = *itr;
    }
    else
    {
     if(*itr == firstMatch) // again at first match
     {
       return itr; 
     }
    }


    std::rotate(itr, std::next(itr, 2), last); // throw matched elements to the end of container
   }
   else
    ++itr;
  }
 return last;
}

template <typename T>
void print(T& c)
{
 for(auto & element : c)
  std::cout << element << " ";

 std::cout << "\n";
}

template <class T>
void process(std::vector<T>& t)
{
  std::string formating(" \t");
   std::cout << "input: " << formating;
 print(t);
 std::sort(t.begin(), t.end());
 std::cout << "sorted:" << formating;
 print(t);
 auto itr_begin = doubleEraser(t.begin(), t.end());
 std::cout << "dEraser:" << formating;
 print(t);
 t.erase(itr_begin, t.end());
 std::cout << "output:" << formating;
 print(t);
}

int main()
{
 std::vector<int> vec {1,2,3,4,5,6,7,8,9,3,5,6,7,2};
 std::vector<char> vec2 {'A', 'C', 'D', 'D', 'G', 'A' };
 std::vector<std::string> vec3 {"Hello", "World", "that", "be", "that", "Hello"};

 process(vec);
 process(vec2);
 process(vec3);
}
\$\endgroup\$
  • \$\begingroup\$ Are you actually starting with two sets or one? Your text description sounds like you have two, but your code has only one set. \$\endgroup\$ – T.C. Feb 13 '15 at 9:14
  • \$\begingroup\$ i expanded the discription: For downloaded data i currently us a vector. For data from DB i use a vector, too. I merge both together, i sort it according to the hashes (obviously). And algorithm doubleEraser on the merged vector. \$\endgroup\$ – eul3r Feb 13 '15 at 9:21
  • \$\begingroup\$ Don't merge them; sort them separately and then use std::set_difference. \$\endgroup\$ – T.C. Feb 13 '15 at 9:22
1
\$\begingroup\$

Comment by @T.C.:

Don't merge them; sort them separately and then use std::set_difference:

#include <algorithm>
#include <vector>
#include <iostream>
template <typename T>
void print(T& c)
{
 for(auto & element : c)
  std::cout << element << " ";

 std::cout << "\n";
}

int main()
{
 std::vector<int> vec {1,2,3,4,6,7,8};
 std::vector<int> vec4 {3,4,5,6};
 std::sort(vec.begin(), vec.end());
 std::sort(vec4.begin(), vec4.end());
std::set_difference(vec.begin(), vec.end(), vec4.begin(), vec4.end(), std::inserter(vec5, vec5.begin()));
 print(vec5);
}
  • Input: {1,2,3,4,6,7,8} and {3,4,5,6}
  • Output wanted: 1,2,5,7,8
  • Output real: 1,2,7,8

You cannot use std::set_difference because of the hashes used as comparison criteria. The Hash Distribution of new hashes is not sortable in a way that new items will be the last ones, which is a requirement for std::set_difference.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not sure I understand; you have a set of "available" ({1,2,3,4,6,7,8}) and a set of "downloaded" ({3,4,5,6}), right? And you want the set of "available but not downloaded", which is, correctly, {1,2,7,8}. {1,2,5,7,8} would be both "available but not downloaded" and "downloaded but not available". If you really want that, there's std::set_symmetric_difference. \$\endgroup\$ – T.C. Feb 13 '15 at 10:28
1
\$\begingroup\$
  1. If std::set_difference or std::set_symmetric_difference work for you, then just use those.

  2. Else if you have to merge the vectors for some reason, I would recommend replacing doubleEraser() with something like this:

    template <typename ForwardItr>
    ForwardItr remove_adjacent (ForwardItr first, ForwardItr last)
    {
        while ((first = std::adjacent_find (first, last)) != last) {
            auto value = *first ;
            last = std::remove (first, last, value) ;
        }
    
        return last ;
    }
    

    You already sort t before you call doubleEraser(), so this should always work. It also handles the case when you have more than just two duplicates.

  3. If the above for some reason does not fit your requirements, then below is a small review of your doubleEraser() function.

    typename std::iterator_traits<ForwardItr>::value_type firstMatch = *first;
    

    Could just be:

    auto firstMatch = *first;
    

    The performance of std::rotate() should be fine.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer. I'll use std::set_ algorithms. Ad 2.) Check your algorithm Given Input: 1 2 3 3 4 4 5 5 6 6 7 8 --sort--- remove_adjacent output: 1 2 4 6 7 8 <--- 4, 6 are illegal numbers. It jumps after it found one dup pair. \$\endgroup\$ – eul3r Feb 15 '15 at 21:18
  • 1
    \$\begingroup\$ Needs to make a copy of *first for remove() - auto val = *first; last = std::remove (first, last, val);. Otherwise weird things happens since remove takes the value by const reference, which changes during the process of removal. \$\endgroup\$ – T.C. Feb 16 '15 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.