How can we efficiently store objects using stl containers? (viz. for searching based on values of their fields)

user_1911652 0
Viewed 109

I have objects of something like this:

struct stStudents 
{
    int roll_number; // Can be think as unique key
    std::string name;
    // There could be more fields here
}

I need to store these objects using stl containers in such a way that I should be able to search them as fast as possible based on field(s) e.g roll_number or name (or both) in above example.

What I already tried/thought of:

  1. As plain as it can get, if I simply store them in std::vector (and probably by using std::find_if) searching will be O(n).

  2. With std::set and std::map it would take O(log N), but for that however overloaded comparison operator of the object needs to be based on particular field (or may be set of fields by using std::tie)

  3. Having various std::unordered_set of pointers (inside struct) to those objects. And define comparison operator in the struct based on search criteria (just like we define multiple indices in database). This will be O(1) search but limited to predefined search criteria.

Question:

How are these approaches and what are other better alternatives can we think of?

c++11 stl c++
1 Answers

Map and set are the best when in comes to searching.
So if we really want only speed in Searching then make maps for both the name and roll. But we are giving up on Space efficiency.

Sample Code : Written in Visual Studio 2012
both search functions could attain O(log(N)).

typedef struct _tagStudent
{
    int m_nRoll;
    std::string m_strName;
    _tagStudent(): m_nRoll(0)
    {}
    _tagStudent( int nRoll, std::string strName): m_nRoll( nRoll ), 
        m_strName(strName)
    {}
    bool operator<( _tagStudent x) const
    {
        return x.m_nRoll > m_nRoll;
    }
}Student;

class Students
{
    std::map< int, Student > m_mapStudent;
    std::map< std::string, std::set<Student> > m_mapStudentIndexName;
public:
    Students();
    ~Students();
    //Adding students Index
    void Add( const Student & );
    //Searching Students by Roll
    Student Search( const int& ) const;
    //Searching Students by Name
    std::set<Student> Search( const std::string&) const;
};


Students::Students()
{}
Students::~Students()
{}
void Students::Add( const Student& oStudent )
{
    m_mapStudent[oStudent.m_nRoll] = oStudent;
    m_mapStudentIndexName[oStudent.m_strName].insert(oStudent);
}

Student Students::Search( const int& nRoll ) const
{
    if( m_mapStudent.find( nRoll ) != m_mapStudent.end() )
    {
        return m_mapStudent.at( nRoll );
    }
    return Student();
}
std::set<Student> Students::Search( const std::string& strName) const
{
    std::set<Student> oStudents;
    if( m_mapStudentIndexName.find( strName ) != m_mapStudentIndexName.end() )
    {
        return m_mapStudentIndexName.at(strName);
    }
    return std::set<Student>();
}

int _tmain(int argc, _TCHAR* argv[])
{   
    Students oStudents;
    oStudents.Add( Student(1, "Tom") );
    oStudents.Add( Student(2, "Jerry") );
    oStudents.Add( Student(15, "Jerry") );
    oStudents.Add( Student(3, "Tim") );

    auto search1 = oStudents.Search( 1 );
    auto search3 = oStudents.Search( "Jerry" );

    return 0;
}
user_66326940
Related