我正在寻找一种数据结构，我可以在其中有效地删除项目并支持随机访问。
我还需要有效的插入，但由于元素的顺序并不重要，我认为我可以为它可能必须存储的最大元素数预分配内存，然后始终将新元素放在末尾，这样就不会重新分配或移动其他元素是必要的。
据我所知，链表非常适合删除，但访问其元素可能需要 O(n) 时间。另一方面，一个简单的数组(例如 C++ 中的 vector)具有随机访问属性，但从这样的结构中删除一个元素的复杂度为 O(n)。
实际上，随机访问要求比我真正需要的要强。我只需要能够随机均匀地选择结构的一个元素。显然高效的访问属性意味着我需要的操作效率，但我不确定这两者是否等同。
提前致谢!
最佳答案
我相信您在问题中暗示的解决方案实际上是您所需要的，除了一个小细节。
你建议:
I thought I can preallocate memory for maximum number of elements it may have to store and then always put the new element at the end so that no reallocation or move of other elements is necessary.
如果您确实可以建立合理的最大条目数，那么我建议您预先分配一个数组(例如，如果最大值在编译时已知，则使用 std::array，或者std::vector otherwise) 和那个数量的条目，建立一个元素计数(以计算当前存储的元素数量)，然后进行如下操作:
我更改的唯一细节是元素删除，我建议您将其实现为与最后一个元素切换位置。
可能的实现:
#include <vector>
#include <utility>
#include <iostream>
template <typename Elem>
class randomaccesstable
{
public:
randomaccesstable(std::size_t initial_size)
: data_(initial_size) , count_(0)
{ }
randomaccesstable &push_back(const Elem &elem)
{
if (count_ < data_.size())
data_[count_++] = elem;
else {
data_.push_back(elem);
++count_;
}
return *this;
}
randomaccesstable &remove(const std::size_t index)
{
if (index < count_)
{
std::swap(data_[index],data_[count_-1]);
--count_;
}
return *this;
}
const Elem &operator[](const std::size_t index) const
{ return data_[index]; }
Elem &operator[](const std::size_t index)
{ return data_[index]; }
std::size_t size() const
{ return count_; }
private:
std::vector<Elem> data_;
std::size_t count_;
};
int main()
{
randomaccesstable<int> table(10);
table.push_back(3);
table.push_back(12);
table.push_back(2);
for (std::size_t i = 0 ; i < table.size() ; ++i)
std::cout << table[i] << ' ';
std::cout << '\n';
table.remove(1); // this removes the entry for 12, swapping it for 2
for (std::size_t i = 0 ; i < table.size() ; ++i)
std::cout << table[i] << ' ';
std::cout << '\n';
return 0;
}
关于c++ - 哪种数据结构支持高效删除和随机访问？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15272538/
类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc
我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h
我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i
我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为
查看Ruby的CSV库的文档，我非常确定这是可能且简单的。我只需要使用Ruby删除CSV文件的前三列，但我没有成功运行它。 最佳答案 csv_table=CSV.read(file_path_in,:headers=>true)csv_table.delete("header_name")csv_table.to_csv#=>ThenewCSVinstringformat检查CSV::Table文档:http://ruby-doc.org/stdlib-1.9.2/libdoc/csv/rdoc/CSV/Table.html
我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah
我有一个围绕一些对象的包装类，我想将这些对象用作散列中的键。包装对象和解包装对象应映射到相同的键。一个简单的例子是这样的:classAattr_reader:xdefinitialize(inner)@inner=innerenddefx;@inner.x;enddef==(other)@inner.x==other.xendenda=A.new(o)#oisjustanyobjectthatallowso.xb=A.new(o)h={a=>5}ph[a]#5ph[b]#nil,shouldbe5ph[o]#nil,shouldbe5我试过==、===、eq?并散列所有无济于事。
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以
我发现ActiveRecord::Base.transaction在复杂方法中非常有效。我想知道是否可以在如下事务中从AWSS3上传/删除文件:S3Object.transactiondo#writeintofiles#raiseanexceptionend引发异常后，每个操作都应在S3上回滚。S3Object这可能吗？？ 最佳答案 虽然S3API具有批量删除功能，但它不支持事务，因为每个删除操作都可以独立于其他操作成功/失败。该API不提供任何批量上传功能(通过PUT或POST)，因此每个上传操作都是通过一个独立的API调用完成的