Database of students At first, I had Database to contain std::list&lt;Student&gt; students, but because there are over 2000 students, searching by students should not be done in linear time.  However, searching for students can be by name or by student number.  To enable both searches in logarithmic time, I decided to give Database two maps that hold the same 2000+ students.  Inserting and removing a student will have to update both maps.  This doubles the time, but I figured that \$2*O(logN)\$ is still much better than \$O(N)\$.  If there are to be k different search criteria later on, then \$k*O(logN)\$ is still better than \$O(N)\$ up to, say, k = 20 or so.  Agree?

Space complexity is a different matter though.  Is the doubling of memory usage bad design here, for 2000+ students?  Tripling?  Quadrupling?

Is there a better solution altogether?

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;memory&gt;
#include &lt;map&gt;

class Student {
    std::string surname, firstName;
    long studentNumber;
public:
    std::string getSurname() const {return surname;}
    std::string getFirstName() const {return firstName;}
    std::string fullName() const {return firstName + ' ' + surname;}
    long getStudentNumber() const {return studentNumber;}
};

class Database {
    std::multimap&lt;std::string, std::shared_ptr&lt;Student&gt;&gt; mapByName;
    std::map&lt;long, std::shared_ptr&lt;Student&gt;&gt; mapByStudentNumber;
public:
    void insertStudent (const std::shared_ptr&lt;Student&gt;&amp; p) {
        mapByName.emplace (getName(p), p);
        mapByStudentNumber.emplace (p-&gt;getStudentNumber(), p);
        // 2 insertions needed.
    }
    inline void removeStudentByStudentNumber();
    inline void removeStudentByName();
private:
    void remove (const std::shared_ptr&lt;Student&gt;&amp; p) {
        mapByName.erase(getName(p));
        mapByStudentNumber.erase(p-&gt;getStudentNumber());
        // 2 removals needed.
    }
    std::string getName (const std::shared_ptr&lt;Student&gt;&amp; p) const {return p-&gt;fullName();}
};

inline void Database::removeStudentByStudentNumber() {
    long studentNumber;
    std::cout &lt;&lt; "Student number? ";
    std::cin &gt;&gt; studentNumber;
    const auto it = mapByStudentNumber.find(studentNumber);
    if (it == mapByStudentNumber.end()) {
        std::cout &lt;&lt; "No student with that student number exists.\n\n";
        return;
    }
    remove(it-&gt;second);
}

inline void Database::removeStudentByName() {
    // Similar to above
}

int main() {}
This code is not complete so difficult to give a full review, but here are my thoughts.

Student

Put public methods first

This point is debatable, but I generally think it's better to have public methods before private variables. This is the only thing users of your class should care about, so make it easier to find.

Use variable name forename

forename is a better variable name than firstName, and fits better with surname (as apposed to lastName).

Type alias std::string

I think it would be clearer to type alias std::string for the names, if you make this public, the database class can use this alias to make the map definition clearer too:

using NameType = std::string;


Add missing constructors

Not sure if these were left out intentionally, but a simple forwarding constructor here will suffice:

template &lt;typename T1, typename T2&gt;
Student(T1&amp;&amp; forename, T2&amp;&amp; surname, long studentNumber);


Make fullName a non-member

It's generally preferable to make your class interface as minimal as possible, and you really gain nothing here by having this as a member method, so make it a non-member:

Student::NameType getFullName(const Student&amp; student);


Return fields by const &amp;

You are making a copy on every call to getFirstName and getSurname, better to return a const reference - the caller can always make a copy if needed.

Database

Don't make Database responsible for reading user input

Your remove functions should not read anything from the user, it obscures the interface and purpose of the class. If you need this functionality, put it into a non-member method:

long getStudentNumberToRemoveFromUser();


Consider a better design

I'd say your design is flawed; you shouldn't be removing Student objects by name (not even full name), as you could have duplicates. Presumably the student number is unique, so this should be the only identifier used for removal. Instead you could offer a public method to gain access for student numbers. So you just have:

std::vector&lt;Student&gt; getMatchingStudents(Student::NameType surname forename, Student::NameType surname) const;
bool remove(const Student&amp; student);


Where the return bool indicates if the record was removed.

Consider Boost.Bimap

Boost.Bimap already solves the two way access problem you are having.

Remove shared_ptr

Assuming you don't want to use Boost.Bimap.

There's really no need to use shared_ptr here; Database has complete control over the lifetime of the Student objects. Introducing the shared_ptr only adds code complexity, additional memory consumption, and confusion. Instead you can either store everything by value (completely feasible for just 2000 records), or store values in mapByStudentNumber and store a raw pointer, or std::reference_wrapper&lt;const Student::NameType in mapByName.

Use better variable names

There's some debate about how to best name maps (xToY, ys, xToYMap etc), but I don't like mapByName and mapByStudentNumber. I'd probably go with namesToNumbers and numbersToNames.