Перемешать список строк в C ++ - PullRequest
Новая
       118

Перемешать список строк в C ++

2 голосов
/ 03 августа 2020

Я пытался перемешать следующий список строк: 

list<string> l({"10000007", "1", "4", "5", "7", "12", "23", "25", "26", "27", "30", "31", "32", "44", "46", "47", "59", "65", "91"})

все мои попытки потерпели неудачу. Это одна из моих лучших попыток.

Попробуйте 1

В основном я копирую из этого ответа Случайно произвольно выбираю std :: list 

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <random>
#include <numeric>

int main() {
    std::list<std::string> l({"10000007", "1", "4", "5", "7", "12", "23", "25", "26", "27", "30", "31", "32", "44", "46", "47", "59", "65", "91"});
    std::vector<std::reference_wrapper<std::string>> v(l.cbegin(), l.cend());
    std::random_device rd;
    std::mt19937 generator(rd());
    std::shuffle(v.begin(), v.end(), generator);
    std::cout << "Original list:\n";
    std::copy(l.cbegin(), l.cend(), std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << "\nShuffled view:\n";
    std::copy(v.cbegin(), v.cend(), std::ostream_iterator<std::string>(std::cout, " "));
}

У меня была эта трассировка ошибки: 

In file included from /usr/include/c++/7/vector:62:0,
                 from /usr/include/c++/7/functional:61,
                 from prueba.cpp:2:
/usr/include/c++/7/bits/stl_construct.h: In instantiation of ‘void std::_Construct(_T1*, _Args&& ...) [with _T1 = std::reference_wrapper<std::__cxx11::basic_string<char> >; _Args = {const std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&}]’:
/usr/include/c++/7/bits/stl_uninitialized.h:83:18:   required from ‘static _ForwardIterator std::__uninitialized_copy<_TrivialValueTypes>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; _ForwardIterator = std::reference_wrapper<std::__cxx11::basic_string<char> >*; bool _TrivialValueTypes = false]’
/usr/include/c++/7/bits/stl_uninitialized.h:134:15:   required from ‘_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; _ForwardIterator = std::reference_wrapper<std::__cxx11::basic_string<char> >*]’
/usr/include/c++/7/bits/stl_uninitialized.h:289:37:   required from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; _ForwardIterator = std::reference_wrapper<std::__cxx11::basic_string<char> >*; _Tp = std::reference_wrapper<std::__cxx11::basic_string<char> >]’
/usr/include/c++/7/bits/stl_vector.h:1331:33:   required from ‘void std::vector<_Tp, _Alloc>::_M_range_initialize(_ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with _ForwardIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; _Tp = std::reference_wrapper<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::reference_wrapper<std::__cxx11::basic_string<char> > >]’
/usr/include/c++/7/bits/stl_vector.h:1299:23:   required from ‘void std::vector<_Tp, _Alloc>::_M_initialize_dispatch(_InputIterator, _InputIterator, std::__false_type) [with _InputIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; _Tp = std::reference_wrapper<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::reference_wrapper<std::__cxx11::basic_string<char> > >]’
/usr/include/c++/7/bits/stl_vector.h:414:26:   required from ‘std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = std::_List_const_iterator<std::__cxx11::basic_string<char> >; <template-parameter-2-2> = void; _Tp = std::reference_wrapper<std::__cxx11::basic_string<char> >; _Alloc = std::allocator<std::reference_wrapper<std::__cxx11::basic_string<char> > >; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::reference_wrapper<std::__cxx11::basic_string<char> > >]’
prueba.cpp:13:76:   required from here
/usr/include/c++/7/bits/stl_construct.h:75:7: error: binding reference of type ‘std::__cxx11::basic_string<char>&’ to ‘const std::__cxx11::basic_string<char>’ discards qualifiers
     { ::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...); }
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/std_function.h:44:0,
                 from /usr/include/c++/7/functional:58,
                 from prueba.cpp:2:
/usr/include/c++/7/bits/refwrap.h:334:7: note:   initializing argument 1 of ‘std::reference_wrapper<_Tp>::reference_wrapper(_Tp&) [with _Tp = std::__cxx11::basic_string<char>]’
       reference_wrapper(_Tp& __indata) noexcept
       ^~~~~~~~~~~~~~~~~

Я безуспешно пытался понять, что reference_wrapper делает в этом примере.

Другие попытки

Все мои попытки с комбинациями классические также терпят неудачу ... С random_engine, shuffle и srand с ошибкой трассировки в тысячи строк.

Почему бы не преобразовать в целые числа?

В моем исходном коде есть два файла. json, jsons всегда имеют ключи в строковом формате. Я знаю, что могу преобразовать список строк в список целых чисел, но проблема в том, что я создаю и алгоритм, и есть:

  • 2000 списков
  • 2000 итераций в алгоритм
  • Вы должны выполнить это преобразование несколько раз на итерацию (строки в int, int в строку ...)

Так что я думаю, что этот вариант будет быть очень дорогим в вычислительном отношении.

Заранее спасибо.

Ответы [ 3 ]

4 голосов
/ 03 августа 2020

В этой строке: 

std::vector<std::reference_wrapper<std::string>> v(l.cbegin(), l.cend());

вы используете const_iterator s для построения вектора, что вызывает ошибку несоответствия типов при построении reference_wrapper<std::string> s из const std::string.

Вместо этого вам нужны неконстантные итераторы, например: 

std::vector<std::reference_wrapper<std::string>> v(l.begin(), l.end());

Вот демонстрация .

3 голосов
/ 03 августа 2020

Функция-член cbegin() возвращает const_iterator, который при разыменовании возвращает const std::string&.

Измените создание vector на: 

std::vector<std::reference_wrapper<const std::string>> v(l.cbegin(), l.cend());

Демо

1 голос
/ 03 августа 2020

Я бы начал с вопроса об использовании / необходимости использования std::list вообще. В этом случае кажется, что вы используете list только для инициализации vector. В этом случае вы можете просто инициализировать и использовать vector напрямую: 

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <random>
#include <numeric>

int main() {
    std::vector<std::string> v({"10000007", "1", "4", "5", "7", "12", "23", "25", "26", "27", "30", "31", "32", "44", "46", "47", "59", "65", "91"});
    std::random_device rd;

    std::cout << "Original list:\n";
    std::copy(v.cbegin(), v.cend(), std::ostream_iterator<std::string>(std::cout, " "));

    std::mt19937 generator(rd());
    std::shuffle(v.begin(), v.end(), generator);

    std::cout << "\nShuffled view:\n";
    std::copy(v.cbegin(), v.cend(), std::ostream_iterator<std::string>(std::cout, " "));

    std::cout << "\n";    
}

Если вы действительно настаиваете на использовании списка, вы можете избавиться от ссылочной оболочки, и она работа: 

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <random>
#include <numeric>

int main() {
    std::list<std::string> l({"10000007", "1", "4", "5", "7", "12", "23", "25", "26", "27", "30", "31", "32", "44", "46", "47", "59", "65", "91"});
    std::vector<std::string> v(l.cbegin(), l.cend());
    std::random_device rd;
    std::mt19937 generator(rd());
    std::shuffle(v.begin(), v.end(), generator);
    std::cout << "Original list:\n";
    std::copy(l.cbegin(), l.cend(), std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << "\nShuffled view:\n";
    std::copy(v.cbegin(), v.cend(), std::ostream_iterator<std::string>(std::cout, " "));
}

... но я не вижу в этом особого смысла.

Что касается затрат на хранение целых чисел и строк: до тех пор, пока вы ' re использует сравнительно недавний компилятор, поэтому его (библиотечная) реализация std::string имеет оптимизацию коротких строк, вероятно, между ними нет большой разницы. Если вам (возможно) потребуется поддержка более старого компилятора, в котором отсутствует оптимизация коротких строк, это резко увеличивает шансы на то, что вам будет лучше преобразовывать и хранить int s вместо хранения строк.

Проблема в том, что довольно просто: без оптимизации коротких строк каждая строка приведет к выделению кучи для хранения фактических данных. Это выделение кучи может быть медленнее, чем преобразование в int и из int (но вам нужно будет протестировать, чтобы быть уверенным). весь файл json, а затем создайте string_view объектов для значений, которые вам нужны. Затем вы можете перетасовать объекты string_view и распечатать их (или что-то еще) по своему усмотрению, но все они просто содержат указатели на исходные данные, поэтому вы не копируете все базовые данные.

...