Moving elements satisfying a predicate from one container to another

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite
1












I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.



This is my implementation:



/**
* Moves all elements in the input container
* that satisfy the given predicate
* into the output container,
* and erases them from the input container.
* @tparam Container The container type.
* @tparam UnaryPredicate The predicate type.
* @param in The input container.
* @param out The output container.
* @param predicate The predicate to satisfy.
*/
template <class Container, class UnaryPredicate>
void move_and_erase_if(Container &in, Container &out, UnaryPredicate predicate)
// sort the input container so that all elements that
// satisfy the predicate are moved to the end.
std::sort(in.begin(), in.end(), [=](auto &a, auto &b)
return !predicate(a) && predicate(b);
);

// find the first element in the sorted container
// that satisfies the predicate.
// all elements following that element
// also satisfy the predicate.
auto it = std::find_if(in.begin(), in.end(), [=](auto &val)
return predicate(val);
);

// move the elements satisfying the predicate
// into the output container.
std::move(it, in.end(), std::back_inserter(out));

// erase the elements satisfying the predicate
// from the input container.
in.erase(it, in.end());



Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.



I've written an example application using the algorithm on ideone.










share|improve this question



























    up vote
    1
    down vote

    favorite
    1












    I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.



    This is my implementation:



    /**
    * Moves all elements in the input container
    * that satisfy the given predicate
    * into the output container,
    * and erases them from the input container.
    * @tparam Container The container type.
    * @tparam UnaryPredicate The predicate type.
    * @param in The input container.
    * @param out The output container.
    * @param predicate The predicate to satisfy.
    */
    template <class Container, class UnaryPredicate>
    void move_and_erase_if(Container &in, Container &out, UnaryPredicate predicate)
    // sort the input container so that all elements that
    // satisfy the predicate are moved to the end.
    std::sort(in.begin(), in.end(), [=](auto &a, auto &b)
    return !predicate(a) && predicate(b);
    );

    // find the first element in the sorted container
    // that satisfies the predicate.
    // all elements following that element
    // also satisfy the predicate.
    auto it = std::find_if(in.begin(), in.end(), [=](auto &val)
    return predicate(val);
    );

    // move the elements satisfying the predicate
    // into the output container.
    std::move(it, in.end(), std::back_inserter(out));

    // erase the elements satisfying the predicate
    // from the input container.
    in.erase(it, in.end());



    Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.



    I've written an example application using the algorithm on ideone.










    share|improve this question

























      up vote
      1
      down vote

      favorite
      1









      up vote
      1
      down vote

      favorite
      1






      1





      I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.



      This is my implementation:



      /**
      * Moves all elements in the input container
      * that satisfy the given predicate
      * into the output container,
      * and erases them from the input container.
      * @tparam Container The container type.
      * @tparam UnaryPredicate The predicate type.
      * @param in The input container.
      * @param out The output container.
      * @param predicate The predicate to satisfy.
      */
      template <class Container, class UnaryPredicate>
      void move_and_erase_if(Container &in, Container &out, UnaryPredicate predicate)
      // sort the input container so that all elements that
      // satisfy the predicate are moved to the end.
      std::sort(in.begin(), in.end(), [=](auto &a, auto &b)
      return !predicate(a) && predicate(b);
      );

      // find the first element in the sorted container
      // that satisfies the predicate.
      // all elements following that element
      // also satisfy the predicate.
      auto it = std::find_if(in.begin(), in.end(), [=](auto &val)
      return predicate(val);
      );

      // move the elements satisfying the predicate
      // into the output container.
      std::move(it, in.end(), std::back_inserter(out));

      // erase the elements satisfying the predicate
      // from the input container.
      in.erase(it, in.end());



      Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.



      I've written an example application using the algorithm on ideone.










      share|improve this question















      I've implemented a C++ algorithm that moves elements satisfying a given unary predicate from one container into the other, deleting them from the input container.



      This is my implementation:



      /**
      * Moves all elements in the input container
      * that satisfy the given predicate
      * into the output container,
      * and erases them from the input container.
      * @tparam Container The container type.
      * @tparam UnaryPredicate The predicate type.
      * @param in The input container.
      * @param out The output container.
      * @param predicate The predicate to satisfy.
      */
      template <class Container, class UnaryPredicate>
      void move_and_erase_if(Container &in, Container &out, UnaryPredicate predicate)
      // sort the input container so that all elements that
      // satisfy the predicate are moved to the end.
      std::sort(in.begin(), in.end(), [=](auto &a, auto &b)
      return !predicate(a) && predicate(b);
      );

      // find the first element in the sorted container
      // that satisfies the predicate.
      // all elements following that element
      // also satisfy the predicate.
      auto it = std::find_if(in.begin(), in.end(), [=](auto &val)
      return predicate(val);
      );

      // move the elements satisfying the predicate
      // into the output container.
      std::move(it, in.end(), std::back_inserter(out));

      // erase the elements satisfying the predicate
      // from the input container.
      in.erase(it, in.end());



      Is there a more efficient way to achieve this? Specifically, the call to std::find_if bugs me, as it applies the predicate to all elements a second time, until it finds the first one that satisfies it.



      I've written an example application using the algorithm on ideone.







      c++ algorithm c++11 collections






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited 34 mins ago









      200_success

      126k14146407




      126k14146407










      asked 1 hour ago









      CrushedPixel

      304




      304




















          2 Answers
          2






          active

          oldest

          votes

















          up vote
          3
          down vote



          accepted










          Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.



          If you still want to follow the sorting path, consider std::lower_bound instead of find_if.






          share|improve this answer




















          • std::partition is exactly what I was looking for. Thank you very much!
            – CrushedPixel
            1 hour ago










          • Or use stable_partition to keep insertion order.
            – Calak
            1 hour ago

















          up vote
          0
          down vote













          Complexity



          std::sort has at runtime complexity of at least $mathcalO(n logn)$, and requires that the given container type provides random access iterators (which are only few of them).



          Also, other than further assumptions in the later code, it doesn't seem sorting is actually required. Why not use a simple linear loop with std::find_if?



          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          out.push_back(std::move(*iter));
          iter = in.erase(iter);



          This has linear time complexity, and works with all types of iterators/containers!



          Design



          Currently, the algorithms requires the following properties of the output container:



          • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).


          • Values can only ever be move to the back of out, requiring the container to have a push_back member function.


          Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.



          To accomplish this, the algorithm could take an output iterator instead.



          template<class Container, class OutIter, class UnaryPredicate>
          OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          *out++ = std::move(*iter);
          iter = in.erase(iter);


          return out;




          Additinally, it would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.







          share|improve this answer




















          • That's O(n * O(erase)), likely O(n²). Inefficient.
            – Deduplicator
            22 mins ago











          • @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
            – hoffmale
            19 mins ago










          • in.erase(iter) is not O(1) for most containers.
            – Deduplicator
            18 mins ago











          • @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
            – hoffmale
            15 mins ago










          • If you only look at the standard containers… But QT for example has its own.
            – Deduplicator
            14 mins ago










          Your Answer




          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "196"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          convertImagesToLinks: false,
          noModals: false,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













           

          draft saved


          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206221%2fmoving-elements-satisfying-a-predicate-from-one-container-to-another%23new-answer', 'question_page');

          );

          Post as a guest






























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          3
          down vote



          accepted










          Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.



          If you still want to follow the sorting path, consider std::lower_bound instead of find_if.






          share|improve this answer




















          • std::partition is exactly what I was looking for. Thank you very much!
            – CrushedPixel
            1 hour ago










          • Or use stable_partition to keep insertion order.
            – Calak
            1 hour ago














          up vote
          3
          down vote



          accepted










          Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.



          If you still want to follow the sorting path, consider std::lower_bound instead of find_if.






          share|improve this answer




















          • std::partition is exactly what I was looking for. Thank you very much!
            – CrushedPixel
            1 hour ago










          • Or use stable_partition to keep insertion order.
            – Calak
            1 hour ago












          up vote
          3
          down vote



          accepted







          up vote
          3
          down vote



          accepted






          Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.



          If you still want to follow the sorting path, consider std::lower_bound instead of find_if.






          share|improve this answer












          Sorting the source is not specified as a requirement, so it seems that std::partition would do the necessary job more efficiently. As a perk benefit, std::partition returns the partition point, eliminating the need to std::find_if.



          If you still want to follow the sorting path, consider std::lower_bound instead of find_if.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 1 hour ago









          vnp

          37.6k12995




          37.6k12995











          • std::partition is exactly what I was looking for. Thank you very much!
            – CrushedPixel
            1 hour ago










          • Or use stable_partition to keep insertion order.
            – Calak
            1 hour ago
















          • std::partition is exactly what I was looking for. Thank you very much!
            – CrushedPixel
            1 hour ago










          • Or use stable_partition to keep insertion order.
            – Calak
            1 hour ago















          std::partition is exactly what I was looking for. Thank you very much!
          – CrushedPixel
          1 hour ago




          std::partition is exactly what I was looking for. Thank you very much!
          – CrushedPixel
          1 hour ago












          Or use stable_partition to keep insertion order.
          – Calak
          1 hour ago




          Or use stable_partition to keep insertion order.
          – Calak
          1 hour ago












          up vote
          0
          down vote













          Complexity



          std::sort has at runtime complexity of at least $mathcalO(n logn)$, and requires that the given container type provides random access iterators (which are only few of them).



          Also, other than further assumptions in the later code, it doesn't seem sorting is actually required. Why not use a simple linear loop with std::find_if?



          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          out.push_back(std::move(*iter));
          iter = in.erase(iter);



          This has linear time complexity, and works with all types of iterators/containers!



          Design



          Currently, the algorithms requires the following properties of the output container:



          • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).


          • Values can only ever be move to the back of out, requiring the container to have a push_back member function.


          Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.



          To accomplish this, the algorithm could take an output iterator instead.



          template<class Container, class OutIter, class UnaryPredicate>
          OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          *out++ = std::move(*iter);
          iter = in.erase(iter);


          return out;




          Additinally, it would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.







          share|improve this answer




















          • That's O(n * O(erase)), likely O(n²). Inefficient.
            – Deduplicator
            22 mins ago











          • @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
            – hoffmale
            19 mins ago










          • in.erase(iter) is not O(1) for most containers.
            – Deduplicator
            18 mins ago











          • @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
            – hoffmale
            15 mins ago










          • If you only look at the standard containers… But QT for example has its own.
            – Deduplicator
            14 mins ago














          up vote
          0
          down vote













          Complexity



          std::sort has at runtime complexity of at least $mathcalO(n logn)$, and requires that the given container type provides random access iterators (which are only few of them).



          Also, other than further assumptions in the later code, it doesn't seem sorting is actually required. Why not use a simple linear loop with std::find_if?



          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          out.push_back(std::move(*iter));
          iter = in.erase(iter);



          This has linear time complexity, and works with all types of iterators/containers!



          Design



          Currently, the algorithms requires the following properties of the output container:



          • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).


          • Values can only ever be move to the back of out, requiring the container to have a push_back member function.


          Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.



          To accomplish this, the algorithm could take an output iterator instead.



          template<class Container, class OutIter, class UnaryPredicate>
          OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          *out++ = std::move(*iter);
          iter = in.erase(iter);


          return out;




          Additinally, it would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.







          share|improve this answer




















          • That's O(n * O(erase)), likely O(n²). Inefficient.
            – Deduplicator
            22 mins ago











          • @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
            – hoffmale
            19 mins ago










          • in.erase(iter) is not O(1) for most containers.
            – Deduplicator
            18 mins ago











          • @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
            – hoffmale
            15 mins ago










          • If you only look at the standard containers… But QT for example has its own.
            – Deduplicator
            14 mins ago












          up vote
          0
          down vote










          up vote
          0
          down vote









          Complexity



          std::sort has at runtime complexity of at least $mathcalO(n logn)$, and requires that the given container type provides random access iterators (which are only few of them).



          Also, other than further assumptions in the later code, it doesn't seem sorting is actually required. Why not use a simple linear loop with std::find_if?



          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          out.push_back(std::move(*iter));
          iter = in.erase(iter);



          This has linear time complexity, and works with all types of iterators/containers!



          Design



          Currently, the algorithms requires the following properties of the output container:



          • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).


          • Values can only ever be move to the back of out, requiring the container to have a push_back member function.


          Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.



          To accomplish this, the algorithm could take an output iterator instead.



          template<class Container, class OutIter, class UnaryPredicate>
          OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          *out++ = std::move(*iter);
          iter = in.erase(iter);


          return out;




          Additinally, it would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.







          share|improve this answer












          Complexity



          std::sort has at runtime complexity of at least $mathcalO(n logn)$, and requires that the given container type provides random access iterators (which are only few of them).



          Also, other than further assumptions in the later code, it doesn't seem sorting is actually required. Why not use a simple linear loop with std::find_if?



          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          out.push_back(std::move(*iter));
          iter = in.erase(iter);



          This has linear time complexity, and works with all types of iterators/containers!



          Design



          Currently, the algorithms requires the following properties of the output container:



          • It has to be of the exact same type as the input container (so transferring values from a std::list to a std::vector isn't possible).


          • Values can only ever be move to the back of out, requiring the container to have a push_back member function.


          Both these restrictions are not necessarily required: Conceptually, there shouldn't be a problem moving the values at some other specified position.



          To accomplish this, the algorithm could take an output iterator instead.



          template<class Container, class OutIter, class UnaryPredicate>
          OutIter move_and_erase_if(Container& in, OutIter out, UnaryPredicate&& predicate)
          for(auto iter = std::find_if(in.begin(), in.end(), predicate);
          iter != in.end();
          iter = std::find_if(iter, in.end(), predicate)

          *out++ = std::move(*iter);
          iter = in.erase(iter);


          return out;




          Additinally, it would be nice to check at compile time whether Container::value_type matches std::iterator_traits<OutIter>::value_type and whether UnaryPredicate accepts an argument of type Container::value_type. This could be done with SFINAE or static_asserts.








          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 1 hour ago









          hoffmale

          5,192835




          5,192835











          • That's O(n * O(erase)), likely O(n²). Inefficient.
            – Deduplicator
            22 mins ago











          • @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
            – hoffmale
            19 mins ago










          • in.erase(iter) is not O(1) for most containers.
            – Deduplicator
            18 mins ago











          • @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
            – hoffmale
            15 mins ago










          • If you only look at the standard containers… But QT for example has its own.
            – Deduplicator
            14 mins ago
















          • That's O(n * O(erase)), likely O(n²). Inefficient.
            – Deduplicator
            22 mins ago











          • @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
            – hoffmale
            19 mins ago










          • in.erase(iter) is not O(1) for most containers.
            – Deduplicator
            18 mins ago











          • @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
            – hoffmale
            15 mins ago










          • If you only look at the standard containers… But QT for example has its own.
            – Deduplicator
            14 mins ago















          That's O(n * O(erase)), likely O(n²). Inefficient.
          – Deduplicator
          22 mins ago





          That's O(n * O(erase)), likely O(n²). Inefficient.
          – Deduplicator
          22 mins ago













          @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
          – hoffmale
          19 mins ago




          @Deduplicator: Please tell me how this solution would be $mathcalO(n^2)$, as it only goes over each element of in once. Did you overlook the iter parameter in the second call to std::find_if?
          – hoffmale
          19 mins ago












          in.erase(iter) is not O(1) for most containers.
          – Deduplicator
          18 mins ago





          in.erase(iter) is not O(1) for most containers.
          – Deduplicator
          18 mins ago













          @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
          – hoffmale
          15 mins ago




          @Deduplicator: Depends on the container. The only ones with $mathcalO(n)$ erase I can think of are std::vector and std::deque. If that matters, those could be special cased.
          – hoffmale
          15 mins ago












          If you only look at the standard containers… But QT for example has its own.
          – Deduplicator
          14 mins ago




          If you only look at the standard containers… But QT for example has its own.
          – Deduplicator
          14 mins ago

















           

          draft saved


          draft discarded















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f206221%2fmoving-elements-satisfying-a-predicate-from-one-container-to-another%23new-answer', 'question_page');

          );

          Post as a guest













































































          Comments

          Popular posts from this blog

          What does second last employer means? [closed]

          Installing NextGIS Connect into QGIS 3?

          One-line joke