How to add data to sorted vector?
-
Hello, I have to add data to a vector in sorted order. For example: 3,7,3,4 must be: 1)3 2)3,7 3)3,3,7 4)3,3,4,7 What is the most quick way to do this? Or maybe other data stuctures like Map would be better for this task?
You may use a multiset [^]. :)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong. -- Iain Clarke
[My articles] -
Hello, I have to add data to a vector in sorted order. For example: 3,7,3,4 must be: 1)3 2)3,7 3)3,3,7 4)3,3,4,7 What is the most quick way to do this? Or maybe other data stuctures like Map would be better for this task?
-
-
Hello, I have to add data to a vector in sorted order. For example: 3,7,3,4 must be: 1)3 2)3,7 3)3,3,7 4)3,3,4,7 What is the most quick way to do this? Or maybe other data stuctures like Map would be better for this task?
Depends on the usage patterns. If the number of lookups is significantly higher than the number of inserts, then I'd just use a sorted vector (as my experiences indicate that a binary search on a sorted vector is significantly faster than use of STL's associative containers in C++). If inserts are more significant than that, use a
std::multisetas suggested elsewhere. If using a sorted vector, it helps to delay the sort operation until required, using something like below, rather than blindly sorting on every insert.template<class Type>
class SortedVector
{
public:
SortedVector() sorted_(true) {}
void insert(Type const& value)
{
sorted_ = false;
data_.push_back(value);
}
typename std::vector<Type>::const_iterator find(Type const& value) const
{
if (!sorted_)
{
std::sort(data_.begin(), data_.end());
sorted_ = true;
}
std::vector<Type>::const_iterator found =
std::lower_bound(data_.begin(), data_.end(), value);
return (*found == value)?found:data_.end();
}
private:
mutable bool sorted_;
mutable std::vector<Type> data_;
};Java, Basic, who cares - it's all a bunch of tree-hugging hippy cr*p
