什么是可用于存储和管理整数集合的最佳C++数据结构？

这是我的第一个StackOverflow问题,如果我没有按照社区准则处理这个问题并且我是否应该删除它,请告诉我.

我得到了我的第一个面试问题,因为我的实施而被拒绝了.

问题是:

设计并实现一个存储整数集合的C++类.在施工时,收集应该是空的.相同的数字可以存储多次.

实现以下方法:

插入(int x).插入值"x"的条目.

擦除(int x).从集合中删除一个值为"x"的条目(如果存在).

擦除(int from,int to).删除[from,to]范围内值的所有条目.

Count(int from,int to).计算有多少条目具有[from,to]范围内的值.

我认为一个好的实现是使用链表,因为它使用非连续内存并且删除条目不需要改组大量数据(如向量或数组).但是,我得到了公司的反馈,说我的实施时间复杂度为O(n ^ 2),效率非常低,所以我被拒绝了.如果在另一次采访中弹出类似的问题,我不想重复同样的错误,所以我想知道解决这个问题的最佳方式是什么(朋友建议使用地图,但他也不确定).

我的代码是:

void IntegerCollector::insert(int x)
{
    entries.push_back(x);
}

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

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

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

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

    while (position != entries.end())
    {
        if (*position >= from && *position <= to)
            count++;

        position++;
    }

    return count;
}

反馈意见提到他们只会雇用能够实现O(nlogn)复杂性的候选人.

这里的关键考虑因素是相同值的整数是无法区分的.因此,您需要做的就是在容器中存储每个不同值的计数.

然后,您可以使用一个std::map支持结构,将每个整数(键)映射到它在数据结构中存在的次数(value = count).

插入和擦除单个元素只是递增和递减(在后一种情况下可能删除)给定键的值(两者都O(log(distinct_values_in_container))用于查找键).

由于std::map是有序的,您可以使用lower_bound和upper_bound进行二进制搜索,因此在[from,to]中查找键非常有效(找到范围也是如此O(log(distinct_values_in_container))).删除它们或计算它们的计数很容易(运行时间更复杂).

如果你想获得额外的功劳,那么理解渐近运行时的局限就会付出代价.考虑以下几点:

这些渐近运行时在实践中意味着什么取决于使用模式.如果没有插入重复项,我们就可以了O(n),但是n如果有很多相同的元素(例如,如果每个键都有O(exp(n))值O(distinct_values_in_container) = O(log(n))),你也可以获得任意好的时间(就插入次数而言).在极端情况下,所有涉及的整数都是相同的,所有操作都是O(1).

作为受访者,我还会谈到这些渐近运行时是否在实践中有意义.可能是地图的树结构(对于缓存和分支预测器是有毒的)对于给定的应用程序而言丢失为简单std::vector>(如果擦除总是批量)或甚至是std::vector(如果密钥是"密集的").

我认为你的主要错误(以及你被拒绝的原因)没有意识到不需要单独存储每个插入的整数.不幸的是,你似乎也错过了保持列表排序的可能性,但我没有看到O(n^2)它来自哪里.

如果您被聘用的角色不需要任何以前的编程经验,那么我就不会单独拒绝您的代码示例.

使用a std::list是一个有趣的选择,并显示你已经考虑过这个.您使用C++标准库容器而不是尝试从较低级别构建此容器的事实对我来说是一个yes-hire标志.你的方法(1)很快,但(2),(3)和(4)会很慢.在没有任何其他信息的情况下,您应该安排事情,以便阅读(包括查询)数据比写入更快.你的方法反过来说.有时虽然这是您想要的 - 例如,在实时进行测量时,您希望数据转储阶段尽可能快,而不是以其他任何方式为代价.对于该应用程序,您的解决方案将难以击败!

预订,但绝不是红线:

整数并不意味着int.在没有能够澄清的情况下,建立你的课程

template std::map

哪里Y是整数类型.注意std::size_t用于柜台.它计算特定Y存在的次数.

下次包括一些程序注释.

不要用using namespace std;.虽然教程是为了清晰起见,但专业程序员却没有.