CODEWITHSUNDEEP
c++algorithmstlfind
Mike Irish
Mike Irish

Reputation: 960

Using STL algorithm to find all matches in a set

I have a set containing Song objects. I want to search for all occurrences of a Songs that have a particular title. I am required to use a STL algorithm.

The problem is when it finds the first occurrence it stops searching.

I am trying to fix it by using a while loop and changing where to start the search from but I am having trouble getting it to work.

Original Function

set<Song> SongLibrary::SearchSong(string title)
{
    set<Song> foundSongs;

    find_if(begin(m_songs), end(m_songs),[&](Song const& p)

        {
            if (p.getTitle() == title)
            {
                foundSongs.insert(p);
            }
            return p.getTitle() == title; });

    return foundSongs;
}

This is my attempt at modifying it to use a while loop

while (startSearch != m_songs.end)
{
    find_if(startSearch, end(m_songs), [&](Song const& p) // wont take start search as a parameter
    {
        if (p.getTitle() == title)
        {
            startSearch == m_songs.Position(); // this Line is wrong
            foundSongs.insert(p);
        }
        return p.getTitle() == title; });
}

Attempt at using Copy_if

copy_if(m_songs.begin(), m_songs.end(), foundSongs, [&](Song const& s), s.getTitle() == title);

Upvotes: 0

Views: 569

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490098

For a case like this, you normally want to use std::copy_if:

set<Song> SongLibrary::SearchSong(string title)
{
    set<Song> foundSongs;

    std::copy_if(begin(m_songs), end(m_songs), 
        std::inserter(foundSongs, end(foundSongs)),
        [&](Song const &s) { return s.getTitle() == title; });

}

[Unrelated aside: I used the same signature as in the question, but it's at least worth considering passing the parameter by const reference rather than by value.]

If you were storing the songs in a sequence container (e.g., vector or deque), you could probably use std::partition instead:

auto pos = std::partition(begin(m_songs), end(m_songs), 
    [&](Song const &s) { return s.getTitle() == title; });

In this case, [m_songs.begin(), pos) are the range of songs that match the request, and [pos, m_songs.end()) are those that didn't match.

Also note that a set stores items in sorted order. Therefore, if getTitle() is used as the key (or at least the primary key) when sorting the members of the set, you may be able to do things a bit more efficiently--you can use the set's equal_range member to find all the songs with the same title. This will give you iterators to the beginning and end of the range with logarithmic complexity. You'll then copy that range (with linear complexity), so if the range you care about is only a small percentage of the entire set, this may give a substantial speed improvement.

Upvotes: 1

DeepakKg
DeepakKg

Reputation: 349

Unfortunately in functions like copy_if one can't use std::back_inserter to the containers which doesn't have push_back function and std::set doesn't have that, However you can achieve the same by copying it into the vector.

// Suppose i want to copy all occurrences of 1
set<int> v{1, 2, 1, 4,1, 6, 1, 1, 9, 10};
vector<int> newSet;
std::copy_if(v.begin(),v.end(),std::back_inserter(newSet),[](int val) {  return val == 1;});

But why are you using set. From the code, it doesn't looks like that Songs instance should be stored in sorted order.

Unless and until you need to store Songs in sorted order of Unique Elements you can use 'vector` to be able to achieve what you're trying to do by doing this

vector<int> v{1, 2, 1, 4,1, 6, 1, 1, 9, 10};
vector<int> newSet;
std::copy_if(v.begin(),v.end(),std::back_inserter(newSet),[](int val) { return val == 1;});

Upvotes: 1

Related Questions