What is the best C++ data structure that could be used for storing and managing a collection of integers? : <p>this is my first StackOverflow question so please let me know if I didn't follow community guidelines with this question and if I should delete it.</p>

<p>I got my first ever interview question and I got rejected because of my implementation.</p>

<p>The question is:</p>

<p>Design and implement a C++ class that stores a collection of integers. On construction, the collection should be empty. The same number may be stored more than once. </p>

<p>Implement the following methods: </p>

<ol>
<li><p>Insert(int x).  Insert an entry for the value “x”. </p></li>
<li><p>Erase(int x).  Remove one entry with the value “x” (if one exists) from the collection.  </p></li>
<li><p>Erase(int from, int to).  Remove all the entries with a value in the range [from, to). </p></li>
<li><p>Count(int from, int to).  Count how many entries have a value in the range [from, to). </p></li>
</ol>

<p>I thought a good implementation would be to use linked lists since it uses non-contiguous memory and removing entries would not require shuffling a lot of data (like in vectors or arrays). However, I got feedback from the company saying my implementation was O(n^2) time complexity and was very inefficient so I was rejected. I don't want to repeat the same mistake if a similar question pops up in another interview so I'd like to know what is the best way to approach this question (a friend suggested using maps but he is also unsure).</p>

<p>My code is:</p>

<pre><code>void IntegerCollector::insert(int x)
{
    entries.push_back(x);
}

void IntegerCollector::erase(int x)
{
    list&lt;int&gt;::iterator position = find(entries.begin(), entries.end(), x);
    if (position != entries.end())
        entries.erase(position);
}

void IntegerCollector::erase(int from, int to)
{
    list&lt;int&gt;::iterator position = entries.begin();

    while (position != entries.end())
    {
        if (*position &gt;= from &amp;&amp; *position &lt;= to)
            position = entries.erase(position);
        else
            position++;
    }
}

int IntegerCollector::count(int from, int to)
{
    list&lt;int&gt;::iterator position = entries.begin();
    int count = 0;

    while (position != entries.end())
    {
        if (*position &gt;= from &amp;&amp; *position &lt;= to)
            count++;

        position++;
    }

    return count;
}
</code></pre>

<p>The feedback mentioned that they would only hire candidates that can implement solutions with O(nlogn) complexity.</p>
