草庐IT

c++ - 具有 O(1) 性能的类似 STL 的容器

coder 2024-02-07 原文

我找不到答案，但我很确定我不是第一个寻找这个的人。 有没有人知道/使用/看到一个类似STL的容器，它具有双向访问迭代器，对于插入/删除具有O(1)复杂性/查找 ?
谢谢。

最佳答案

插入、删除和查找没有复杂度为 O(1) 的抽象数据类型，它还提供双向访问迭代器。

编辑:

对于任意大的域都是如此。给定一个足够小的域，您可以使用数组和双向链表实现一个具有 O(1) 复杂度的插入、删除和查找集合以及双向访问迭代器:

std::list::iterator array[MAX_VALUE];
std::list list;

初始化:

for (int i=0;i<MAX_VALUE;i++)
    array[i] = list.end();

插入:

if (array[value] != list.end())
    array[value] = list.insert(value);

删除:

if (array[value] != list.end()) {
    array[value].erase();
    array[value] = list.end();
}

查找:

array[value] != list.end()

关于c++ - 具有 O(1) 性能的类似 STL 的容器，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1601060/

容器ampstrongsectioncodec++stl

有关c++ - 具有 O(1) 性能的类似 STL 的容器的更多相关文章

  1. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby-on-rails - Rails 3.1 中具有相同形式的多个模型？ - 2

    我正在使用Rails3.1并在一个论坛上工作。我有一个名为Topic的模型，每个模型都有许多Post。当用户创建新主题时，他们也应该创建第一个Post。但是，我不确定如何以相同的形式执行此操作。这是我的代码:classTopic:destroyaccepts_nested_attributes_for:postsvalidates_presence_of:titleendclassPost...但这似乎不起作用。有什么想法吗？谢谢! 最佳答案 @Pablo的回答似乎有你需要的一切。但更具体地说...首先改变你View中的这一行对此#

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  7. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  8. ruby - Ruby 是否有类似于 Perl 的 "perl -d"的逐步调试器？ - 2

    Ruby是否有逐步调试器，类似于Perl的“perl-d”？ 最佳答案 ruby-debug(对于ruby1.8)，debugger(对于ruby1.9)，byebug(对于ruby​​2.0)以及trepanning系列都有一个-x或--trace选项。在调试器内部，命令setlinetrace将打开或关闭线路跟踪。这是themanualforruby-debug原来的答案已经修改，因为数据噪声文章的链接，唉，不再有效了。还添加了ruby​​-debug的后继者 关于ruby-Ruby

  9. ruby - 使对象的行为类似于 ruby​​ 中并行分配的数组 - 2

    假设您在Ruby中执行此操作:ar=[1,2]x,y=ar然后，x==1和y==2。是否有一种方法可以在我自己的类中定义，从而产生相同的效果？例如rb=AllYourCode.newx,y=rb到目前为止，对于这样的赋值，我所能做的就是使x==rb和y=nil。Python有这样一个特性:>>>classFoo:...def__iter__(self):...returniter([1,2])...>>>x,y=Foo()>>>x1>>>y2 最佳答案 是的。定义#to_ary。这将使您的对象被视为要分配的数组。irb>o=Obje

  10. ruby-on-rails - 具有同名的模块和类 - 2

    我有一个模块stat存在于目录结构中:lib/stat_creator/stat/在lib/stat_creator/stat.rb中，我在lib/stat_creator/stat/目录中有我需要的文件，以及:moduleStatCreatormoduleStatendend当我使用该模块时，我将这些类称为StatCreator::Stat::Foo.new现在我想要一个存在于应用程序中的根Stat类。我在app/models中制作了我的Stat类，并在routes.rb中进行了设置。但是，如果我转到Rails控制台并尝试在应用程序/模型中使用Stat类，例如:Stat.by_use

随机推荐