我有一个整数数组,我需要删除重复项,同时保持每个整数第一次出现的顺序.我可以看到这样做,但想象有一种更好的方法可以更好地利用STL算法吗？插入不受我的控制,因此在插入之前我无法检查重复项.
int unsortedRemoveDuplicates(std::vector<int> &numbers) {
std::set<int> uniqueNumbers;
std::vector<int>::iterator allItr = numbers.begin();
std::vector<int>::iterator unique = allItr;
std::vector<int>::iterator endItr = numbers.end();
for (; allItr != endItr; ++allItr) {
const bool isUnique = uniqueNumbers.insert(*allItr).second;
if (isUnique) {
*unique = *allItr;
++unique;
}
}
const int duplicates = endItr - unique;
numbers.erase(unique, endItr);
return duplicates;
}
如何使用STL算法完成？
请考虑以下数据结构和代码.
struct Sentence {
std::string words;
int frequency;
Sentence(std::string words, int frequency) : words(words), frequency(frequency) {}
};
struct SentencePCompare {
bool operator() (const Sentence* lhs, const Sentence* rhs) const {
if (lhs->frequency != rhs->frequency) {
return lhs->frequency > rhs->frequency;
}
return lhs->words.compare(rhs->words) < 0;
}
};
std::set<Sentence*, SentencePCompare> sentencesByFrequency;
int main(){
Sentence* foo = new Sentence("foo", 1);
Sentence* bar = new Sentence("bar", 2);
sentencesByFrequency.insert(foo);
sentencesByFrequency.insert(bar);
for (Sentence* sp : sentencesByFrequency) {
std::cout << sp->words << std::endl;
}
foo->frequency = 5; …是否std::set将对象存储在连续内存中std::vector？
我在网上找不到这个，cppreference 没有提到内存分配的细节。但我不明白为什么它不能使用连续内存，因此我的问题。
一个明显的(天真的？)方法是:
std::set<int> s;
for (int i = 0; i < SIZE; ++i) {
s.insert(i);
}
这是合理的可读性,但从我的理解,不是最优的,因为它涉及重复搜索插入位置并且没有利用输入序列已经排序的事实.
是否有更优雅/高效(或事实上)的方式来初始化std::set一系列数字？
或者,更一般地说,如何有效地将有序的条目列表插入到集合中？
浏览文档,我刚刚注意到接受迭代器的构造函数来指示插入的位置:
iterator insert ( iterator position, const value_type& x );
这意味着这将更有效:
std::set<int> s;
std::set<int>::iterator it = s.begin();
for (int i = 0; i < SIZE; ++i) {
it = s.insert(it, i);
}
这看起来合理,但我仍然愿意接受更多建议.
我知道标准没有规定必须实现STL容器的方式,而是规定了每个容器的一组要求.
然而,众所周知,STL有序容器通常被实现为红黑树.
您可以使用各自的迭代器迭代a std::set或a 的元素std::map,或者使用ranged循环来迭代C++ 11.
然而令我困惑的是,STL中一个有序的容器如何"知道"它的"结束".或者换句话说,因为它们是作为树实现的,如何实现容器的结束还是可以实现？
我知道标准规定§23.2.1/ c一般容器要求(强调矿井):
begin()返回一个引用容器中第一个元素的迭代器.end()返回一个迭代器,它是容器的past-the-end值.如果容器为空,则begin()== end();
好吧,对于连续的容器来说这很容易,但这种"过去的结果"如何实现树木？
我是C++的新手.我想知道经验丰富的程序员是如何做到这一点的.
是)我有的:
set<int> s;
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(5);
for(set<int>::iterator itr = s.begin(); itr != s.end(); ++itr){
if (!(*itr % 2))
s.erase(itr);
}
当然,它不起作用.因为itr在擦除后会递增.这是否意味着Itr必须在每次擦除集合中的元素后指向集合的开头？
我有一个const-correctness问题,我似乎无法解决.这是我的程序的结构:
class Node
{
private:
int id;
std::set<Node*> neighbours;
public:
Node();
Node(int id_p);
void set_id(const int& id_p);
int get_id() const;
void add_neighbour(Node* neighbour);
bool is_neighbour(Node* neighbour) const;
friend bool operator <(const Node& lhs, const Node& rhs);
};
class Graph
{
private:
std::set<Node> node_list;
public:
Graph();
void add_node(int id);
const Node* get_node_by_id(int id) const;
bool has_node(int id) const;
void check_add_node(int id);
void add_edge(int id_1, int id_2);
bool has_edge(int id_1, int id_2) const;
void check_add_edge(int id_1, int id_2);
(...)
};
现在问题是,如果我调用该函数Graph::get_node_by_id() …
我有地图,哪些键是std :: string.我想在地图中找到以"DUPA/"prefix 开头的那些元素.找到下限很容易,但上限有点问题.我写了这样一段代码:
const char* prefix = "DUPA/";
const char* firstAfterPrefix = "DUPA0";
auto prefixedBeginIt = myMap.upper_bound(prefix);
auto prefixedEndIt = myMap.lower_bound(firstAfterPrefix);
代码工作正常,但我不认为它是优雅的,因为必须知道它0是/在ASCII表中的第一个.第二种方法是复制前缀和增加最后一个符号.你知道更优雅的解决方案吗？