valgrind Недопустимое чтение размера 4

Question

Я использую valgrind для обнаружения ошибки памяти, и результат выглядит следующим образом: Я думаю, что valgrind ссылается на функцию getScore(), которая, как представляется, не инициализируется.

==5149== Invalid read of size 4 
==5149== at 0x8050CC0: __gnu_cxx::__normal_iterator<USim*, std::vector<USim, std::allocator<USim> > >::__normal_iterator(USim* const&) (stl_iterator.h:720) 
==5149== by 0x80507C1: std::vector<USim, std::allocator<USim> >::begin() (stl_vector.h:464) 
==5149== by 0x804FE4A: UserUserSim::getScore(int&, MovieList*) (UserUserSim.cpp:36) 
==5149== by 0x804FD3F: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:28) 
==5149== by 0x804975C: main (main.cpp:44) 
==5149== Address 0xbec8acb0 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes 
==5149== 
==5149== Invalid read of size 4 
==5149== at 0x8050CC0: __gnu_cxx::__normal_iterator<USim*, std::vector<USim, std::allocator<USim> > >::__normal_iterator(USim* const&) (stl_iterator.h:720) 
==5149== by 0x80507E4: std::vector<USim, std::allocator<USim> >::end() (stl_vector.h:482) 
==5149== by 0x804FFC2: UserUserSim::getScore(int&, MovieList*) (UserUserSim.cpp:43) 
==5149== by 0x804FD3F: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:28) 
==5149== by 0x804975C: main (main.cpp:44) 
==5149== Address 0xbec8acb4 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes 
==5149== 
==5149== Invalid read of size 4 
==5149== at 0x804FE8D: UserUserSim::getScore(int&, MovieList*) (UserUserSim.cpp:45) 
==5149== by 0x804FD3F: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:28) 
==5149== by 0x804975C: main (main.cpp:44) 
==5149== Address 0x6a2eb60 is 0 bytes inside a block of size 128 free'd 
==5149== at 0x402ACFC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==5149== by 0x8051FC6: __gnu_cxx::new_allocator<USim>::deallocate(USim*, unsigned int) (new_allocator.h:98) 
==5149== by 0x805196A: std::_Vector_base<USim, std::allocator<USim> >::_M_deallocate(USim*, unsigned int) (stl_vector.h:156) 
==5149== by 0x8050D30: std::_Vector_base<USim, std::allocator<USim> >::~_Vector_base() (stl_vector.h:142) 
==5149== by 0x805089D: std::vector<USim, std::allocator<USim> >::~vector() (stl_vector.h:351) 
==5149== by 0x8050498: UserUserSim::getTop(int) (UserUserSim.cpp:136) 
==5149== by 0x804FD1D: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:26) 
==5149== by 0x804975C: main (main.cpp:44) 

Вот связанные исходный код: UseUserSim Класс:

#include <stdlib.h> 
#include "UserUserSim.h" 
UserUserSim::UserUserSim(string &query_url): 
    _query_url(query_url) 
{ 

} 

void UserUserSim::calculate(ostream &out){ 
    ifstream infile(_query_url.c_str()); 
    string line; 
    int movie_id; 
    int user_id; 
    MovieList* ml; 
    while(infile>>line){ 
     if (line[line.length()-1]==':'){ 
      movie_id=atoi(line.c_str()); 
      ml=MovieDictionary::getInstance().getMovie(movie_id); 
      if (ml==0) cout<<"shit"<<endl; 
      ml->sortList(); 
      out<<line<<'\n'; 
     } 
     else{ 
      user_id=atoi(line.c_str()); 
      if (_map.find(user_id)==_map.end()) 
       getTop(user_id); 

      float score=getScore(user_id,ml); 
      out<<score<<'\n'; 
     } 
    } 
} 
float UserUserSim::getScore(int &user_id, MovieList* ml){ 
    vector<USim>* p=_map[user_id]; 
    vector<UserScore>::iterator it=ml->begin(); 
    vector<USim>::iterator sim_it=p->begin(); 
    float score=0; 
    float score2=0; 
    int total_num=0; 
    float total_weight=0; 
    int it_user_id; 
    int sim_it_user_id; 
    while(it != ml->end() && sim_it != p->end()){ 
     it_user_id=(*it).user_id; 
     sim_it_user_id=(*sim_it).user_id; 
     //cout<<it_user_id<<" sdfsd "<<sim_it_user_id<<endl; 
     if (it_user_id>sim_it_user_id) 
      sim_it++; 
     else if (it_user_id<sim_it_user_id) 
      it++; 
     else{ // when the user id matches 
      score+=(*it).rating*(*sim_it).score; 
      score2+=(*it).rating; 
      total_num++; 
      total_weight+=(*sim_it).score; 
      sim_it++; 
      it++; 
     } 
    } 
    if (total_weight!=0) 
     score=score/total_weight; 
    else 
     score=3.37827;//score2/total_num; 
    return score; 
} 
typedef pair<int, float> mapPair; 
bool compareSim(USim p1, USim p2){ 
    return p1.score>p2.score; 
} 
bool compareID(USim p1, USim p2){ 
    return p1.user_id<p2.user_id; 
} 
void UserUserSim::getTop(int user_id){ 
    vector<USim> result; 
    vector<USim>* p=&result; 
    _map.insert(pair<int,vector<USim>*>(user_id,p)); 

    UserList* ul=UserDictionary::getInstance().getUser(user_id); 
    vector<MovieScore>::iterator it1; //the iterator for the userlist 
    vector<MovieScore>::iterator it2; 
    map <int,UserList *>::iterator it_dict; 
    vector<USim> score_list; //the iterator for the result list 
    //first read out those in cache: 
/* 
    if (UserSimCache::getInstance().prepareCache(user_id)){ 
     vector<USim>::iterator it; 
     for (it=UserSimCache::getInstance().getCache_begin(user_id);it!=UserSimCache::getInstance().getCache_end(user_id);++it){ 
      score_list.push_back((*it)); 
      cout<<"save once"<<user_id<<endl; 
     } 
    }*/ 
    // Then calculate those not in cache: 
    for (it_dict=UserDictionary::getInstance().begin();it_dict!=UserDictionary::getInstance().end();++it_dict){ 
     if (/* !UserSimCache::getInstance().hasOneCache(it_dict->first) &&*/ (*it_dict).second->size()>2){ 
      float score=0; 
      it1=ul->begin(); 
      it2=(*it_dict).second->begin(); 
      int match_pair=0; 
      while(it1!=ul->end() && it2!=(*it_dict).second->end()){ 
       int uid1=it1->movie_id; 
       int uid2=it2->movie_id; 
       if (uid1>uid2) 
        it2++; 
       else if (uid1<uid2) 
        it1++; 
       else{ 
        score+=(it1->rating)*(it2->rating); 
        it1++; 
        it2++; 
        ++match_pair; 
       } 
      } 
      if (score!=0 && match_pair>=2){ 
       USim us; 
       us.user_id=it_dict->first; 
       us.score=score; 
       score_list.push_back(us); 

       //create the Cache for further use: 
       //UserSimCache::getInstance().setCache(us.user_id); 
       //UserSimCache::getInstance().addCache(user_id,score); 
      } 
     } 
    } 
    // We have finished calculation, do not need to store the cache: 
    //UserSimCache::getInstance().cleanCache(user_id); 

    int k=10; 
    //partial_sort(score_list.begin(),score_list.begin()+k,score_list.end(),compareSim); 
    vector<USim>::iterator v_it; 
    //store these users into the user_sim vector 
    for (v_it=score_list.begin();v_it<score_list.begin()+k;++v_it){ 
     USim us=(*v_it); 
     p->push_back(us); 
    } 
    sort(p->begin(),p->end(),compareID); 
} 

MovieDictionary Класс:

#ifndef MOVIEDICTIONARY_H 
#define MOVIEDICTIONARY_H 

using namespace std; 
#include "MovieList.h" 
#include <vector> 
#include <map> 
class MovieDictionary{ // a singelton 
public: 
    static MovieDictionary& getInstance(); 

    void addMovie(const int &id,MovieList *&p); 
    MovieList* getMovie(const int &id); 
private: 
    map <int,MovieList *> _id_map; 
    static void CleanUp(); 
    MovieDictionary(); 
    ~MovieDictionary(){} 

    //not copyable: 
    MovieDictionary(MovieDictionary const&); 
    MovieDictionary& operator=(MovieDictionary const&); 

    static MovieDictionary* MInstance; 

}; 

#endif 


#include "MovieDictionary.h" 
//Singelton Implementation: 
MovieDictionary* MovieDictionary::MInstance = 0; 
MovieDictionary::MovieDictionary(){atexit(&CleanUp);} 
void MovieDictionary::CleanUp(){delete MInstance; MInstance=0;} 
MovieDictionary& MovieDictionary::getInstance(){ 
    if (MInstance==0) 
     MInstance = new MovieDictionary(); 
    return *MInstance; 
} 

//add and get operation 
void MovieDictionary::addMovie(const int &id, MovieList *&p){ 
    _id_map.insert(pair<int, MovieList*>(id,p)); 
} 
MovieList* MovieDictionary::getMovie(const int &id){ 
    if (_id_map.find(id)==_id_map.end()) 
     return 0; 
    return _id_map[id]; 
} 

MovieList Класс:

#include "MovieList.h" 
MovieList::MovieList(const int &mid): 
    id(mid) 
{} 

void MovieList::add(const int &user_id, const int &rating){ 
    UserScore us; 
    us.user_id=user_id; 
    us.rating=rating; 
    _list.push_back(us); 
} 
void MovieList::displayStats(ostream &out){ 
    int rating_count[5]={0,0,0,0,0}; 
    int total_num=0; 
    vector<UserScore>::iterator it; 
    for (it=_list.begin();it<_list.end();it++){ 
     rating_count[(*it).rating-1]++; 
     total_num++; 
    } 
    float avg=0; 
    for (int i=0;i<5;i++) 
     avg+=(i+1)*rating_count[i]; 
    avg=avg/total_num; 
    cout<<"# of users:"<<total_num<<endl; 
    cout<<"Rates as 1:"<<rating_count[0]<<endl; 
    cout<<"Rates as 3:"<<rating_count[2]<<endl; 
    cout<<"Rates as 5:"<<rating_count[4]<<endl; 
    cout<<"Average rating:"<<avg<<endl; 
} 

struct compare{ 
    bool operator()(UserScore u1,UserScore u2){ 
     return (u1.user_id<u2.user_id); 
    } 
}compareUserID; 
void MovieList::sortList(){ 
    sort(_list.begin(),_list.end(),compareUserID); 
} 

Я горе что я или не правильно объявляю MovieList * ml в функции calculate() класса UserUserSim, поскольку первая ошибка памяти, кажется, лежит там. Но я не могу понять, почему это неправильно.

PS: входной файл в формате, как: movie_id: user_id user_id user_id ... movie_id: user_id user_id user_id

и ошибка не будет происходить до тех пор, очень поздно (возможно, выполнить на 5 000-й строке входного файла).

Я попытался прокомментировать функцию getScore(), и теперь ошибка, похоже, лежит в функции getTop():

==5339== Invalid read of size 4 
==5339== at 0x805037A: UserUserSim::getTop(int) (UserUserSim.cpp:133) 
==5339== by 0x804FD1D: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:26) 
==5339== by 0x804975C: main (main.cpp:44) 
==5339== Address 0x5ce87fc is 4 bytes after a block of size 16 alloc'd 
==5339== at 0x402B9B4: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so) 
==5339== by 0x80520A3: __gnu_cxx::new_allocator<USim>::allocate(unsigned int, void const*) (new_allocator.h:92) 
==5339== by 0x8051B81: std::_Vector_base<USim, std::allocator<USim> >::_M_allocate(unsigned int) (in /home/timyitong/hw5_origin/Code/Implementation/recommend) 
==5339== by 0x805102A: std::vector<USim, std::allocator<USim> >::_M_insert_aux(__gnu_cxx::__normal_iterator<USim*, std::vector<USim, std::allocator<USim> > >, USim const&) (vector.tcc:327) 
==5339== by 0x80509C4: std::vector<USim, std::allocator<USim> >::push_back(USim const&) (stl_vector.h:834) 
==5339== by 0x80502F8: UserUserSim::getTop(int) (UserUserSim.cpp:117) 
==5339== by 0x804FD1D: UserUserSim::calculate(std::ostream&) (UserUserSim.cpp:26) 
==5339== by 0x804975C: main (main.cpp:44) 

Answer 1

Проблема заключается здесь: в функции getTop() из класса UserUserSim, последние несколько строк:

for (v_it=score_list.begin();v_it<score_list.begin()+k;++v_it){ 
    USim us=(*v_it); 
    p->push_back(us); 
} 

Я забыл проверить, что иногда итератор score_list.begin() + k будет превышать score_list.end().

Answer 2

Вы можете инициализировать ml до значения, например, 0 в calculate(): От взглядов его случайное значение в ml используется, когда первая строка файла не заканчивается двоеточием. Учитывая, что вы дали слишком много, но также и неполную информацию, это то, что я буду смотреть в первую очередь.

Answer 3

Первое, что выделяется именно тем, что внутри getTop вы используете локальную переменную result в качестве отображаемого "данных", члена вашей карты _map.

void UserUserSim::getTop(int user_id){ 
    vector<USim> result; 
    vector<USim>* p=&result; 
    _map.insert(pair<int,vector<USim>*>(user_id,p)); 
    ... 

Когда getTop заканчивается, локальный объект result получает автоматически уничтожается, а _map продолжает жить. Это означает, что указатель, хранящийся в _map, становится недействительным: он указывает на «мертвую» и полностью бесполезную ячейку памяти.

Между тем, вы продолжаете использовать _map в других функциях вашего кода и получать доступ к отображаемым данным. Например

float UserUserSim::getScore(int &user_id, MovieList* ml){ 
    vector<USim>* p=_map[user_id]; 
    ... 

Как вы ожидаете, что это сработает?