现在的位置: 首页 > 自动控制 > 工业·编程 > 正文

实现从vector中过滤重复的数据

2014-09-10 06:39 工业·编程 ⁄ 共 2335字 ⁄ 字号 暂无评论

0、前言

相信有很有种情况下面要在vector下过滤掉重复的数据就比如在数组中需要过滤重复数据一样重要一般常用的方法,好像还是在学校中教的,进行匹配一遍,然后再进行插入既然有了STL容器,那么我们可以完全抛弃上面提到的一般方法,把效率提高至少1倍

1、思路

map也是我们常用的一种容器,他主要的保存方式是,也就是通过key来进行索引,而且这个key是不重复的,那么在我们过滤的前提下,map就是成败的关键了,看看如何把它用好

2、容易陷入的错误

a、一想到容器,很容易想到使用迭代器(iterator),但是对于map,加入数据量大的时候,进行iterator的操作很慢很慢!

b、容易想到,先把数据都插入到map中,再最后直接在写入vector中,其实这样又回到了a中

3、流程分析

假设我们要存放N多的数据(假设是海量的),那么我们需要避免对map进行iterator的操作(很慢很慢!)

于是在数据插入的时候,我先去从map中find一下,加入map中并不存在这个key,那么我们放心的插入到map中,同时插入到vector中。总之,每一次想到要插入vector我都想到map.find、map.insert,那么最终的vector就是不存在重复的,也同时避免了在map中使用迭代器(iterator)

4、一个简单的实例(class)

play_list.h:

#include "iostream" 

#include "string" 

#include "vector" 

#include "unordered_map" 

using namespace std; 

    

class PlayList 

public: 

    PlayList(); 

    ~PlayList(); 

  

    bool ReadFile(const string &path); 

    bool WriteFile(const string &path); 

  

    void AddPlayVideoPath(string play_video_path); 

  

private: 

    bool ReadFile(const string &path,  vector<string> &vec); 

    bool WriteFile(const string &path, vector<string> &vec); 

  

private: 

    vector<string> all_video_path_vec_; 

    unordered_map<string, string> all_video_path_map_; 

}; 

play_list.cpp:

#include "stdafx.h" 

  

#include "fstream" 

#include "play_list.h" 

    

PlayList::PlayList() 

  

    

PlayList::~PlayList() 

  

    

bool PlayList::ReadFile(const string &path) 

    return ReadFile(path, all_video_path_vec_); 

    

bool PlayList::WriteFile(const string &path) 

    return WriteFile(path, all_video_path_vec_); 

    

bool PlayList::ReadFile(const string &path, vector<string> &vec) 

    ifstream fin; 

    fin.open(path); 

    if (!fin.is_open()) 

    { 

        return false; 

    } 

  

    // 取出数据 

    string tmp; 

    while (fin >> tmp) 

    { 

        cout << tmp << endl; 

//      vec.push_back(tmp); 

        AddPlayVideoPath(tmp); 

    } 

  

    fin.close(); 

  

    return true; 

    

bool PlayList::WriteFile(const string &path, vector<string> &vec) 

    ofstream fout; 

    fout.open(path); 

  

    vector<string>::iterator it; 

    for (it = vec.begin(); it != vec.end(); it++) 

    { 

        fout << *it << endl; 

    } 

    fout.close(); 

  

    return true; 

    

void PlayList::AddPlayVideoPath(string play_video_path) 

    unordered_map<string, string>::iterator it; 

    it = all_video_path_map_.find(play_video_path); 

    if (it != all_video_path_map_.end()) 

    { 

        return; 

    } 

  

    all_video_path_map_.insert(pair<string, string>(play_video_path, "")); 

    all_video_path_vec_.push_back(play_video_path); 

作者:zengraoli

给我留言

留言无头像?