473,382 Members | 1,373 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,382 software developers and data experts.

std::vector removing a random element

From what I learned, if you want to do random element insertions and
deletions you should use a list. But, with std::vector, if the order of the
elements does not matter, couldn't you efficiently remove a random element
by swapping it with the last element and then just using pop_back? Does
erase do this internally? Or does erase do the element shift to fill in the
gap?

Oct 15 '05 #1
2 4704
"vsgdp" <sp**@void.com> wrote in message
news:tA%3f.2513$i%.1327@fed1read07
From what I learned, if you want to do random element insertions and
deletions you should use a list.
A list inserts/deletes equally well in the middle of a list as at either end
whereas a vector inserts/deletes more quickly at the end than it does in the
middle. This doesn't actually tell you anything about the relative
efficiency of lists and vectors for middle operations; it only compares list
operations to other list operations and vector operations to other vector
operations. If relative efficiency of lists and vectors is important, you
should time them for the actual container sizes and operations that are
relevant to you.
But, with std::vector, if the order
of the elements does not matter, couldn't you efficiently remove a
random element by swapping it with the last element and then just
using pop_back?
Yes. For large vectors, a swap and pop_back operation would be quicker. Much
of the time, however, preserving the order of elements does matter.
Does erase do this internally? Or does erase do the
element shift to fill in the gap?


erase preserves the order of remaining elements, so it shifts elements.
--
John Carson

Oct 15 '05 #2

vsgdp wrote:
From what I learned, if you want to do random element insertions and
deletions you should use a list. But, with std::vector, if the order of the
elements does not matter, couldn't you efficiently remove a random element
by swapping it with the last element and then just using pop_back? Does
erase do this internally? Or does erase do the element shift to fill in the
gap?


What operations are you doing with this collection of objects? By
random, do you mean, randomly selected or random access? If you mean
random access, and if the sequence order of the elements does not
matter, it sounds like you should be using a std::set or std::multiset.

Oct 15 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: Tino | last post by:
I have a std::vector<int> which, after some initialization, has a fixed number of elements...after initialization I must do the following repeatedly: I remove an element which could be anywhere in...
18
by: Janina Kramer | last post by:
hi ng, i'm working on a multiplayer game for a variable number of players and on the client side, i'm using a std::vector<CPlayer> to store informatik about the players. CPlayer is a class that...
11
by: Steve | last post by:
Hi, I'm using a std::vector to store a list of user defined objects. The vector may have well over 1000 elements, and I'm suffering a performance hit. If I use push_back I get a much worse...
2
by: Morten Aune Lyrstad | last post by:
Hi! I haven't been using the standard template libraries much. I have a hard time trying to figure out just what is the practical difference between std::vector and std::list. Aren't both basically...
5
by: Eric Lilja | last post by:
Hello, consider this complete program (sorry, it's not minimal but I hope it's readable at least): #include <algorithm> #include <iostream> #include <vector> class Row { public:
17
by: Michael Hopkins | last post by:
Hi all I want to create a std::vector that goes from 1 to n instead of 0 to n-1. The only change this will have is in loops and when the vector returns positions of elements etc. I am calling...
8
by: Ross A. Finlayson | last post by:
I'm trying to write some C code, but I want to use C++'s std::vector. Indeed, if the code is compiled as C++, I want the container to actually be std::vector, in this case of a collection of value...
8
by: Jason Heyes | last post by:
Does the STL have a function like this one? template <typename T> void remove(std::vector<T> &v, std::vector<T>::size_type index) { std::swap(v, v.back()); v.resize(index); } Unlike...
82
by: Peter Olcott | last post by:
I need std::vector like capability for several custom classes. I already discussed this extensively in the thread named ArrayList without Boxing and Unboxing. The solution was to simply create...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.