Search code examples
c++stlmultimap

Usage of multimap with next_permutation c++

i am just trying to implement Knapsack Problem in a Naive way to stress test my original solution.

MY CODE

double StressTest(multimap<int, int> ValWt, int KnapscakWeight)
{
    vector<double> TotalValue;
    double Temp_KnapsackWeight = 0.0;
    double Value = 0.0;
    multimap<int, int>::iterator itr1;// = ValWt.begin();

    do
    {
        itr1 = ValWt.begin();
        Temp_KnapsackWeight = KnapscakWeight;
        while( (Temp_KnapsackWeight > 0) && (itr1 != ValWt.end()) )
        {
            if(itr1->second > Temp_KnapsackWeight)
            {
                Value += ( (Temp_KnapsackWeight/itr1->second) * itr1->first );
                Temp_KnapsackWeight = 0;
            }

            else
            {
                Temp_KnapsackWeight -= itr1->second;
                Value += itr1->first;
            }
            itr1++;
        }

        TotalValue.push_back(Value);
        Value = 0.0;

    }while( next_permutation(ValWt.begin(), ValWt.end()) );

    return *max_element(TotalValue.begin(), TotalValue.end());
}

ERROR

In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from 2_max_val_of_loot.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h: In instantiation of ‘void std::iter_swap(_ForwardIterator1, _ForwardIterator2) [with _ForwardIterator1 = std::_Rb_tree_iterator<std::pair<const int, int> >; _ForwardIterator2 = std::_Rb_tree_iterator<std::pair<const int, int> >]’:
/usr/include/c++/7/bits/stl_algo.h:2926:22:   required from ‘bool std::__next_permutation(_BidirectionalIterator, _BidirectionalIterator, _Compare) [with _BidirectionalIterator = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]’
/usr/include/c++/7/bits/stl_algo.h:2966:2:   required from ‘bool std::next_permutation(_BIter, _BIter) [with _BIter = std::_Rb_tree_iterator<std::pair<const int, int> >]’
2_max_val_of_loot.cpp:39:53:   required from here
/usr/include/c++/7/bits/stl_algobase.h:148:11: error: use of deleted function ‘typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type std::swap(std::pair<_T1, _T2>&, std::pair<_T1, _T2>&) [with _T1 = const int; _T2 = int; typename std::enable_if<(! std::__and_<std::__is_swappable<_T1>, std::__is_swappable<_T2> >::value)>::type = void]’
       swap(*__a, *__b);
       ~~~~^~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/7/bits/char_traits.h:39,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from 2_max_val_of_loot.cpp:1:
/usr/include/c++/7/bits/stl_pair.h:503:5: note: declared here
     swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete;

MY OBSERVATION

  1. next_permutation() is creating error, but why i don't understand why.

  2. next_permutation() requires bidirectional iterator and multimap iterator is a bidirectional iterator.

  3. I doubt as multimap are sorted always, that's why the error is shown ??

Please Help. Thanking You.

Solution

  • You cannot use std::map or std::multimap (or unordered versions) as std::next_permutation requires:

    -BidirIt must meet the requirements of ValueSwappable and LegacyBidirectionalIterator.

    but std::multimap values are not swappable as key in the map is not mutable:

    value_type std::pair<const Key, T>

    (emphasis is mine)

    Less formally order of elements in map is determined and cannot me changed. You have to use different container like std::vector to perform this operation.