<p>I'm fairly new to the STL, so I was wondering whether there are any dynamically sortable containers?  At the moment my current thinking is to use a vector in conjunction with the various sort algorithms, but I'm not sure whether there's a more appropriate selection given the (presumably) linear complexity of inserting entries into a sorted vector.</p>

<p>To clarify "dynamically", I am looking for a container that I can modify the sorting order at runtime - e.g. sort it in an ascending order, then later re-sort in a descending order.</p>

[{'answer_id': 67437, 'author': 'Torlack', 'author_id': 5243, 'author_profile': 'https://Stackoverflow.com/users/5243', 'pm_score': 2, 'selected': False, 'text': '<p><code>std::set</code> is basically a sorted container.</p>\n'}, {'answer_id': 67460, 'author': 'Doug T.', 'author_id': 8123, 'author_profile': 'https://Stackoverflow.com/users/8123', 'pm_score': 4, 'selected': False, 'text': '<p>You\'ll want to look at std::map</p>\n\n<pre><code>std::map&lt;keyType, valueType&gt;\n</code></pre>\n\n<p>The map is sorted based on the &lt; operator provided for keyType.</p>\n\n<p>Or </p>\n\n<pre><code>std::set&lt;valueType&gt;\n</code></pre>\n\n<p>Also sorted on the &lt; operator of the template argument, but does not allow duplicate elements.</p>\n\n<p>There\'s</p>\n\n<pre><code>std::multiset&lt;valueType&gt;\n</code></pre>\n\n<p>which does the same thing as std::set but allows identical elements.</p>\n\n<p>I highly reccomend "The C++ Standard Library" by Josuttis for more information. It is the most comprehensive overview of the std library, very readable, and chock full of obscure and not-so-obscure information.</p>\n\n<p>Also, as mentioned by 17 of 26, Effective Stl by Meyers is worth a read.</p>\n'}, {'answer_id': 67465, 'author': '17 of 26', 'author_id': 2284, 'author_profile': 'https://Stackoverflow.com/users/2284', 'pm_score': 0, 'selected': False, 'text': '<p>STL maps and sets are both sorted containers.</p>\n\n<p>I second Doug T\'s book recommendation - the Josuttis STL book is the best I\'ve ever seen as both a learning and reference book.</p>\n\n<p><a href="https://rads.stackoverflow.com/amzn/click/com/0201749629" rel="nofollow noreferrer" rel="nofollow noreferrer">Effective STL</a> is also an excellent book for learning the inner details of STL and what you should and shouldn\'t do.</p>\n'}, {'answer_id': 67496, 'author': 'yrp', 'author_id': 7228, 'author_profile': 'https://Stackoverflow.com/users/7228', 'pm_score': 0, 'selected': False, 'text': '<p>For "STL compatible" sorted vector see A. Alexandrescu\'s AssocVector from <a href="http://loki-lib.sourceforge.net/" rel="nofollow noreferrer">Loki</a>.</p>\n'}, {'answer_id': 67531, 'author': 'zweiterlinde', 'author_id': 6592, 'author_profile': 'https://Stackoverflow.com/users/6592', 'pm_score': 1, 'selected': False, 'text': "<p>You should definitely use a set/map.  Like hazzen says, you get O(log n) insert/find.  You won't get this with a sorted vector; you can get O(log n) find using binary search, but insertion is O(n) because inserting (or deleting) an item may cause all existing items in the vector to be shifted.</p>\n"}, {'answer_id': 67586, 'author': 'yrp', 'author_id': 7228, 'author_profile': 'https://Stackoverflow.com/users/7228', 'pm_score': 1, 'selected': False, 'text': "<p>It's not that simple. In my experience insert/delete is used less often than find. Advantage of sorted vector is that it takes less memory and is more cache-friendly. If happen to have version that is compatible with STL maps (like the one I linked before) it's easy to switch back and forth and use optimal container for every situation.</p>\n"}, {'answer_id': 67618, 'author': 'ugasoft', 'author_id': 10120, 'author_profile': 'https://Stackoverflow.com/users/10120', 'pm_score': 1, 'selected': False, 'text': '<p>in theory an associative container (set, multiset, map, multimap) should be your best solution.</p>\n\n<p>In practice it depends by the average number of the elements you are putting in.\nfor less than 100 elements a vector is probably the best solution due to:\n- avoiding continuous allocation-deallocation\n- cache friendly due to data locality\nthese advantages probably will outperform nevertheless continuous sorting.\nObviously it also depends on how many insertion-deletation you have to do. Are you going to do per-frame insertion/deletation?</p>\n\n<p>More generally: are you talking about a performance-critical application?</p>\n\n<p>remember to not prematurely optimize...</p>\n'}, {'answer_id': 67683, 'author': 'hazzen', 'author_id': 5066, 'author_profile': 'https://Stackoverflow.com/users/5066', 'pm_score': 2, 'selected': False, 'text': '<p>The <code>stl</code> provides no such container. You can define your own, backed by either a <code>set/multiset</code> or a <code>vector</code>, but you are going to have to re-sort every time the sorting function changes by either calling <code>sort</code> (for a <code>vector</code>) or by creating a new collection (for <code>set/multiset</code>).</p>\n\n<p>If you just want to change from increasing sort order to decreasing sort order, you can use the reverse iterator on your container by calling <code>rbegin()</code> and <code>rend()</code> instead of <code>begin()</code> and <code>end()</code>. Both <code>vector</code> and <code>set/multiset</code> are reversible containers, so this would work for either.</p>\n'}, {'answer_id': 67701, 'author': 'moswald', 'author_id': 8368, 'author_profile': 'https://Stackoverflow.com/users/8368', 'pm_score': 4, 'selected': True, 'text': '<p>If you know you\'re going to be sorting on a single value ascending and descending, then set is your friend.  Use a reverse iterator when you want to "sort" in the opposite direction.</p>\n\n<p>If your objects are complex and you\'re going to be sorting in many different ways based on the member fields within the objects, then you\'re probably better off with using a vector and sort.  Try to do your inserts all at once, and then call sort once.  If that isn\'t feasible, then deque may be a better option than the vector for large collections of objects.</p>\n\n<p>I think that if you\'re interested in <em>that</em> level of optimization, you had better be profiling your code using actual data. (Which is probably the best advice anyone here can give: it may not matter that you call sort after each insert if you\'re only doing it once in a blue moon.)</p>\n'}, {'answer_id': 67991, 'author': 'JProgrammer', 'author_id': 1675, 'author_profile': 'https://Stackoverflow.com/users/1675', 'pm_score': 1, 'selected': False, 'text': '<p>The answer is as always it depends.</p>\n\n<p><code>set</code> and <code>multiset</code> are appropriate for keeping items sorted but are generally optimised for a balanced set of add, remove and fetch. If you have manly lookup operations then a sorted <code>vector</code> may be more appropriate and then use <code>lower_bound</code> to lookup the element.</p>\n\n<p>Also your second requirement of resorting in a different order at runtime will actually mean that <code>set</code> and <code>multiset</code> are not appropriate because the predicate cannot be modified a run time.</p>\n\n<p>I would therefore recommend a sorted vector. But remember to pass the same predicate to <code>lower_bound</code> that you passed to the previous sort as the results will be undefined and most likely wrong if you pass the wrong predicate.</p>\n'}, {'answer_id': 68162, 'author': 'Max Lybbert', 'author_id': 10593, 'author_profile': 'https://Stackoverflow.com/users/10593', 'pm_score': 2, 'selected': False, 'text': '<p>It sounds like you want a <a href="http://www.boost.org/doc/libs/1_36_0/libs/multi_index/doc/index.html" rel="nofollow noreferrer">multi-index container</a>.  This allows you to create a container and tell that container the various ways you may want to traverse the items in it.  The container then keeps multiple lists of the items, and those lists are updated on each insert/delete.</p>\n\n<p>If you really want to re-sort the container, you can call the <a href="http://www.sgi.com/tech/stl/sort.html" rel="nofollow noreferrer"><code>std::sort</code></a> function on any <code>std::deque</code>, <code>std::vector</code>, or even a simple C-style array.  That function takes an optional third argument to determine how to sort the contents.</p>\n'}, {'answer_id': 7653110, 'author': 'user864791', 'author_id': 864791, 'author_profile': 'https://Stackoverflow.com/users/864791', 'pm_score': 1, 'selected': False, 'text': "<p>Set and multiset use an underlying binary tree; you can define the &lt;= operator for your own use.  These containers keep themselves sorted, so may not be the best choice if you are switching sort parameters.  Vectors and lists are probably best if you are going to be resorting quite a bit; in general list has it's own sort (usually a mergesort) and you can use the stl binary search algorithm on vectors.  If inserts will dominate, list outperforms vector.</p>\n"}]
['https://Stackoverflow.com/questions/67426', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/10247/']