c++: How to transform a map iterator which point to pair into a “regular” pair pointe

[danalovesc]

those are the maps:

multimap<SortKey,T> firstMap;
    multimap<SearchKey,pair<SortKey,T>*> secondMap;


    template <class T,class SortKey, class SearchKey> bool GarageDataBase<T,SortKey,SearchKey>::Add(T data,SortKey key1, SearchKey key2) 
    {
     multimap<SortKey,T>::iterator it;
     it=(firstMap.insert(pair<SortKey,T>(key1,data)));
     pair<SortKey,T> *mizi=&*it;
     
     secondMap.insert(pair<SearchKey,pair<SortKey,T>*>(key2,mizi));
     return true;
    }

I am trying to insert a pair into the firstMap and get a pointer to this pair and insert it into the "second" field in the secondMap

so that i could go into my firstMap from the secondmap.

pair<SortKey,T> *mizi=&*it;

this doesn't compile saying :

error C2440: 'initializing' : cannot convert from 'std::pair<_Ty1,_Ty2> *' to 'std::pair<_Ty1,_Ty2> *'

any idea whats going on or maybe a better way to make it work?

[vijayan121]

The value_type of a std::multimap<KEY,T> is std::pair< const KEY, T > . So,

std::multimap<SortKey,T> firstMap;
std::multimap<SearchKey, pair< const SortKey, T >* > secondMap;


// ...
     std::multimap<SortKey,T>::iterator it = firstMap.insert( std::make_pair(key1,data) ) ;

     std::pair< const SortKey, T >* mizi = &*it ;
     secondMap.insert( std::make_pair(key2,mizi) ) ;
// ...

[danalovesc]

ok this works, but when i try to remove an element: i go to secondMap which contains in second field a pointer to the first map, now when i try to erase it it gives me problems again:

template <class T,class SortKey, class SearchKey> T GarageDataBase<T,SortKey,SearchKey>::Remove(SearchKey toRemove) 
{
	multimap<SearchKey,pair<const SortKey,T>*>::iterator it;
	it=secondMap.find(toRemove);
	multimap<SortKey,T>::const_iterator itr;
	itr=(it->second);//pointer to a pair in the first map
	firstMap.erase(itr);
	
}

error C2664: 'std::_Tree_iterator<_Mytree> std::_Tree<_Traits>::erase(std::_Tree_const_iterator<_Mytree>)' : cannot convert parameter 1 from 'std::_Tree_const_iterator<_Mytree>' to 'std::_Tree_const_iterator<_Mytree>'

error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::pair<_Ty1,_Ty2>' (or there is no acceptable conversion)

any thoughts?

[mike_2000_17]

I have to say that I disapprove greatly of this code you posted. I cannot sanction the idea of getting a pointer to a pair that is used in a map or multimap object. This is because you don't know, and I don't know, how multimap implements it list of pairs (is it a linked-list or an array?). The standard prescribes that the iterators given by multimap are bidirectional iterators (not random-access iterators) which could indicate that the implementation is a double linked-list (however not guaranteed). There is a good reason why this is not strictly defined: freedom of choice = optimization possibilities. So, I don't know which is used and, as they say, ignorance is bliss (which holds very well with the idea of abstraction in C++).

The problem with this, is that there is no guarantee that the pointer to a pair in the map will remain the valid or still pointing to the same pair after you add or remove any element from the map (resorting might shift all the elements). I highly recommend you rethink your implementation to avoid taking a pointer to a pair inside the map.

For the compiler errors you are getting, first, a pointer to a pair and a map iterator is not the same, so the assignment of itr to it->second is not valid and can never be made valid by any tricks. Imagine you have a linked-list implementation, then the map will store each pair within a node of the list along with the pointers to the previous and next nodes. So, a pointer to the pair (contained in the node) does not have the information about the previous and next nodes, so a conversion is impossible (there is a loss of information when getting the pointer to the pair which cannot be reconstructed without an extremely weird and convoluted hack). If the map is implemented as a normal array (which makes the iterator type pretty much the same as an ordinary pointer), it could work in principle, but the fact the the iterator from the multimap is a bi-directional iterator rules out that possibility (it might be possible if it was a random-access iterator, but it is not).

One naive solution is to use a multimap iterator in the secondMap instead of a pointer. However, this does not work. If the map is a linked-list, then the iterator would be copied when it is assigned to the element of secondMap and that will "freeze" its state. In other words, the previous and next pointers in the iterator would point to the linked-list nodes that were before and after that element at the time that it was provided by firstMap, but could no longer make sense by the time you use it (after add/erase operations, and resorting, of firstMap). If the multimap is a normal array, more-or-less the same problem occurs, the iterator will point to the position of the element in the array at the time it was given by the firstMap, which could change due to resorting by the time you use the iterator again.

Another naive solution is to store a pointer to the iterator as the mapped value of secondMap. This is even worse, because the iterators that are provided by firstMap are just copies of internally used iterators (if any at all). They are volatile and taking their address is meaningless because they will rapidly go out of scope and make that pointer invalid.

The only way out is to change your design (as far as I know) or to implement your own container with two keys and some special sorting and searching. For example, maybe secondMap could map search keys to sort keys and then use the sort key obtained from a search key to get the pair from the firstMap. Of course, I understand you might want to avoid those two loop-up operations. Give more details on why you need those two levels of keys and we might be able to help better in finding an alternative.

[danalovesc]

Thank you very much for your replay.

This is what we're trying to do.

We need to have a Template which keeps the values sorted by a certain key lets call it key1, but when we want to remove an object, we need to search it and remove it by a different key lets call it key2, we also need to add/remove in a O(LogN) and have a "Top" method which returns the object with the minimal key1 (the first key) in O(1).

we are trying to make a Template using 2 maps:

first will hold key1+Data
second will hold key2+pointer to the matching map-node in the firstMap.

this should give us the requested complexity, we manged to implement Top and Add however we got stuck in Remove as posted earlier. (pointer to iterator for erase purpose).

We will be glad to hear other alternatives, using STL.

Thank you again.

[mike_2000_17]

In that case, the solution I proposed at the end of my last post is not worse than that, at least in terms of complexity. The Top function is trivial since you have a map of key1 to data, so getting the first element is O(1) and fulfills you requirement. Then, the Add function has now a complexity of O(logN) but it is actually O(2logN) because you add an entry to first- and second-Map. If you have a Remove function implemented as a look-up of key1 based on key2, and then a look-up of Data based on key1, then the complexity is two calls to a O(logN) function (multimap::find()) which makes the complexity O(2logN) just like the Add function. I believe this meets the requirements. However, if you are looking to get rid of that factor of 2, you are in trouble.

[danalovesc]

Ok, thanks I understood what u were saying.
2logN is perfect.
The part i didn't understand, you say that after i find what i want to remove by key2, and i go to find the data by key1 - the problem is - this a multimap that can contain identical key1s for different data, how do i make sure that the data i find by key1 is the same as the one i was pointing at and not a different data with the same key - key1?
i know that when i have an iterator pointing at my object i can use map.erase on that iterator, should i just use the pointer iterator on which i have in the secondMap to erase the pointed value on the firstMap? (and did u mean i should keep a pointer to an iterator on the secondMap or an iterator?)
thanks!

[mike_2000_17]

>>how do i make sure that the data i find by key1 is the same as the one i was pointing at and not a different data with the same key - key1?
You can't, that's the problem with multimap. If you absolutely need to have several elements associated with key1 (can't you make key1 unique somehow?). Then you would need an extra level of indirection.

>>should i just use the pointer iterator on which i have in the secondMap to erase the pointed value on the firstMap?
NO absolutely not, read my first post. DO NOT HOLD A POINTER TO AN ITERATOR OR AN ITERATOR OR A POINTER TO THE OBJECT IN secondMap!

Here is a solution to your problem (which is not trivial btw, so don't feel bad for having trouble with it, I had a bit of trouble with it myself). I implemented it as a class just for clarity. It has a bit of memory overhead, but if the object (Data) is big enough it should be amortized.

template <class SortKey, class SearchKey, class DataType>
class SortSearchList {
  private:
    typedef std::pair<SortKey,DataType*> KeyDataPair;
    typedef std::multimap<SortKey,KeyDataPair> SortMapType;
    typedef std::multimap<SortKey,KeyDataPair>::iterator SortMapIter;
    typedef std::map<SearchKey,KeyDataPair> SearchMapType;
    typedef std::map<SearchKey,KeyDataPair>::iterator SearchMapIter;

    SortMapType sortedMap;
    SearchMapType searchableMap;
  public:
    DataType& Top() {
      return *(sortedMap.begin()->second.second); //all calls are constant time complexity.
    };

    void Add(SearchKey aSearchKey, SortKey aSortKey, const DataType& aData) {
      KeyDataPair element; //constant complexity.
      element.first = aSortKey; //constant complexity.
      element.second = new DataType(aData); //"constant" complexity (heap dependent).
      searchableMap[aSearchKey] = element; //A*logN complexity. (you probably want to add a test for duplicate of searchkey)
      sortedMap.insert(std::pair<SortKey,KeyDataPair>(aSortKey,element)); //B*logN complexity.
      //overall complexity A*logN + B*logN + constant terms = O(logN)
    }; 

    void Remove(SearchKey aSearchKey) {
      SearchMapIter itsearch = searchableMap.find(aSearchKey); //A*logN complexity.
      if(itsearch != searchableMap.end()) {
        std::pair<SortMapIter,SortMapIter> itrngsort = sortedMap.equal_range(itsearch->second.first); //B*logN complexity
        for(SortMapIter itsort = itrngsort.first; itsort != itrngsort.second; ++itsort) {
          if(itsort->second.second == itsearch->second.second) { //if the objects correspond, then remove:
            sortedMap.erase(itsort); //amortized constant complexity.
            delete itsearch->second.second; //clean up the object itself.
            searchableMap.erase(itsearch); //amortized constant complexity.
            break; //get out of there.
          };
        };
      };
      //overall complexity: A*logN + B*logN + constant terms = O(logN)
    };
};

I hope this makes sense for you.

[vijayan121]

If you feel at home with templates, you might want to have a look at boost::multi_index<>. http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/index.html

For example, a multi_index with two ordered non_unique keys would look something like this:

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>
using namespace ::boost ;
using namespace ::boost::multi_index ;
using namespace std ;

struct A
{
    A( int i, const char* n, double d ) : id(i), _name(n), _data(d) {}

    const int id ; // non-unique key
    const string& name() const { return _name ; } // non-unique key

    // tags for lookup
    struct by_id {} ;
    struct by_name {} ;

    private :
        string _name ;
        double _data ;
        // ...

        friend inline ostream& operator<< ( ostream& stm, const A& a )
        {
            return stm << "{ " << a.id << ", " << a.name()
                       << ", " << a._data << " }" ;
        }
} ;

typedef multi_index_container
    <

        A,

        indexed_by<
                 ordered_non_unique< tag<A::by_id>,
                        BOOST_MULTI_INDEX_MEMBER( A, const int, id ) >,

                 ordered_non_unique< tag<A::by_name>,
                    BOOST_MULTI_INDEX_CONST_MEM_FUN( A, const string&, name ) >
                  >

    > dual_key_multimap ;

template< typename TAG, typename MULTI_INDEX_CNTR > inline
void print( MULTI_INDEX_CNTR& multi_index_cntr, ostream& stm = cout )
{
    typename MULTI_INDEX_CNTR::template index<TAG>::type& seq =
                                     multi_index_cntr.get<TAG>() ;
    copy( seq.begin(), seq.end(),
          ostream_iterator<typename MULTI_INDEX_CNTR::value_type>(stm,"\n") ) ;
}

template< typename TAG, typename MULTI_INDEX_CNTR, typename KEY > inline
void erase_all_with_key( MULTI_INDEX_CNTR& multi_index_cntr, const KEY& key )
{
    typedef typename MULTI_INDEX_CNTR::template index<TAG>::type SEQ ;
    SEQ& seq = multi_index_cntr.get<TAG>() ;
    seq.erase( seq.lower_bound(key), seq.upper_bound(key) ) ;
}

int main()
{
    A a[] = { A( 1, "abcd", 123.4 ), A( 2, "efgh", 234.5 ),
              A( 3, "ijkl", 345.6 ), A( 4, "mnop", 456.7 ),
              A( 4, "mnop", 567.8 ), A( 3, "abcd", 678.9 ),
              A( 1, "efgh", 789.1 ), A( 2, "ijkl", 891.2 ) } ;
    dual_key_multimap mmap_2keys( a, a+sizeof(a)/sizeof(*a) ) ;

    // insert
    mmap_2keys.insert( A( 2, "abcd", 999.9  ) ) ;

    cout << "\n-------  by id  ---------\n" ;
    print<A::by_id>( mmap_2keys ) ;
    cout << "\n-------  by name  -------\n" ;
    print<A::by_name>( mmap_2keys ) ;

    // erase all elements with id == 2
    erase_all_with_key<A::by_id>( mmap_2keys, 2 ) ;
    cout << "\n-----  by name after erase id 2 ---\n" ;
    print<A::by_name>( mmap_2keys ) ;

    // erase all with name == 'abcd'
    erase_all_with_key<A::by_name>( mmap_2keys, "abcd" ) ;
    cout << "\n-----  by id after erase name 'abcd' ----\n" ;
    print<A::by_id>( mmap_2keys ) ;
}

[danalovesc]

@mike:

Wow, thanks for your great replay.

It took me sometime to figure out what u did there - had to learn some new STL methods like
equal_range and much more, and i have to say this solution was not at all trivial.

I tried to run it by saving it onto an h file adding to my project and creating an instance of the searchsortlist in main and try using the methods
when i try to run it gives me this:

error C2146: syntax error : missing ';' before identifier 'SearchMapIter' 
error C2146: syntax error : missing ';' before identifier 'SearchMapIter' 
error C2146: syntax error : missing ';' before identifier 'SearchMapIter' 
error C2146: syntax error : missing ';' before identifier 'SortMapIter' 
error C2146: syntax error : missing ';' before identifier 'SortMapIter' 
error C2146: syntax error : missing ';' before identifier 'SortMapIter' 
error C4430: missing type specifier - int assumed. Note: C++ does not support default-int 
error C4430: missing type specifier - int assumed. Note: C++ does not support default-int 
error C4430: missing type specifier - int assumed. Note: C++ does not support default-int

do i need to #include anything to get it to work??
Thanks again for your effort and answers!

[danalovesc]

@vijayan121

Thanks for your reply, i really am not familiar with boost, still trying to figure out what going there and how can use it for my needs!

[danalovesc]

@mike:

I've fixed the problems I had - compiler differences :)

My question about your code :

on line 30, we run between the Iterators which mark identical values with a for loop..

what happens if all the keys are identical? we could run on the entire map? and this is O(N) complexity.. any solution for that?

[mike_2000_17]

@mike:
what happens if all the keys are identical? we could run on the entire map? and this is O(N) complexity.. any solution for that?

Sorry for the late reply. In order to avoid a O(N) on the search for the right object associated to a key that is the same for N other objects. You would have to sort with respect to object pointer too. For example, this is a composite key that could be added:

template<class SortKey,class DataType>
struct CompositeKey {
  SortKey key;
  DataType* data;
  CompositeKey(SortKey aKey, DataType* pObj) : key(aKey), data(pObj) { }; //not needed in C++0x
  bool operator <(const CompositeKey<SortKey,DataType>& RHS) const {
    if( key < RHS.key)
      return true;
    else if(key > RHS.key)
      return false;
    else //this is the case that key == RHS.key
      return (data < RHS.data); //apply second level of sorting.
  };
};

This makes all the keys unique (map instead of multimap) but there could be quite a bit of memory and processing overhead by introducing a larger and more complex key type. So in this case, it is a matter of finding the optimum for your case (do you expect that normally there are only a few elements that have the same key or is it more usual to have a lot of elements and only a few different keys). Computer scientist like to put everything in O() form because it is nice and easy, but in real-life there are often situations where something with a worst O() is actually better for a specific case.