Условно скопировать ключи карты в вектор - PullRequest
Новая
       35

Условно скопировать ключи карты в вектор

0 голосов
/ 16 июля 2011

У меня есть контейнер с картой. Я хочу скопировать все его ключи с указанными пользователем первыми буквами в вектор. Как это сделать эффективно? Спасибо! 

std::map(std:string, size_t) myMap;
myMap.insert(std:make_pair("Ace", 11);
myMap.insert(std:make_pair("Ape", 12);
myMap.insert(std:make_pair("Age", 13);
myMap.insert(std:make_pair("Beat", 21);
myMap.insert(std:make_pair("Boat", 22);
myMap.insert(std:make_pair("Boss", 23);
myMap.insert(std:make_pair("Coat", 31);
myMap.insert(std:make_pair("Cost", 32);
myMap.insert(std:make_pair("Cast", 33);

Например, если я хочу извлечь все элементы с ключами, начинающимися с "Bo" из myMap, и заполнить удовлетворенные результаты в myVec, myVec будет иметь следующие элементы: 

Boat
Boss

Ответы [ 4 ]

1 голос
/ 16 июля 2011

ЕСЛИ вы можете предположить, что буквы, представляющие строку, являются последовательными и , что "one-past-z" по-прежнему является допустимым символом строки, вы можете использовать два вызоваlower_bound и transform, которые располагаются в векторе. 

const_iterator start = myMap.lower_bound("Bo");
const_iterator finish = myMap.lower_bound("Bp");  // "Bo" with the last digit incremented by 1

struct Transformer
{
    mapKey operator()(const myMapType::value_type& item)
    {
        return item.first;
    }
}

vector<mapKey> output;
std::transform(start, finish, std::back_inserter(output), Transformer());
1 голос
/ 16 июля 2011

Объявления опущены для краткости: 

begin = myMap.lower_bound("Bo");
end = std::find_if(begin, myMap.end(), first_does_not_begin_with("Bo"));
for (i=begin; i!=end; ++i)
    myVec.push_back(i->first);

Вы можете реализовать класс функторов first_does_not_begin_with, верно?Оператор должен иметь такую ​​подпись: 

bool operator()(std::pair<const std::string, size_t> const &);
0 голосов
/ 16 июля 2011

Наряду с myMap вы также можете сохранить multimap, в котором ключом будет двухбуквенная строка, и итератор исходной карты в качестве значения.map::insert возвращает итератор (через pair), который вы можете поместить в multimap объект.

Всякий раз, когда вам нужен эффективный поиск двухбуквенного ключа, просто найдите multimap, получите итераторов оригинальной карты 'и используйте их.Объект multimap будет ничем иным, как index на вашей исходной карте - идея, которая используется в системах баз данных.Важно знать, что в оригинальном map должно быть много элементов, иначе использование multimap в качестве индексатора не будет таким выгодным.

0 голосов
/ 16 июля 2011

Мое решение: 

std::string token = "Bo"; //first few letters
std::vector<std::string> myVec;
for(std::map<std::string,size_t>::iterator i=myMap.begin();i!=myMap.end();i++)
{
       if ( token == i->first.substr(0, token.size()) )
               myVec.push_back(i->first);
}
for(std::vector<std::string>::iterator i=myVec.begin();i!=myVec.end();i++ )
      std::cout << *i << std::endl;

Выход: 

Boat
Boss

Полная демонстрация: http://www.ideone.com/03cps

А если вам нравятся <algorithm> и <iterator>, тогда вы можете сделать это вместо этого: 

std::vector<std::string> myVec=std::for_each(myMap.begin(),myMap.end(),collector("Bo"));
std::ostream_iterator<std::string> oiterator(std::cout, "\n");
std::copy(myVec.begin(), myVec.end(), oiterator);

Выход: 

Boat
Boss

А функтор collector реализован так: 

struct collector
{
   std::string token;
   std::vector<std::string> keys;
   collector(const std::string & token) : token(token) {}
   void operator()(const std::pair<std::string,size_t> &p)
   {
        if ( token == p.first.substr(0, token.size()) )
               keys.push_back(p.first);
   }
   operator std::vector<std::string>() { return keys; }
};

Полная демонстрация: http://www.ideone.com/U1299

...